Quantum Computers Are…

Quantum computers are

  • Blue versions of classical computers [1] [2] [3][4]
  • Blue or grey abstract patterns [1] [2][3][4][5][6]
  • A bunch of connectors [1][2]
  • Blurred out chips [1]
  • What goes inside the dilution fridge [1][2][3]
  • Closed dilution fridges [1]
  • Part of a flag [1]
  • A button near the enter key [1]
  • Icy cold really big atoms [1]

Quantum computers are so many things (and no I will not add “all at once” to the end of this sentence)!  I’d be excited to hear about even more things that are quantum computers.

Quantum computers can work in principle

Gil Kalai has just posted on his blog a series of videos of his lectures entitled “why quantum computers cannot work.”  For those of us that have followed Gil’s position on this issue over the years, the content of the videos is not surprising. The surprising part is the superior production value relative to your typical videotaped lecture (at least for the first overview video).

I think the high gloss on these videos has the potential to sway low-information bystanders into thinking that there really is a debate about whether quantum computing is possible in principle. So let me be clear.

There is no debate! The expert consensus on the evidence is that large-scale quantum computation is possible in principle.

Quoting “expert consensus” like this is an appeal to authority, and my esteemed colleagues will rebuke me for not presenting the evidence. Aram has done an admirable job of presenting the evidence, but the unfortunate debate format distorts perception of the issue by creating the classic “two sides to a story” illusion. I think it’s best to be unequivocal to avoid misunderstanding.

The program that Gil lays forth is a speculative research agenda, devoid of any concrete microscopic physical predictions, and no physicist has investigated any of it because it is currently neither clear enough nor convincing enough. At the same time, it would be extremely interesting if it one day leads to a concrete conjectured model of physics in which quantum computers do not work. To make the ideas more credible, it would help to have a few-qubit model that is at least internally consistent, and even better, one that doesn’t contradict the dozens of on-going experiments. I genuinely hope that Gil or someone else can realize this thrilling possibility someday.

For now, though, the reality is that quantum computation continues to make exciting progress every year, both on theoretical and experimental levels, and we have every reason to believe that this steady progress will continue. Quantum theory firmly predicts (via the fault-tolerance threshold theorem) that large-scale quantum computation should be achievable if noise rates and correlations are low enough, and we are fast approaching the era where the experimentally achievable noise rates begin to touch the most optimistic threshold estimates. In parallel, the field continues to make contributions to other lines of research in high-energy physics, condensed matter, complexity theory, cryptography, signal processing, and many others. It’s an exciting time to be doing quantum physics.

And most importantly, we are open to being wrong. We all know what happens if you try to update your prior by conditioning on an outcome that had zero support. Gil and other quantum computing skeptics like Alicki play a vital role in helping us sharpen our arguments and remove any blind spots in our reasoning. But for now, the arguments against large-scale quantum computation are simply not convincing enough to draw more than an infinitesimal sliver of expert attention, and it’s likely to remain this way unless experimental progress starts to systematically falter or a concrete and consistent competing model of quantum noise is developed.

TQC 2014!

While many of us are just recovering from QIP, I want to mention that the submission deadline is looming for the conference TQC, which perhaps should be called TQCCC because its full name is Theory of Quantum Computation, Communication and Cryptography. Perhaps this isn’t done because it would make the conference seem too classical? But TQQQC wouldn’t work so well either. I digress.
The key thing I want to mention is the imminent 15 Feb submission deadline.
I also want to mention that TQC is continuing to stay ahead of the curve with its open-access author-keeps-copyright proceedings, and this year with some limited open reviewing (details here). I recently spoke to a doctor who complained that despite even her Harvard Medical affiliation, she couldn’t access many relevant journals online. While results of taxpayer-funded research on drug efficacy, new treatments and risk factors remain locked up, at least our community is ensuring that anyone wanting to work on the PPT bound entanglement conjecture will be able to catch up to the research frontier without having to pay $39.95 per article.
One nice feature about these proceedings is that if you later want to publish a longer version of your submission in a journal, then you will not face any barriers from TQC. I also want to explicitly address one concern that some have raised about TQC, which is that the published proceedings will prevent authors from publishing their work elsewhere. For many, the open access proceedings will be a welcome departure from the usual exploitative policies of not only commercial publishers like Elsevier, but also the academic societies like ACM and IEEE. But I know that others will say “I’m happy to sign your petitions, but at the end of the day, I still want to submit my result to PRL” and who am I to argue with this?
So I want to stress that submitting to TQC does not prevent submitting your results elsewhere, e.g. to PRL. If you publish one version in TQC and a substantially different version (i.e. with substantial new material) in PRL, then not only is TQC fine with it, but it is compatible with APS policy which I am quoting here:

