Wrestling with two quantum Merlins

UPDATE: A bug has been found in the proof, the paper has been withdrawn.

—
It has long been known, that if an all-powerful quantum wizard called Merlin can convince a quantum verifier called Arthur of some statement by sending a single quantum message, then a classical computer by itself can compute the same result in exponential time . The game changes, though, if two independent quantum Merlins send a message to Arthur. It was not clear if in this case a classical computer can simulate this situation in less than double exponential time !

Today I have shown, that indeed even the latter situation can be simulated by a classical computer in at most exponential time. Eventhough the two scenarios are still not known to be equivalent in terms of certain other complexity measures, at least for the practical purpose of simulation on a classical computer in the shortest possible time, they are – up to our best current knowledge – of comparable difficulty.

In particular, the important Pure State N-Representability problem in quantum chemistry is now known to be solvable in at most exponential time.

For details, please find my paper here: http://arxiv.org/abs/1510.08447

Advertisement

New quantum paper released!

It took me a while, but finally my first quantum paper has been released to the arXiv! And it only took a little while longer to get it pubished in Phys. Rev. Lett. 108, 110502 (2012).

The paper introduces a novel method to efficiently construct a quite general class of quantum states on a quantum computer. This class of quantum states is known as Projected Entangled Pair States (PEPS) and is conjectured to represent ground states of gapped Hamiltonians faithfully while having a polynomial-sized classical description. Our algorithm can reconstruct such states from their description whenever they satisfy certain additional properties (injectivity, gapped parent Hamiltonian) which are considered quite general and not too restrictive. It is clear that some restrictions must be placed on the subset of efficiently constructible PEPS as otherwise this would imply the computational power of solving PP-complete problems, which is well beyond the conjectured capabilities of a quantum computer. Our result essentially says, that all reasonably defined PEPS are also physically realizable.

Another interesting point about our result is the fact that the PEPS are classically described as the (partial) contraction of a tensor network. A tensor is simply a multi-dimensional array of complex numbers. A tensor with just one index is a vector, a tensor with two indices is a matrix, but in general tensor can have an arbitrary number of indices. A tensor network is simply a graph, where a tensor is attached to each vertex with as many indices as there are edges coming into the vertex, and where each edge can be labeled with a number from 1 to up to the dimension of the associated tensor index (of course tensor index dimensions at the two ends of the edge must match up).

A PEPS is a special class of tensor networks, where each vertex has an open index, called the physical index, representing the state of the local quantum system represented by this vertex. The quantum state represented by the PEPS is simply the contraction of (sum over) all closed edges of the tensor network.

Contracting a tensor network as described above is a quite generic primitive that can be used to model many kinds of exponential sums over products of variables. Such sums-of-products are seen for example in the partition function of systems in statistical physica, quantum spin systems of course, the classical simulation of quantum computers, and all kinds of counting problems. In general, such problems have been shown to be #P-complete and are thus considered intractable for classical computers. Interestingly, our paper shows that a specific subset of these partition functions can be represented as a quantum state and can be constructed efficiently on a quantum computer. It would be interesting to understand, if any new counting problem or other classical problem not known to be tractable classically (but also not shown #P-complete) could be solved by constructing the respective quantum state and measuring some non-trivial observable. This would exhibit a new type of quantum algorithm yielding a speedup over classical computers. First steps in this direction have been taken by Arad and Landau, and van den Nest, et al., who give efficient contractions of certain classical partition functions on quantum computers. These results, though, do not rely on explicitly constructing a quantum state implied by the partition function but use other methods to approximate this contraction value using a quantum computer. In this sense, our result provides a new, generic tool to these approaches, eventhough we have not really shown its efficiveness in this context yet.

I’ve had a lot of fun working out this result jointly with Frank and Kristan. It uses quite a few nice linear algebra tricks, such as Jordan’s Lemma on the interaction of two subspaces and the fact that the injectivity property of PEPS implies it is the unique ground state of an easily constructed parent Hamiltonian.

First Flight of Boeing 787!

Today the Boeing 787 took its first flight! It’s nice to see projects come to completion one has been working on for a while. After the Airbus A380 that’s the second one for me to watch that I’ve been contributing to a little. Tonight we had a nice little first-flight party at TTTech.

