Is This A Quantum Computer?
Can we detect whether or not a computer is a quantum computer?
Meg Poitevint is a colleague who is not a theorist or a mathematician. She is one of our relatively new development officers here at Georgia Tech, in the College of Computing. She is now talking with our faculty to try and figure out what each of us does—this is invaluable to a development officer.
Today I want to try to answer one of her questions that she asked me a while ago over lunch: what is a quantum computer?
Meg is a great listener, a quick study, and has a breadth of knowledge that makes her job possible. I think anyone would be challenged in trying to understand—even at a high level—what faculty do. She does have a tiny tiny flaw: she is a fan of the Bulldogs. That is, the Bulldogs of the University of Georgia—her degree is from there. The “Dogs” are one of the main rivals to our great Yellow Jacket teams, so we must overlook this small indiscretion. We take sports seriously at Tech, and unfortunately, this is all-too-often a case where the bark is worse than the sting.
Ken and I, and our guest posters and commenters, have been talking a lot recently about whether or not it will be possible to build quantum computers in the near, distant, or even far future. It made me realize that Meg’s question is a pretty good one: just what are these things that we are taking about? And I realized that it was a real challenge to me: is there a way to explain what a quantum computer is without losing everyone who does not know a large amount of mathematics? Perhaps it is impossible, but as they say in England, I thought we would have a “go” at it.
The Machine Arrives
Imagine that someone sends Meg a package, and after she opens it, she sees that it contains a shiny new laptop, with the Apple logo and the name “qBook Pro.” A single sheet that comes with the machine says that it is a gift from Apple, and that it is a quantum computer. Meg turns it on, and soon has the standard Apple screen. Is it a quantum computer or not? How can she tell?
Meg calls me up and I come over to her office to look at the machine. She ask me: “so is this really a quantum computer? And what is that?” I tell her I have never seen this type of machine, but it could be a quantum computer. But I add that I believe there is really no way for us to tell. There is simply no way to tell from the outside, from just looking at the laptop, that it is a quantum-based machine.
Memory?
Ah, I think of one way I possibly could tell: perhaps the quantum computer can store huge amounts of data. If the qBook could store a vast amount of information, then would that show that it is a quantum computer? I open the hard-drive bay, and things look promising: the brandname says Quantum. Indeed the drive is identified as a Quantum Bigfoot drive—didn’t someone say that doubting quantum computers was like disproving Bigfoot?
Alas, the capacity stated on the drive is only 19.2 terabytes, which according to this chart is already underwhelming. Then I remember that, unfortunately, the storage of a quantum machine and a classical one are about the same. This is a consequence of quantum information theory—see here for the details.
So I tell Meg that we cannot use the size of its memory to prove it is a quantum computer. Too bad.
Quantum Benchmarking
Okay, you might say, what about using the computer? Can we run it on some problem to tell for sure that it is or is not a quantum computer? I claim the answer is still that there is no way to tell.
How about factoring?—of course a bunch of people suggest this. Can I run something on the machine that would help prove that it truly is a quantum machine? I look at the programs that are installed, and see that one is called {\tt factor}. This program once opened up says that it is an implementation of Peter Shor’s famous factoring algorithm. There is a box and I need only type a number and in a few seconds it will return the factors.
I try it one some simple numbers, then some larger numbers, and then some challenge numbers from the RSA page. It gets all of them right and gets them right in a few seconds. So it must be a quantum computer?
No. There is an alternative explanation. Perhaps the machine is running a classical factoring algorithm that is efficient. Many believe that such algorithms do not exist, and even while I believe they may exist, I do not think they would be practical. Yet we cannot rule out this possibility.
In a paper with Jin-Yi Cai, Bob Sedgewick, and Andy Yao, we considered general issues of proving that a computer actually carried out a claimed suite of operations. These issues are already substantial in the classical computing world, let alone quantum. I’m glad to notice a recent paper tackling the problem for cloud computing, for verifying performance guarantees in the cloud.
Go Inside
So the only way to tell for sure is to look inside the machine and take it apart. So how would that work? Say Meg asks me to call up Tom Conte, one of our top computer architecture experts. Tom looks at the machine and says that he could take it to his lab and take it apart. But he quickly adds it could destroy the machine, and even looking inside might not reveal anything meaningful. He says he is willing to try, but makes no promises. He takes the machine off
Open Problems
I think that if we are to talk about quantum computers it might be nice to have an objective method to tell if one is really legit. Yes the factoring test is not bad, but the it is not definite in my mind. So what can we do? Another problem with the factoring test is what if the qBook only can implement Shor for numbers that classic computers can also factor? Then what?
Back to Tom. He takes the machine apart and sees—big surprise—that it has sealed metal chips of various shapes and sizes. What does he do even if he is carefully forces one open? What is the fingerprint that shows that it really is a quantum computer? Five years ago, this article quoted a professor responding that “the easiest way to verify” claims by a certain company to have built a quantum computer is, “Peer-reviewed publication.”
Nice question Meg.
Thank God Meg got her quantum computer for free. Cause you are the worst quantum computer salesman ever.
Is this quantum computer salesmanship, or what? 🙂
What to do if you are a country that feels “left out” of the Facebook IPO
http://qbnets.wordpress.com/2012/02/19/what-to-do-if-you-are-a-country-that-feels-left-out-of-the-facebook-ipo/
Would Grover’s algorithm be of help here? Inverting a hash of size n in O(2^(n/2)) time instead of O(2^n) seems like it would be strong evidence of “quantumness”. It does assume P!=NP, but that’s a less strong claim than “Factoring is hard”.
With a base running time of 2^{n/2} it strikes us (Dick and I just talked by phone) as hard to find a niche of problem size n where this demo would convincingly rule out classical alternative methods from being under-the-hood. For factoring, too, he notes that the better constants on classical methods—even before assumptions like P!=NP—may push the overall demo time up very high before one can assure a concrete difference that proves quantum.
Also with Grover, the more one scales down the setting of the algorithm toward searching N different physical sites in O(sqrt{N}) time, the more one runs into my skepticism of how the standard quantum circuit model reckons time or effort. My thoughts on the last are much less concrete than these; I’m trying to use polynomial ideal theory to measure multi-partite entanglement in a way to argue that the effective width of an n-qubit circuit is n^2. I’m actually a Shor-believer, but my Grover/QC-model skepticism boils down to fearing that the actual effort required for Shor scales quadratically worse than claimed.
If the worst-case performance of the algorithm, across a wide variety of instances of varying sizes, looks like square root curve on a log(y)-linear(x) plot, that’s pretty strong evidence. It seems impossible to generate runtime proof from a single program run. But if you run it millions of times on a wide varieties of inputs, you get a curve (or a line).
If Grover’s algorithm actually works, and the computer is a quantum one, then you should see a square root curve after you take the log of the worst-case runtime. If not, then you should see a straight line. This is nice, because it’s even falsifiable! Once the initial data has been taken (and presumably the proper curve is seen), the hypothesis of a worst-case square-root curve can be destroyed by just a single problem instance that requires too much time to compute. You don’t need to have a quantum/classical race or anything like that. Just a hypothesized worst-case scenario that repeatedly fails to be falsified, and thus must be provisionally accepted.
Have you guys looked at Chaitin’s constant? He claims that this probability cannot be computed, yet some person in Australia, using a quantum computer prototype claims to have calculated the first few digits. This surprised Chaitin. I believe that N=NP can be shown to be true using a quantum computer. But I am just an amateur.
All one needs is a simulation that a quantum computer performs better than classical computer (Feynman’s idea)
Nice article.
Can we disassemble the quantum computer to observe its components, without destroying the entanglement, and getting instead a classical computer? Can we observe it while functioning, to confirm that the operations is performing are quantum, without causing it to decohere? It seems that indeed the only way to check is that you mention, to rely on peer review: the peers can check that the components function indeed as specified. But to my mind, the methods you already described seem like what a peer will do to verify the claims 🙂
One hope may be that there is something like a Bell-type inequality, which can be satisfied only by classical computers, and should be violated by quantum computers…
qbook pro!! love it!!
The question you are raising has been explicitly studied by Aharonov, Ben-Or, Eban, “Interactive Proofs For Quantum Computations (arXiv:0810.5375v2). Their solution is an interactive protocol between a BQP prover and a BPP verifier, which needs access to a small quantum register, though. Independently, Broadbent, Fitzsimons, Kashefi have proposed a protocol for Universal Blind Quantum Computation (arXiv:0807.4154v3) which can be interpreted to answer the same question as well. By moving to the multi-quantum-prover setting, the same authors have removed the need for any quantum communication between the classical verifier an the two, entangled quantum provers in their QMIP=MIP* result (arXiv:1004.1130).
Using this approach on two qBooks connected with a qEthernet link and two classical Ethernet links to your own PC, you can convince yourself that indeed one of the provers is executing a quantum circuit you instruct it to in a gate by gate fashion, or catch it if it tries to cheat on you.
Martin, how are two qBooks connected by a qEthernet link essentially different from one qBook? To put it another way, we diminish the requirement to accept on faith the quantum internal workings of the qBooks only by increasing the requirement to accept on faith the quantum internal workings of the qEthernet cable,
It seems (to me) that the most strict construction of Dick’s question requires that the validation of qBook “quantum-ness” be an explicit measure, which can be either deterministic or statistical, that in either case is computable with classical resources in P.
Well, of course having only a single classical verifier and a classical connection to the qBook would have been great, but has apparently been challenging to achieve. That’s why the authors relaxed the problem by first exploiting the power of entanglement to their advantage, and then used the power of questioning two provers independently to solve the problem of verifying these machines are really executing quantum gates as commanded. Improving upon that by eleminating the second quantum prover would of course be great, but is an open problem. But let us first appreciate what has been achieved so far: you can feed the two qBooks any quantum circuit, gate by gate, online, including measurements. You can run any BQP algorithm on the two qBooks as you wish. You will catch any attempt of cheating, i.e. other gates being applied than those you fed, with high probability. And finally, the blindness guarantee of the protocol ensures, that the two provers will not learn anything about the algorithm that you are feeding them (other than maybe it’s length). Thus, as they don’t know whether you are performing Shor’s algorithm or just a classical Quicksort, they cannot systematically cheat you by running some other, classical algorithm solving your problem instead. In this way, I think the question “How can we assure ourselves that a system is indeed performing quantum mechanically as specified?” has been given a beautiful answer by the above authors.
John, the main difference is that if necessary you can have the two computers space-like separated, ensuring that communication between the two systems is impossible within a given time window.
To this list I would also add work on quantum self-testing, such as Matt McKague’s work (arXiv:1010.1989 etc.). In my opinion, the open questions at the end of the post aren’t quite as open as the post suggests, though there are still many interesting problems in the area.
This comment is almost spot on.
If Apple sold an NP machine—perhaps P=NP but only Apple knows the algorithm—you would have no way of verifying it. Yes, you could give it 3SAT instances and check its answers, but maybe Apple has discovered a 1.00000001^n time algorithm, or maybe the machine is just really very fast. How could you tell?
A quantum computer is different. You can tell if Apple honestly sold you a quantum computer or not. This is amazing, a very cool feature of quantum mechanics that is impossible classically. I don’t know that it is especially useful, but theoretically it is surprising.
There are algorithms (eg. http://en.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa_algorithm ) for which quantum computers are provably faster than classical ones, so assuming your quantum computer implements one of those, should be easy to test.
We—in particular I—argued at the end of this post that if the classical algorithm is allowed to use linear extensions then there’s no difference. I regard this as a fair comparison insofar as quantum is implicitly using algebraic values other than 0 or 1, but you might come up with an implementation that proves your point and nixes my comparison.
See also the followup attempt to do this for Simon’s algorithm, which has a more-definitive separation proof than Deutsch-Jozsa. (As for why I was thinking “chocolate”, we haven’t had time yet to cover this paper by Karl Svozil.)
A quantum computer is a processor that can execute quantum algorithms at quantum speed. If you didn’t know what program your machine is executing, then I agree you could have doubts. But what if you’re the programmer? What if you’re the one who typed into the machine your own implementation of Shor’s algorithm? From the viewpoint of software development it’s not reasonable to suppose the machine could be running some unknown classical efficient factoring algorithm instead of your quantum one. Even with classical computers, at testing stage you have to make sure your machine is executing your own program and not somebody else’s. Otherwise software development would be impossible.
By the way, most computer users aren’t even aware that for the moment they’ve only been using “classical” computing devices. How could they make any distinction between their current computers and the future quantum ones… apart from some unusual buzz in the media about new methods for cryptography and credit card security?
Logan, the verification test that you suggested (run the Deutsch–Jozsa algorithm) requires quantum resources to implement (namely, the quantum oracle function under test). A strict construction of the GLL question asks for verification tests that accord with the everyday engineering meaning of “verification”, that is, deterministic or statistical tests of correctness that in either case are implemented entirely with classical resources in P.
The GLL question thus strictly construed is (as it seems to me) mathematically natural, physically fundamental, and even pragmatically essential.
Oh yeah … it strikes me that Dick Lipton showed both good technical judgment and outstanding collegiality (as usual) in ending his GLL essay by appreciating and thanking Meg Poitevint for raising these verification-related issues.
So please let me say too, “Nice question, Meg!”
John,
Thank you for this and all your kind comments
Couldn’t you just open up a shell and see that it is running catOS? And that every time you launch an executable you get a message back that says:
Maybe your process has started …
or an error:
Something might have gone wrong, or it might not have.
🙂
Without more research I would only offer this idea. One other avenue wouldn’t be to check how well the machine works, but how the machine fails. If one started with an idealized quantum computer, you have to assume it has resolved the issues of decoherence in order to work. So the natural question is how does one create instability in whatever quantum error correction process and what would one expect to see happen as decoherence takes hold. Then the next question is how is that different from failure modes in a classical computer. If those are substantial different in nature, for the classical computer, one would need to postulate that the clever classical quantum emulator has some hardware or software solution that allows it to mimic the failure modes of the quantum computer. So the trick would be to search the hardware and software for signs of a failure emulator.
Hey, the Yellow Jacket is *my* mascot! GT needs to back off, srsly…
http://en.wikipedia.org/wiki/Berkeley_High_School_(Berkeley,_California)
😉
If it turns out that deciding if a computer is really a quantum computer or a classical computer is difficult, i wonder if it will be useful to build one of them…
You just haven’t heard the end of the story:
Then Dick asked his grandson to get the qBook hooked up properly. So that was the problem! And Voila, the QC started simulating String Theory and folding proteins for him in a heart beat.
If BPP=BQP, and the laptop is a classical computer with a good emulator (preferably nearly linear time and space), then there’s not much you can do to distinguish this from a genuine quantum computer.
Alternatively, if it really is a quantum computer, but with a terrible OS that doesn’t let you access its powers, then you also wouldn’t be able to tell. 🙂
It’s much easier to test whether the ethernet is quantum, if you’ve first established that the computer is quantum. You could test Bell inequalities even if each quantum computer could store only a single qubit.
What I wrote about BPP=BQP is somewhat wrong.
The existence of a fast classical simulation of quantum computers would imply additional not-obviously-equivalent things, like the collapse of the polynomial hierarchy (see 1005.1407, 1011.3245, and even quant-ph/0205133).
And what we’d really want for a fake quantum computer is a simulation that recreates output probabilities, not merely one that solves the same set of languages.
The remarks on this topic bring to mind a familiar urban legend of physics, whose rich history Snopes.com traces back to 1958 (or even earlier):
In this same “barometer” vein, let’s ask what other transformational enterprises qBook technology (and the technologies necessary to design and manufacture qBooks) would enable the qApple Corporation to pursue.
———-
Therefore we open the qBook, fire-up a web browser, and by visiting the qApple website immediately discover that:
(1) qApple offers the world’s broadest array of mathematically natural and computationally efficient simulation software packages;
(2) Building upon capability (1), qApple is the world’s foremost vendor of quantum-limited telescopes, microscopes, and spectroscopes;
(3) By a roadmap that combines (1–2), qApple curates (for the entire planet) a unitary observational database that encompasses every variety of galaxy, star cluster, solar system, planet, biome, organism, cell, organelle, biomolecule, and genome;
(4) By a roadmap that combines (1–3), qApple dominates the world’s energy-collecting, water-purifying, chemical-separating, ore-processing, disease-diagnosing and drug-designing technologies;
(5) By a roadmap that combines (1–5), the quantum systems engineers at qApple are diligently working to synthesis the above capabilities into a comprehensive capability for directed regenerative healing in medicine.
———-
Thus, by “barometric reasoning” we have arrived at a common-sense insight: capabilities (1-5) surely are sufficient preconditions — and arguably even are technologically necessary preconditions — for qApple to ship working qBooks. And the roadmap associated to these five preconditions will transform our planet so profoundly that if qBooks are practicable at all, they foreseeably will be simply given away, as the least valuable of the immense contributions of QM/QC/QIT to the 21st century.
If these are the actual prospects of quantum computing, then I’m not so sure I’d like QC to be feasible. Too often, I find that the frontier between reality and virtuality is already much too narrow.
By the way, there seems to be some similarity between the questions “does P=NP?” and “is QC feasible?”. Both of them ask the question of the theoretical powers of computing. Therefore, I don’t believe that any of them will be answered soon.
Just a follow up on the earlier thought. When the quantum computer fails and decoheres the qubits pick a one or zero state. So it spits out some random number, so the question is whether that random number is a possible output state of the routine being run by the classical computer. One could imagine that a routine running on a classical computer would be restricted to certain smaller subspace of the full n-bit space, e.g. there are numbers it couldn’t output under any running of the routine barring having a “perfect” random number generator spit out a number on failure.
Here is something along the lines I’m thinking.
http://scienceblogs.com/pontiff/2008/01/contextuality_of_quantum_theor.php
This is a practical problem today. Apple doesn’t sell quantum computers, but D-Wave claims to. I’d guess the cost is on the order of magnitude of $1 million. Say you’re Mitt Romney, don’t really pay any taxes, and have a few extra bucks lying around. You could buy a D-Wave machine. You can’t factor with it, because it is not a general purpose computer. So what did you really buy?
That’s an open question. As quantum computers get better, it should get easier to answer. I’ll personally be convinced when RSA public keys are being factored regularly.
What do we want?
Evidence-based change!
When do we want it?
After peer review!
Seven years latter…
Apparently, IBM has built one. I imagine that a machine that can make distinctions should have a differentiated memory that would accumulate distinctions. We’ll see…