Similar exceptions [to the prohibition against double publishing] are generally made for work disclosed earlier in abbreviated or preliminary form in published conference proceedings. In all such cases, however, authors should be certain that the paper submitted to the archival
journal does not contain verbatim text, identical figures or tables, or other copyrighted materials which were part of the earlier publications, without providing a copy of written permission from the copyright holder. [ed: TQC doesn’t require copyright transfer, because it’s not run by people who want to exploit you, so you’re all set here] The paper must also contain a substantial body of new material that was not included in the prior disclosure. Earlier relevant published material should, of course, always be clearly referenced in the new submission.

I cannot help but mention that even this document (the “APS Policy on Prior Disclosure”) is behind a paywall and will cost you $25 if your library doesn’t subscribe. But if you really want to support this machine and submit to PRL or anywhere else (and enjoy another round of refereeing), TQC will not get in your way.
Part of what makes this easy is TQC’s civilized copyright policy (i.e. you keep it). By contrast, Thomas and Umesh had a more difficult, though eventually resolved, situation when combining STOC/FOCS with Nature.

Two Cultures in One of the Cultures

This makes no senseA long time ago in a mental universe far far away I gave a talk to a theory seminar about quantum algorithms. An excerpt from the abstract:

Quantum computers can outperform their classical brethren at a variety of algorithmic tasks….[yadda yadda yadaa deleted]… This talk will assume no prior knowledge of quantum theory…

The other day I was looking at recent or forthcoming interesting quantum talks and I stumbled upon one by a living pontiff:

In this talk, I’ll describe connections between the unique games conjecture (or more precisely, the closely relatedly problem of small-set expansion) and the quantum separability problem… [amazing stuff deleted]…The talk will not assume any knowledge of quantum mechanics, or for that matter, of the unique games conjecture or the Lasserre hierarchy….

And another for a talk to kick off a program at the Simons institute on Hamiltonian complexity (looks totally fantastic, wish I could be a fly on the wall at that one!):

The title of this talk is the name of a program being hosted this semester at the Simons Institute for the Theory of Computing….[description of field of Hamiltonian complexity deleted…] No prior knowledge of quantum mechanics or quantum computation will be assumed.

Talks are tricky. Tailoring your talk to your audience is probably one of the trickier sub-trickinesses of giving a talk. But remind me again, why are we apologizing to theoretical computer scientists / mathematicians (which are likely the audiences for the three talks I linked to) for their ignorance of quantum theory? Imagine theoretical computer science talks coming along with a disclaimer, “no prior knowledge of the PCP theorem is assumed”, “no prior knowledge of polynomial-time approximation schemes is assumed”, etc. Why is it still considered necessary, decades after Shor’s algorithm and error correction showed that quantum computing is indeed a fascinating and important idea in computer science, to apologize to an audience for a large gap in their basic knowledge of the universe?
As a counter argument, I’d love to hear from a non-quantum computing person who was swayed to attend a talk because it said that no prior knowledge of quantum theory is assumed. Has that ever worked? (Or similar claims of a cross cultural prereq swaying you to bravely go where none of your kind has gone before.)

Portrait of an Academic at a Midlife Crisis

Citations are the currency of academia. But the currency of your heart is another thing altogether. With apologies to my co-authors, here is a plot of my paper citations versus my own subjective rating of the paper. Hover over the circles to see the paper title, citations per year, and score. Click to see the actual paper. (I’ve only included papers that appear on the arxiv.)