TTTech has been cooperating with Hamilton-Sundstrand, the supplier of the Engine Power Generation System. For the past years TTTech has been involved in implementing the Primary and Secondary Power Distribution Network using TTTech’s TTP, the Time-Triggered Protocol. My part of the job was to lead the team of software engineers developing and designing the embedded run-time software used to interface TTP with the customer’s application. This software is now certified to design assurance level A (the highest level of criticality) according to the RTCA DO-178B  standard for airborne software certification. Furthermore my (former) team has develop quite sophisticated test equipment for lab and flight-test use. In addition to the software aspects I’ve been involved with,  TTTech has also contributed in the development of powerful scheduling and configuration tools, the implementation and environmental tests of the TTP physical layer and, of course, the design, development, and certification of the TTP controller AS8202NF, which is also flying on the Airbus A380, Aermacchi M346, and Lockheed-Martin’s F-16 Block E aircraft.

Looking forward to the launch of NASA’s Ares-I rocket carrying the Orion Crew Exploration Vehicle in 2014!

Quantum Computing PhD

As some of you might already know, on October 1st I finally started to focus on my PhD in (roughly speaking) Quantum  Computing by taking a sabbatical leave from TTTech in order to do research at Frank Verstraete’s Quantum Information Theory group at University of Vienna. For the next 6 months I will finally have time to sit down and think through more deeply a couple of ideas I have in this area and for crystallizing them into papers. I will have the same opportunity another time in a year from now in order to continue where I left off.  I’m hoping to create the essential content of my PhD thesis within this sabbatical, even though it seems unrealistic to expect completion of the thesis entirely within that time frame. Nevertheless, now I have time to work full-time on what has been an enjoyable hobby and spare-time activity so far.

Many of my computer scientist friends may wonder how it is possible to skip over to an entirely different field, doing a PhD in physics without having a physics undergraduate degree. Whether this is really going to work out I don’t even know myself for sure, but I can tell you the story as it has developed so far: Back in the undergraduate days, probably in 2002, I got interested in quantum computing for the first time. At this time Prof. Jozef Gruska was teaching a one-semester guest class  on Quantum Computing at TU Vienna, where I was studying Computer Science. I was curious about that class,  yet frightened to take it by the mere thought of a computer scientist having to master quantum mechanics in a semester just in order to complete that class. So I was too scared to actually take that class. But what I did do was buying Gruska’s 1999 book on Quantum Computing, which was the first ever text book in this area covering all the basics in one place. So I had this book sitting on my book shelf for years and every now and then I came back to it for curiosity. But most of the time I was simply overwhelmed by the strange physicist notation of and and tensor products () when jumping right to the gems of the area: Shor’s and Grover’s algorithms. But once I figured out, that Quantum Computing is essentially Linear Algebra and the bra and ket symbols are merely short-hand notation for row and column vectors representing states, while state transitions are performed just by matrix multiplications, most mysteries resolved in delight. I thought “Hey, that’s just Linear Algebra! Well, I can do that!” and after mastering the basics, a quite lively and active research area was open and accessible to me. What I enjoyed most was that another Computer Science area I have alway been fond of was central to this area: Complexity Theory ( and related questions). Naturally, one of the most intriguing question of this area was: How powerful are quantum computers? Can a quantum computer perform certain tasks significantly more efficient than any classical computer? (for the experts: ?) Furthermore, with the language of Quantum Complexity Theory, it was now possible to formally ask the question how hard it is to compute the ground state of quantum systems using a quantum computer, which essentially boils down to a quantum version of the question, namely ? Given Quantum Mechanics as humanity’s best description of the physical world, what are the hardest problems that can be possibly solved within Nature and what kind of problems will for ever stay out of reach?

