This is a little “flashback” intermission in my posts about my debate with Aram Harrow. This time I try to refer to Cris Moore’s question regarding the motivation for my study. For the readers it givesan opportunity to win a $50 prize!
(Cris Moore, the debate’s very first comment!) I am also a little confused by Gil’s motivation for his conjectures. (My response:) To the best of my memory, my main motivation for skeptically studying quantum fault-tolerance was that I thought that this is a direction worth pursuing and that I had a shot at it.
While listening with Ravi Kannan to this 2002 lecture by Michel Devoret at Yale, I wondered if there are enough scientists working on the “mirage” side.
Flashback: Mittag-Leffler 2005
I started systematically thinking about quantum fault-tolerance in February 2005. There were several things that triggered my interest to the question in the previous fall and I decided to spend some time learning and thinking about it in our winter break. One of those triggers was something Dorit Aharonov told me a few months earlier: she said that once, when she was telling her students about quantum computers, she suddenly had a feeling that maybe it was all just nonsense. Another trigger came from a former student who told me about a Polish scientist (whose name he could not remember) who wrote an article about impossibility of quantum error-correction. I thought that the lack of a quantum analog of the repetition code, and the unique properties of the majority function in terms of sensitivity to noise that I studied with Itai Benjamini and Oded Schramm earlier could be a good starting point for looking skeptically at quantum computers.
In our 2005 winter break, I spent two weeks at Yale and then additional two weeks at the Mittag-Leffler institute near Stockholm. At Yale, I only had little time to think about quantum computers. I had to finish a survey article with Muli Safra about threshold phenomena (To a volume that Cris Moore and Allon Perkus were among the editors). One of the last days in Yale we went to dinner with two guests, Chris Skinner who gave the colloquium talk, and Andrei Okounkov who visited me and gave a talk about partition enumeration and mirror symmetry. At the dinner Andrew Casson asked, out of the blue, if we think that quantum computers can be built and it almost seemed as if that Andrew was reading my mind on what I plan to work on the weeks to come. My answer there was the same as my answer now, that I tend to find it implausible.
Mittag-Leffler Institute February 2005 with Xavier Viennot and Alain Lascoux
In Sweden I spent most of my time on quantum fault-tolerance. I was jet-lagged and being jet-lagged in the Mittag-Leffler institute already worked for me once, when finding my subexponential randomized variant of the simplex algorithm was a substitute for sleeping some night in fall 1991 . In 2005 it was not as bad, I just came to my office very early in the morning and started working. And very early in the morning somebody was already playing the piano.
And who was playing the piano at the institute in the cold Swedish mornings of February 2005? The first reader to guess correctly, and convince me in a comment that she or he knows the answer without revealing it to everybody else will get $50. Continue reading →
This is the second of three posts giving few of the non-technical highlights of my debate with Aram Harrow. (part I)
After Aram Harrow and I got in touch in June 2011, and decided to have a blog debate about quantum fault-tolerance towards the end of 2011, the first post in our debate was launched on January 30, 2012. The first post mainly presented my point of view and it led to lovely intensive discussions. It was time for Aram’s reply and some people started to lose their patience.
(rrtucky) Is Aram, the other “debater”, writing a dissertation in Greek, as a reply?
Dave Bacon was the patron saint for Aram’s first post.
(Aram) There are many reasons why quantum computers may never be built… The one thing I am confident of is that we are unlikely to find any obstacle in principle to building a quantum computer.
(Aram) If you want to prove that 3-SAT requires exponential time, then you need an argument that somehow doesn’t apply to 2-SAT or XOR-SAT. If you want to prove that the permanent requires super-polynomial circuits, you need an argument that doesn’t apply to the determinant. And if you want to disprove fault-tolerant quantum computing, you need an argument that doesn’t also refute fault-tolerant classical computing.
From the discussion
Why not yet? Boaz set a deadline
(Boaz Barak) could [you] explain a bit about the reasons why people haven’t been able to build quantum computers with more than a handful of qubits yet? Continue reading →
(Email from Aram Harrow, June 4, 2011) Dear Gil Kalai, I am a quantum computing researcher, and was wondering about a few points in your paper…
(Aram’s email was detailed and thoughtful and at the end he proposed to continue the discussion privately or as part of a public discussion.)
(Gil to Aram) Thank you for your email and interest. Let me try to answer the points you raised. … (I gave a detailed answer.) … Right now, I don’t plan on initiating a public discussion. How useful such public discussions are (and how to make them useful) is also an interesting issue. Still they were useful for me, as two of my conjectures were raised first in a discussion on Dave Bacon’s blog and another one is partially motivated by a little discussion with Peter Shor on my blog. Continue reading →
(A few more quantum posts are coming. But let’s have a quick break for games.)
Tic Tac Toe is played since anciant times. For the common version, where the two players X and O take turns in marking the empty squares in a 3 by 3 board – each player has a strategy that can guarantee a draw.
Now suppose that the X player has a budget of Y dollars, the O playare has a budget of 100 dollars and before each round the two players bid who makes the next move. The highest bidder makes the move and his budget is reduced by his bid.
For example, if, to start with, the X player have 120 dollars, and if for the first move X bids 40 dollars and O bids 30 dollars, then X will make the first move and will be left with 80 dollars while O will be left with his 100 dollars.
What would you expect the minimal value of Y is so the X player has a winning strategy? Of course if Y>300, X can make 3 uninterrupted moves and win, but perhaps much less is enough?
(Thanks to Reshef Meir and Moshe Tennenholtz)
Update: Another variant of this game is when the player winning the turn pays his bid to the other player. (This version is called “Richman game,” while the variant above is called “Poorman game”. In this case if Y> 800 the X player can play three moves and win. And again the question is what is the infimum value of Y for which the X player can force a win…
I gathered a few of the comments made by participants of my lecture “Why quantum computers cannot work and how”, and a few of my answers. Here they are along with some of the lecture’s slides. Here is the link for the full presentation.
Last Friday, I gave a lecture at the quantum information seminar at MIT entitled “Why quantum computers cannot work and how.” It was a nice event with lovely participation during the talk, and a continued discussion after it. Many very interesting and useful remarks were made. Here are the slides. (The abstract can be found on this page.)
After having an almost a year-longdebate with Aram Harrow, I finally met Aram in person, and we had nice time together during my visit.
Aram is so nice that had it been up to me I would certainly make quantum computers possible (But this is not up to us and all we can do is to try to explore if QC are possible or not.)
We talked about quite a few topics starting with various exotic models of noise that treat differently classic and quantum information, the relevance of locally correctable codes and their quantum counterparts, the sum of Squares/Lasserre hierarchy, unique games and hypercontractivity, my smoothed Lindblad evolutions , NMR and spin-echo, quantum annealing and stoquasicity, and works by Mossbüer, Rekha Thomas, and Monique Laurent were mentioned.
I just returned yesterday night from Yale after a very fruitful visit. Here is a picture of a snowcar decorated with car mirrors from the great blizzard.
Maximal lattice-free convex bodies introduced by Herb Scarf and the related complex of maximal lattice free simplices (also known as the Scarf complex) are remarkable geometric constructions with deep connections to combinatorics, convex geometry, integer programming, game theory, fixed point computations, algebraic geometry, and economics. It is certainly an object I would like to think more and tell you more about. Here is a sculpture made by artist Ann Lehman based on such a body generated by a certain 4 by 3 matrix.
Ann Lehman: A sculpture based on a maximal lattice free convex body (photograph taken by the sculptress).
The body described in this sculpture is topologically a (two dimensional) disk, triangulated in a specific way. The boundary is a polygon embedded in 3-space consist of 21 ”blue” edges. The “black” edges are internal edges of the triangulation. The triangles of the triangulation are not part of the sculpture but it is easy to figure out what they are and the shape has a remarkable zigzag nature. All vertices are integral. The only interior integral point is in “red”. (The “green” point is the origin, it is not in the body.)
Herb Scarf, me , and the sculpture (picture taken by Kareen Rozen)
Let G be a simple planar graph with V vertices and E edges. It follows from Euler’s theorem that
E ≤ 3V
In fact, we have (when V is at least 3,) that E ≤ 3V – 6.
To see this, denote by F the number of regions or faces determined by G (in other words, the number of connected components in the complement of the embedded graph). Euler’s theorem asserts that
E – V + F = 2
V – E + F = 2
and now note that every face must have at least three edges and every edge is contained in two faces and therefore , so 6=3V – 3E + 3F ≤ 3V – 3E +2E.
2. F ≤ 4E
Now let K be a two-dimensional simplicial complex and suppose that K can be embedded in . Denote by E the number of edges of K and by F the number of 2-faces of K.
Here is a really great conjecture:
F ≤ 4E
A weaker version which is also widely open and very interesting is:
For some absolute constant C,
F ≤ C E
Remarks: The conjecture extends to higher dimensions. If K is an r-dimensional simplicial complex that can be embedded into then the conjecture is that
Where is a constant depending on r. Hereis the number of i-dimensional faces of K. A stronger statement is that . The conjecture also extends to polyhedral complexes and more general form of complexes. In the conjecture ‘embed’ refers to a topological embedding.
Both PRIMALITY – deciding if an integer n is a prime and FACTORING – representing an integer as a product of primes, are algorithmic questions of great interest. I am curious to know what is known about these questions over general number fields. A major difference there is that there is know unique factorization to primes. Let me repeat here a question that I asked over TCS-stackexchange.
What is known about the computational complexity of factoring integers in general number fields? More specifically:
0. Over the integers we represent integers via their binary expansions. What is the analogous representations of integers in general number fields?
1. Is it known that primality over number fields is in P or BPP?
2. What are the best known algorithms for factoring over number fields? (Do the and the (apparently) algorithms extend from ?) Here, factoring refers to finding some representation of a number (represented by n bits) as a product of primes.
3. What is the complexity of finding all factorizations of an integer in a number field? Of counting how many distinct factorizations it has?
4. Over it is known that deciding if a given number has a factor in an interval is NP-hard. Over the ring of integers in number fields, can it be the case that finding if there is a prime factor whose norm is in a certain interval is already NP-hard?
Today is the general election day in Israel. This is an exciting day. For me election is about participation much more than it is about influence and I try not to miss it. This is why I regard the influence-based arguments for “why it is irrational to vote,” as unconvincing, and even a little silly. Influence vs participation was also the basis for my poll on “would you decide the election if you could.” I voted ‘no’ but about two-thirds of the participants voted yes. Four years ago I brought on this day the nice story of Achnai’s oven.