If I were an economist I suppose at this point I would fit a sloping line through the data and claim victory. But being a lowly software developer, its more interesting to me to give a more anecdotal treatment of the data.

  • The paper that I love the most has, as of today, exactly zero citations! Why do I love that paper? Not because it’s practical (far from it.) Not because it proves things to an absolute T (just ask the beloved referees of that paper.) But I love it because it says there is the possibility that there exists a material that quantum computes in a most peculiar manner. In particular the paper argues that it is possible to have devices where: quantum information starts on one side of device, you turn on a field over the device, and “bam!” the quantum information is now on the other side of the material with a quantum circuit applied to it. How f’in cool is that! I think its just wonderful, and had I stuck around the hallowed halls, I probably would still be yelling about how cool it is, much to the dismay of my friends and colleagues (especially those for which the use of the word adiabatic causes their brain to go spazo!)
  • Three papers I was lucky enough to be involved in as a graduate student, wherein we showed how exchange interactions alone could quantum compute, have generated lots of citations. But the citations correlate poorly with my score. Why? Because it’s my score! Haha! In particular the paper I love the most out of this series is not the best written, most deep, practical, or highly cited. It’s the paper where we first showed that exchange alone was universal for quantum computing. The construction in the paper has large warts on it, but it was the paper where I think I first participated in a process where I felt like we knew something about the possibilities of building a quantum computer that others had not quite exactly thought of. And that feeling is wonderful and is why that paper has such a high subjective score.
  • It’s hard not to look this decades worth of theory papers and be dismayed about how far they are from real implementation. I think that is why I like Coherence-preserving quantum bit and Adiabatic Quantum Teleportation. Both of these are super simple and always felt like if I could just get an experimentalist drunk enough excited enough they might try implement that damn thing. The first shows a way to make a qubit that should be more robust to errors because its ground state is in an error detecting state. The second shows a way to get quantum information to move between three qubits using a simple adiabatic procedure related to quantum teleportation. I still hope someday to see these executed on a functioning quantum computer, and I wonder how I’d feel about them should that happen.

When I Was Young, I Thought It Would Be Different….

When I was in graduate school (back before the earth cooled) I remember thinking the following thoughts:

  1. Quantum computing is a new field filled with two types of people: young people dumb enough to not know they weren’t supposed to be studying quantum computing, and old, tenured people who understood that tenure meant that they could work on what interested them, even when their colleagues thought they were crazy.
  2. Younger people are less likely to have overt biases against woman.  By this kind of bias I mean that like the math professor at Caltech who told one of my friends that woman were bad at spatial reasoning (a.k.a. Jerks).  Maybe these youngsters even had less hidden bias?
  3. Maybe, then, because the field was new, quantum computing would be a discipline in which the proportion of woman was higher than the typical rates of their parent disciplines, physics and in computer science?

In retrospect, like most of the things I have thought in my life, this line of reasoning was naive.
Reading Why Are There So Few Women In Science in the New York Times reminded me about these thoughts of my halcyon youth, and made me dig through the last few QIP conferences to get one snapshot (note that I just say one, internet comment troll) of the state of woman in the quantum computing (theory) world:

Year Speakers Woman Speakers Percent
2013 41 1 2.4
2012 43 2 4.7
2011 40 3 7.5
2010 39 4 10.2
2009 40 1 2.5

Personally, it’s hard to read these numbers and not feel a little disheartened.

Reflections on the Discord Bubble