Gruska’s book is a good introduction to the field, but the presentation is still quite biased towards physicists rather than computer scientists. The current standard text book in this area is Nielsen and Chuang, which is almost “physics-free” and probably even better accessible to computer scientists than Gruska. All of this I found extremely exciting, so I started to devote much of my spare time to learn everything about this area and at some point in time I started to ask myself, whether I shouldn’t channel this efforts into something with fruitful outcome, like a PhD. During that time I started reading very many papers in this area, some of them (co-)authored by Frank Verstraete, who is a well-known researcher in this field. At one point in time, I observed that Frank is now with University of Vienna, having been appointed as full professor in 2007. So I figured out it might be a good idea to get in contact with him to discuss some of my ideas, which I did in early 2009. Since that loose collaboration seemed to work out excitingly for both of us, Frank accepted me as a PhD student and so I inscribed at University of Vienna for the PhD programme in Physics in summer semester 2009. Of course, with a Computer Science undergraduate degree this was not entirely straightforward, but in the end I got accepted conditioned on taking an extra Quantum Optics lab course including the associated theory course in addition to the classes I need to take for the PhD programme itself. So I took the theory class by Markus Arndt and Phillip Walter, which I very much enjoyed and which I did on vacation time of my regular job at TTTech. But the lab itself is blocked into one entire month of full-time lab work. How could I align that with my full-time job at TTTech? And more generally, how could I align doing a PhD with my job at all? So I was looking for funding opportunities, being aware of the fact that any option would mean a severe pay cut. Nevertheless, I was willing to accept that, for the enjoyment and intellectual excitement to be expected. Finally, the most straightforward funding opportunity to support a PhD without quitting my job turned out to be the sabbatical programme (Bildungskarenz) offered by the government of Austria: If your employer accepts, you are free to take off 1 year within a time-frame of 4 years for (provable) personal education while being redeemed some part of your last net salary. As this was acceptable to me, I agreed with TTTech to split the sabbatical into 2 times 6 months starting October 1st. Splitting it in a more fine-grained way (e.g. part-time job/part-time PhD) would have been the ideal solution, but unfortunately this was not compatible with the legal requirements of the sabbatical programme offered by the government.

Now I’m here at the university, working with Frank and his small and brilliant team on exciting Quantum Algorithms! I hope you enjoyed reading my story so far! Be sure, I will keep you informed.

The CERN Petition

A few days ago Austria’s minister for science and research Johannes Hahn has had the bright idea of optimizing Austria’s scientific spending by pulling out of CERN, the flagship institution of European fundamental research. In the end, this would save Austria about 16 M€, which is approximately the amount of money out of the national budget supplied to the Austrian public railway system in 4 days, or 2€ tax money per Austrian per year. If you feel hard pressed to follow the soundness of Hahn’s logic, please join me in signing the following petition:

http://sos.teilchen.at/petition/

Let’s hope the world-wide web – an unremarkable CERN spin-off – helps stopping Hahn from commiting this “historic blunder” as some have called it, and let’s hope Hahn will never require the services of MedAustron, the medical neutron source, currenlty being built in co-operation with CERN in Wiener Neustadt (50km south of Vienna).

Update: Johannes Hahn has finally retracted his plans to exit CERN.  Thanks for your support!

Quantum Workshops in Vienna 2009

Throughout this year there are two very nice workshops with relation to quantum computing (in a broad sense) scheduled to be held here in Vienna:

• 2nd Vienna Symposium on the Foundations of Modern Physics 2009 (June 11-14 2009)
  This conference is really a theoretical physics conference. With regards to quantum computing this will be a venue to meet with well-known QC researchers such as Scott Aaronson and Bill Wootters.
• Workshop on Quantum Computation and Quantum Spin Systems (August 10-14 2009)
  This workshop is hosted by Frank Verstraete and Barbara Terhal (et al.) and features the who-is-who in quantum computing as speakers.

Hats

Another interesting funding opportunity, this time with relation to Formal Methods. Checkout my About page, if you’re not yet familiar with Formal Methods!

Vienna PhD School of Informatics

I just came across a new PhD funding opprtunity that I would like to share with my readers. As reported here and here, TU Vienna is launching a new, funded 3-year PhD programme for computer scientists. As reported by TU officials, the programme is currently at the conceptual stage and due to launch in April 2009 with a funding period of 2009-2011. The City of Vienna is sponsoring 15 female students within this larger programme with 700 k€. So this looks like 46 k€ per student in total, or 15 k€/yr over 3 years, or 1300 EUR per months (gross) – well, seems to be a medicore funding level and hardly convincing for Masters already working in the industry, but better than nothing. Let’s wait for further conditions on that funding (age, gender, etc.), once they got it through.

Update 2009-05-19: I just came across the standard funding levels 2009 for PhD students paid by the Austrian FWF (Fund for Scientific Research).