The following is a guest post by Marco Piani.
A couple of months ago Steve wrote a post on “the discord bubble“. Let me try to provide a summary of his post and of his thoughts.
There have been too many works, too often of insufficient quality either technically or conceptually (“pointless” works in Steve’s words) about a property of quantum systems and correlations—the so-called quantum discord—that has not been proven yet to be key in our understanding of nature or of the `inner workings’ of quantum information processing. That is, such flurry of activity does not appear to be justified and is rather due to “hype”; most importantly, the product of such activity is way too often of questionable quality. Steve goes on to suggest that the bubble needs to be put under control, so that we would go down to a reasonable rate of publications on the subject, hopefully of higher average quality. In order to assess such quality, Steve proposes some rules of thumb—check them out in Steve’s post—to be applied hopefully by the authors themselves. In his words, Steve’s intention was

“not to trash the subject as intrinsically uninteresting; rather, [he wanted] to highlight the epidemic of pointless papers that constitute the discord bubble. [He hoped] that thinning the herd will increase the quality of the results in the field and decrease the hype surrounding it, because it has really gotten completely out of control.”

While I found Steve’s post essentially to the point and I furthermore highly appreciated his invitation to highlight in the comments good research on quantum discord—because there is good research on the topic—I feel that there is room for more reflection and discussion, in particular within—but of course not limited to—the community working on discord-related problems. To start it, I would like to express some of my own opinions.

Is there a bubble? What is it at its origin?

Yes, there is a bubble. Yes, there is too much hype. Yes, there are too many papers on the subject that are of questionable quality.
On one hand, the subfield of the `general quantumness of correlations’—as I like to think of discord and related concepts—still lacks a killer application to justify the present level of activity. The explosion of interest in the subfield was in a good part due to hints that such quantumness could help explain the quantum advantage in some noisy models of (limited) quantum computation. Such hints, to my knowledge, remain just hints; that is, too little to justify so many papers. We are still searching for a task/protocol that convincingly highlights discord or similar related properties as `resources’  or `the key’ in a general enough scenario—see this related post by Valerio Scarani. On the other hand, as Steve pointed out, many papers on discord are characterized by a low scientific merit, technically and/or conceptually.
I believe that the “discord bubble” is due to a combination of several factors, which have all come together to create the `perfect bubble’. Some are:
1) we live in a “publish or perish” (academic) world: if hype starts to be generated regarding a topic, many researchers will flock to that topic in the hope to score well in the number and kind of publications—high-impact journals—and the corresponding citations they are bound to get;
2) when there is a `new’ topic (like `discord’ with respect to the good ol’ `entanglement’) the technical and conceptual threshold to contribute new results is lower; on the other hand, quantum information is by now a mature field and new exciting results in `traditional’ theoretical topics—quantum Shannon theory, quantum error correction, quantum computation, … —require a high level of expertise and skills;
3) some form of `confirmation bias’: positive statements on the value and significance of new and old results on the topic are easily accepted and perpetuated, especially in light of 1) and 2).
Let me stress that these factors are mostly independent of the topic itself—discord. I am pretty sure that other fields of science have their own bubbles.

Is it worth working on discord and related issues?

Quantum information processing aims at exploiting quantum features to provide us with new, powerful means to manipulate information. Reaching this goal requires the best possible understanding of such features.
More specifically for our case, there are quantum features that 1) are proper of bi- and multi-partite systems (i.e., they do not have a real correspondent for single systems)  and 2) do not reduce to entanglement, e.g, they can be present also in the absence of entanglement.  For example, one of these properties is related to the celebrated no-cloning theorem; another one is the unavoidable disturbance introduced by local measurements. In this sense there is a `general quantumness of correlations’, which, for the above reasons, I believe is worth investigating.
Of course, an argument like “[PROPERTY] could be useful, so we should study it” is not  enough, if not substantiated. There should be some concrete evidence and some convincing perspective of such usefulness in order to motivate the related investment of resources. I think that what we know about the general quantumness of correlations, although not enough to justify the number of papers dealing with it, satisfies these requirements, at least partially. More clearly:
We have concrete evidence that the general quantumness of correlations is a useful concept to consider.
Such usefulness goes from foundations—e.g., addressing the measurement problem and the emergence of classicality—to the alternative take on the no-cloning theorem mentioned above, to the study of quantum effects in the `locking’ of classical correlations in quantum information theory.
On the other hand:
We have not yet found a way to think about and exploit the general quantumness of correlations that makes such quantumness worthy of the central stage of quantum information processing, or of the title of `resource’.
As mentioned above, the protocols so far designed that pinpoint discord as the relevant `resource’ at play can be considered contrived. More generally, I doubt that discord will ever achieve a status of resource similar to entanglement. I rather believe that, for example, discord is—with the risk of sounding like I am trying to be witty—something that makes it possible to make something else impossible. For example, discord makes it impossible to access `in a classical way’  part of the information content of correlations.
All in all, I do believe that the general quantumness of correlations will further prove its usefulness, both as a conceptual tool and as concrete property present in distributed systems. What we have to remember is that such usefulness is not well established and that most of the work on the subject should still go in the direction of clarifying the value and applicability of the concept rather than, e.g., calculating discord in all sorts of physical systems.
Let me add that I consider the study of the general quantumness of correlations also as an attempt to think about the quantum from a different/larger perspective—different/larger with respect to what was previously done. In my case, thinking in terms of the `general quantumness of correlations’ has helped me, for example, to better understand entanglement itself.

What should people who work or consider working on discord do? What about the rest of the quantum information community?

The effort worth investing—as individual researchers, as a scientific (in particular, quantum information) community, and as a society (e.g., in terms of funding)—in the study of the general quantumness of correlations is not easy to determine. This actually holds in general, for essentially any research subject. What is worrisome about a bubble, is that it can reduce the efficiency of the procedures in place—in particular the peer-review process—to shape the activity of the community, to reallocate its resources, and to induce researchers to adopt a good practice. [We actually know that the peer-review process, in particular in the standard form associated to publication in journals, does not work perfectly in general.]  As personal experience goes, I have often rejected low-quality papers on discord only to see them published in another journal. So it is important to recognize the presence of a bubble and bring the problem to the attention of the community, so that extra care can be taken in assessing the value of papers, both in terms of correctness and relevance. While I endorse Steve’s rules of thumb to assess the quality of papers related to discord, I would like to address the problem of the discord bubble with a list of suggestions mostly comprising general good practices.
So, to the people working/interested in working on discord:
a) re-evaluate why you are working on the topic. A useful exercise it that of imagining explaining to someone who is NOT already working on discord why he should be interested in investigating the subject. If whatever reason you provide is based on previous results in the field, make sure that you have checked the source at a sufficient level of detail to be sure that those results—and in particular any related strong claim—would be convincing for him, and, most importantly, that they are convincing for you;
b) be aware of the large body of work that already exists in quantum information processing: what you think is new and exciting may well be already known (either published, or easy to see and part of the `folklore’);
c) analyze critically your work and that of the others, both as author and as referee: cite only literature that is significant and relevant to your paper and reject papers that do not provide substantial advance in neither understanding nor applications;
d) focus on providing more—and possibly conclusive—evidence that the study of the quantumness of correlations is justified: we need `killer applications’ and `killer concepts’;
e) entanglement theory has been a very fruitful field of study because entanglement is a fundamental concept and it can be understood/analyzed as a resource in a reasonable, operationally justified framework—that of distant labs, where the quantum operations allowed are only local, at most coordinated by classical communication. Trying to mimic successful stories might be a good idea, but there are dangers involved. Let us avoid creating the Bizzarro version of entanglement.
To the rest of the quantum information community:
Be critical and open-minded at the same time.
While complaining about the existence of a discord bubble is more than reasonable and, from my point of view, quite welcome, attacking the study of discord per se is unjustified. Please challenge whoever makes claims that are too strong, question observations and calculations that you judge irrelevant, push people who work on discord to meet the highest standards in international research, reject papers when they do not meet such standards. But please do not dismiss a talk or a paper just because it deals with discord; evaluate it only on the basis of its specific scientific merit.  Furthermore, if you feel like it, you can ponder for some minutes on questions like “Is there anything quantum about a distributed quantum state that is not solely due to entanglement?”, and “Can we make use of it?”.

On the fractal nature of bubbles

The best results of recognizing that there is a `discord bubble’ and of taking corresponding action—maybe on the lines suggested above—would be, on one hand, to improve the research activity on discord, and, on the other hand, to avoid the risk that the subject and the people working on it acquire a bad reputation.
Let me mention that there are scientists who think that research on quantum computation is itself a bubble—see this post by Scott Aaronson. Is this further proof that bubbles can have a fractal structure? Of course the `accusation’ of being bubbles is at different levels for discord and quantum information, and not just in the sense of the `fractal level’. The criticism towards quantum computing is mostly about its realizability, while discord, although a useful conceptual tool, has not convincingly been proven to be a `resource’, even in theory.  Nonetheless, there is something in common about the two accusations of being a bubble: hype—again. Indeed, Scott writes about the accusations of the quantum computing skeptic M. I. Dyakonov:

“Dyakonov fumes about how popular articles, funding agency reports, and so forth have overhyped progress in quantum computing, leaving the conditions out of theorems and presenting incremental advances as breakthroughs.  Here I sadly agree.”

So, let me add a point to the above list of suggestions:
f) try to reduce—or at least do not contribute to—the hype.
This will have the effect of making the topic of discord less attractive for people whose work will not actually improve the standing of the topic, and improve its reputation within the quantum information community, potentially attracting good researchers.
The above-mentioned post by Scott is also notable for having started a high-quality discussion in the comments section on whether quantum computing deserves the accusation of being a bubble. It would be great to have a similar discussion on discord in the comments below. I expressed already my personal opinion: we are in front of a discord bubble, but there is merit in studying the general quantumness of correlations. I would be particularly happy to have a discussion on whether—and why—my opinion is too harsh or too mild, and to receive, as Steve already asked in his post, motivated suggestions about works that should survive a `pop’ of the discord bubble.

Simple circuit "factors" arbitrarily large numbers

Last Thursday, at the QIP rump session in Beijing, John Smolin described recent work with Graeme Smith and Alex Vargo [SSV] showing that arbitrarily large numbers N can be factored by using this constant-sized quantum circuit

to implement a compiled version of Shor’s algorithm.  The key to SSV’s breathtaking improvement is to choose a base for exponentiation, a, such that the function a^x bmod N is periodic with period 2.  (This kind of  simplification—using a base with a short period such as 2, 3, or 4—has in fact been used in all experimental demonstrations of Shor’s algorithm that we know of).  SSV  go on to show that an a with period 2 exists for every product of distinct primes N=pq, and therefore that the circuit above can be used to factor any such number, however large.  The problem, of course, is that in order to find a 2-periodic base a, one needs to know the factorization of N. After pointing this out, and pedantically complaining that any process requiring the answer to be known in advance ought not to be called compilation, the authors forge boldly on and note that their circuit can be simplified even further to a classical fair coin toss, giving a successful factorization whenever it is iterated sufficiently many times to obtain both a Head and a Tail among the outcomes (like having enough kids to have both a girl and a boy).   Using a penny and two different US quarters, they successfully factor 15, RSA-768, and a 20,000-bit number of their own invention by this method, and announce plans for implementing the full circuit above on state-of-the art superconducting hardware.  When I asked the authors of SSV what led them into this line of research, they said they noticed that the number of qubits used to do Shor demonstrations has been decreasing over time, even as the number being factored increased from 15 to 21, and they wanted to understand why.  Alas news travels faster than understanding—there have already been inquiries as to whether SSV might provide a practical way of factoring without the difficulty and expense of building a large-scale quantum computer.

QIP 2013 accepted talks, travel grants

The accepted talk list for QIP 2013 is now online. Thomas Vidick has done a great job of breaking the list into categories and posting links to papers: see here. He missed only one that I’m aware of: Kamil Michnicki’s paper on stabilizer codes with power law energy barriers is indeed online at arXiv:1208.3496. Here are Thomas’s categories, together with the number of talks in each category.

  • Ground states of local Hamiltonians (4)
  • Cryptography (3)
  • Nonlocality (6)
  • Topological computing and error-correcting codes (4)
  • Algorithms and query complexity (6)
  • Information Theory (9)
  • Complexity (2)
  • Thermodynamics (2)

Other categorizations are also possible, and one important emerging trend (for some years now) is the way that the “information theory” has broadened far beyond quantum Shannon theory. To indulge in a little self-promotion, my paper 1210.6367 with Brandao is an example of how information-theoretic tools can be usefully applied to many contexts that do not involve sending messages at optimal rates.
It would be fascinating to see how these categories have evolved over the years. A cynic might say that our community is fad-driven, but instead I that the evolution in QIP topics represents our field working to find its identity and relevance.
On another note, travel grants are available to students and postdocs who want to attend QIP, thanks to funding from the NSF and other organizations. You don’t have to have a talk there, but being an active researcher in quantum information is a plus. Beware that the deadline is November 15 and this is also the deadline for reference letters from advisors.
So apply now!