PERSPECTIVE ARTICLE
published: 30 May 2014
doi: 10.3389/fphy.2014.00033
How to test the “quantumness” of a quantum computer?
Alexandre M. Zagoskin 1,2*, Evgeni Il’ichev 3, Miroslav Grajcar 4, Joseph J. Betouras 1 and Franco Nori 2,5
1 Department of Physics, Loughborough University, Loughborough, UK
2 Center for Emergent Matter Science, RIKEN, Saitama, Japan
3 Quantum Detection, Leibnitz Institute of Photonic Technology, Jena, Germany
4 Department of Experimental Physics, Comenius University, Bratislava, Slovakia
5 Department of Physics, University of Michigan, Ann Arbor, MI, USA
Edited by:Jacob Biamonte, ISI Foundation,Italy
Reviewed by:Vasileios Basios, Université Libre deBruxelles, BelgiumJames Daniel Whitﬁeld, ViennaCenter for Quantum Science andTechnology, AustriaJosé Geraldo Peixoto De Faria,Centro Federal de EducaçãoTecnológica de Minas Gerais, Brazil
*Correspondence:Alexandre M. Zagoskin, Departmentof Physics, LoughboroughUniversity, Loughborough LE11 3TU,UKe-mail: a.zagoskin@lboro.ac.uk
Recent devices, using hundreds of superconducting quantum bits, claim to performquantum computing. However, it is not an easy task to determine and quantify thedegree of quantum coherence and control used by these devices. Namely, it is a difﬁculttask to know with certainty whether or not a given device (e.g., the D-Wave One orD-Wave Two) is a quantum computer. Such a veriﬁcation of quantum computing wouldbe more accessible if we already had some kind of working quantum computer, tobe able to compare the outputs of these various computing devices. Moreover, theveriﬁcation process itself could strongly depend on whether the tested device is astandard (gate-based) or, e.g., an adiabatic quantum computer. Here we do not propose atechnical solution to this quantum-computing “veriﬁcation problem,” but rather outline theproblem in a way which would help both specialists and non-experts to see the scale ofthis difﬁcult task, and indicate some possible paths toward its solution.
Keywords: quantum computing, adiabatic quantum computing, quantum coherence, quantum annealing, D-WaveSystems, quantum simulations, quantum speed-up
Suppose we are given a black box and told that this is a quantumcomputer. How do we test if it is capable of performing quan-tum computing? The standard approach would be to run a seriesof tests of few-qubit operations, and compare the outputs withresults obtained using a standard (classical) computer simulat-ing the quantum evolution. This is possible for small-size systems,likely comprising less than 40–50 qubits, given the current capa-bilities and fundamental limitations of classical computers (due tothe exponential growth of computing resources needed to modellarge quantum systems [11]. But what if the system size is larger?Another challenging task would be to ﬁnd out how to change thedesign of the “black-box computer” to improve its performance.Namely, if the black box computer is not working as a quantumcomputer, how to ﬁnd this out and how to ﬁx the problem?
Now we are facing a similar situation. The development of an
“adiabatic quantum annealer” by D- Wave Systems Inc. over thelast few years did produce reactions ranging from excitement toskepticism [2–9]. Considerable interest was generated by:
(1) the demonstration of quantum annealing in an 8-qubit
register of the prototype processor [10];
(2) the sale of a 128-qubit quantum annealer “D-Wave One”
to Lockheed Martin and its installation at the University ofSouthern California (2011), and its upgrade to a 512-qubit“D-Wave Two” (2013);
(3) the subsequent evidence of quantum annealing in the work-
ing 108 qubits of this device [11, 12];
(4) the realization of a quantum adiabatic algorithm on a nom-
inally 512-qubit (439 qubits operational) device “D-WaveTwo” outperforming at least some classical algorithms [13]and losing to some other classical algorithms [14];
(5) the May 2013 decision by NASA, Google and the Universities
Space Research Association to purchase a “D-Wave Two” tobe installed at their common Quantum Artiﬁcial IntelligenceLab at NASA’s Ames Research Centre [15];
(6) the evaluation of small Ramsey numbers using the “D-Wave
One” device [16].
Questions were raised concerning the relative speed of theD-Wave processors compared to classical optimization algo-rithms [7] and the quantum character of their evolution (see [17],the response [18] and the reply to the response [19]). While theformer question is crucial for information science, the latter one ismore important from the point of view of physics. We believe thatresolving it would drastically improve the current status of theﬁeld, which we ﬁnd unsatisfactory in several important respects.The very fundamental impossibility of an efﬁcient simulation,with classical means, of large enough quantum systems [1], whichprovides the justiﬁcation for the quest for quantum computing,may prevent us from developing quantum computers, unless bet-ter classical approaches toward their design and evaluation arefound.
CURRENT SITUATIONThe device (“D-Wave One”), tested in Boixo et al. [11, 12], con-sisted of 128 (108 of which were operational) Nb- based super-conducting ﬂux qubits (see, e.g., [20], Ch.2), arranged in blocksof 8, with selective tunable couplings. This particular design useddc SQUIDs in place of Josephson junctions, which allowed toﬁne-tune the qubit parameters by changing the magnetic ﬂuxesthrough the control loops. The amplitude and sign of the cou-plings between the qubits could also be tuned in a similar way
www.frontiersin.orgMay 2014 | Volume 2 | Article 33 | 1
PHYSICS
Zagoskin et al.How to test the “quantumness” of a quantum computer?
[21]. The qubits formed a lattice, which can be modeled by anetwork of Ising spins with randomly chosen interactions.The goal of the experiment [11, 12] was to ﬁnd the statisticsof the device by determining the random spin glass ground stateand comparing the results with the algorithms based on simulatedclassical and quantum annealing (SCA and SQA, respectively).The surprising result was that the operation of D-Wave One pro-duced a bimodal statistical distribution of success probabilities,corresponding to clearly distinct groups of “easy” and “hard”problems, similar to the one produced by SQA, but drasticallydifferent from SCA. In addition, they detected strong positive cor-relations of the success probabilities at different instances betweenthe D-Wave One processor and SQA. As pointed out in Smolinand Smith [17], the bimodality itself was not sufﬁcient to claimthe evidence for quantum annealing, as it could be reproducedby semi-classical spin models. Nevertheless, the absence of cor-relations between semi-classical models and D-Wave One madea strong case in favor of quantum behavior, demonstrating someessential features of quantum annealing [11, 12, 18]. The aboveresults are surprising, since the adiabatic evolution time of theprocessor (5–15 µs) greatly exceeded the decoherence time ofeach separate qubit (∼100 ns) and therefore of the processor asa whole. More recent data obtained on a larger D-Wave Two pro-cessor seems to indicate the quantum character of the evolution[22] and show an improvement due to the use of a quantum errorcorrection scheme [23].
QUANTUM COHERENCE AND ENTANGLEMENTWhile the critical importance of maintaining quantum coher-ence for gate-based quantum computing is ﬁrmly established,the question of its role for universal adiabatic quantum comput-ing, and its more limited versions (such as quantum optimizationor approximate adiabatic quantum computing) is being debated(see, e.g., [24, 25]). Quantum coherence is certainly necessary, buton what scale, and for how long?There is a point of view, according to which the existence ofentangled energy eigenstates is not only necessary, but it may evenbe sufﬁcient, for at least a limited operation of an adiabatic quan-tum computer. This was guiding some early efforts in this ﬁeld[26–28]. Due to the fact that the tested structures consisted of asmall number of superconducting ﬂux qubits, it was possible toestablish the existence of such eigenstates by the direct modelingof the quantum evolution of the system, and its comparison withthe experimental data was possible. But for a general system thequestion remains: multiqubit entanglement is certainly necessary,but on what scale, and for how long?
SCALING WITH THE NUMBER OF QUBITSThe situation becomes qualitatively different with the current andfuture generations of multiqubit processors. The simulation ofthe full 108-qubit system in the quantum limit was not attempted,and therefore a direct investigation of the role of entangled energyeigenstates could not be undertaken. (Difﬁculties of such sim-ulation were already explicit in Johnson et al. [10], where onlya single 8-qubit register was investigated.) It was only possibleto make a conjecture [18] that the better correlations betweenthe behavior of the D-Wave processor and the SQA (compared
to semi-classical spin models) was due to the fact that entan-gled energy eigenstates were used in the SQA calculations, butnot in the semiclassical models. The exact classical optimizationalgorithms used in Boixo et al. [11, 12], as well as generic approx-imate algorithms, will take impractically long time to run for512 qubits. For the speciﬁc structure of the D-Wave One proces-sor, it is expected that the simulated annealer algorithms (bothclassical and quantum) will scale exponentially (as exp[a√
N])with the number N of qubits, the same as exact solvers [11, 12].Therefore, it is likely that their usefulness for establishing thequantum character of their evolution in the planned devices,with several thousand qubits, is questionable. However, since SQAdoes not simulate the actual quantum behavior of the system,its results are of questionable relevance for the prediction of theability of a given large-scale quantum qubit array to demonstratequantum behavior at a given level of environmental and intrinsicdecoherence, dispersion of parameters, etc.
THE PROBLEM AND POSSIBLE SOLUTIONSThe looming impossibility to predict the behavior of any bigenough quantum processor (adiabatic, gate-based, etc) and evento test it for “quantumness” using classical tools, is the elephantin the room, and it may effectively restrict any further progress.Even taking the optimistic view, that quantum computing is notfundamentally restricted (by, e.g., limits on the size of systemscapable of demonstrating quantum behavior [29]), it is realistic toexpect, based on the current state of art, that a quantum proces-sor capable of simulating itself accurately and quickly enough tobe useful, will contain signiﬁcantly more qubits than the currentor prospective D-Wave machines.A recent analysis of the perspectives of superconducting cir-cuits as a platform for universal quantum computation [30]stressed the very high price of implementing quantum error cor-rection (necessary for the gate-based quantum computing) or“surface code” quantum computing [31], which runs to hundredsor thousands of physical qubits per a logical qubit. Devoret andSchoelkopf [30] speculates that large quantum processors shouldperhaps rely on a modular approach (when the operation andfunctionality of unit modules can be separately tested and char-acterized), or on some “hardware—speciﬁc shortcuts” (like usingnon-linear oscillators instead of qubits as a basis for supercon-ducting quantum computing). However, these speculations maybe overly optimistic. In order to use quantum parallelism oneshould entangle a few dozen logical qubits, which is only possi-ble if all, or a signiﬁcant fraction, of the unit elements are in aquantum coherent state for some minimum period of time. Itwas recently demonstrated experimentally [32], that the quan-tumness of a gate-based quantum computer can be veriﬁed usinga smaller quantum device. It would be very interesting to knowwhether this approach can be extended to quantum annealers orused to estimate the performance of such devices. But so far, wecannot avoid the need to estimate and evaluate the behavior oflarge, essentially quantum systems with classical means, in orderto develop a useful quantum computer.The problem pertains for quantum annealers, universal quan-tum computers (gate-based or otherwise), adiabatic quantumcomputers, quantum simulators, and even for simpler artiﬁcial
Frontiers in Physics | Interdisciplinary PhysicsMay 2014 | Volume 2 | Article 33 | 2
Zagoskin et al.How to test the “quantumness” of a quantum computer?
quantum structures, such as quantum metamaterials, whoseproperties are essentially determined by quantum correlationsand entanglement within large collections of artiﬁcial atomsinteracting with the electromagnetic ﬁeld.Nevertheless, we believe that this problem can be solved. Thiswill ﬁrst require developing a better set of theoretical tools. A sys-tem of qubits is, after all, a quantum many-body system, whichmay be amenable to the approaches which worked so well inmany applications to condensed matter physics and statisticalmechanics. If, for the moment, we restrict the ﬁeld to quan-tum annealers, then the existing theoretical formalism must beextended to efﬁciently include the two essential features of thisproblem: its essentially non-equilibrium, transitional character,and the importance of quantum coherence (e.g., following [33]).It would be desirable to have an efﬁcient method of establishingthe probability, that the observed set of runs of a large-enoughquantum annealer cannot be reduced to classical physics, and ofestimating the performance of such a device based solely on thedevice parameters. This would not require to classically simulatea particular run of the device and could use an appropriate set ofvariables characterizing the system at the macroscopic level, e.g.,its non-trivial adiabatic invariants.Such set of theoretical tools will be useful not just for appli-cations to quantum computing, but in a wider ﬁeld of quantumengineering and second-generation quantum technologies [34].Moreover, it may prove indispensable when addressing problemssuch as quantum simulations [35, 36], quantum-to-classical tran-sition in open systems [37] and the challenging new ﬁeld ofquantum biology [38]. However, the whole area cannot developuntil the proper guidelines are obtained on what kind of sys-tems and under what conditions macroscopic quantum behavioris likely to be realized, and what should be the signs of thisrealization. How to evaluate the “quantumness” of a black boxis a challenging problem, which requires a concerted approach,appropriate for such a fundamental task.
ACKNOWLEDGMENTSEvgeniIl’ichevacknowledgessupportfromtheEU7thFramework Programme collaborative project iQIT. MiroslavGrajcar was supported by the Slovak Research and DevelopmentAgency under the contracts APVV-0515-10, DO7RP-0032-11,and European Community’s Seventh Framework Programme(FP7/2007-2013) under Grant No. 270843(iQIT). Joseph J.Betouras was supported by EPSRC through grant EP/H049797/1.Franco Nori is partially supported by the RIKEN iTHES Project,MURI Center for Dynamic Magneto-Optics, and a Grant-in-Aidfor Scientiﬁc Research (S).
REFERENCES1. Feynman R. Simulating physics with computers. Int J Theor Phys. (1982)21:467. doi: 10.1007/BF026501792. Hardy Q. Google buys a quantum computer. New York Times (2013 8 May).3. Jones N. D-Wave’s Quantum Computer Courts Controversy. Available onlineat:http://www.scientiﬁcamerican.com/article/d-waves-quantum-computer-courts-controversy/ (2013 19 June).4. Cartwright J. Has a quantum computer solved the ‘party problem’?Physicsworld.com. (2013 September).5. Smith G, and Smolin J. Viewpoint: putting “Quantumness” to the test. Physics(2013) 6:105. doi: 10.1103/Physics.6.105
6. Guizzo E. “Loser: D-wave does not quantum compute,” in IEEE Spectrum(2009 December).7. Aaronson S. D-wave: Truth Finally Starts to Emerge. (Blog Entry). Availableonline at: http://www.scottaaronson.com/blog/?p=1400 (2013).8. Aron J. Google’s Quantum Computer Flunks Landmark Speed Test. Availableonline at: http://www.newscientist.com/article/dn24882-googles-quantum-computer-ﬂunks-landmark-speed-test.html?full=true#.UvF28fvurvY(2014January).9. Grossman L. The quantum quest for a revolutionary computer. Time 28 (2014February).10. Johnson M, Amin M, Gildert S, Lanting T, Hamze F, Dickson N. et al.Quantum annealing with manufactured spins. Nature (2011) 473:194. doi:10.1038/nature1001211. Boixo S, Albash T, Spedalieri F, Chancellor N, Lidar D. Experimental signa-ture of programmable quantum annealing. Nat Comm. (2013) 4:3067. doi:10.1038/ncomms306712. Boixo S, Roennow T, Isakov S, Wang Z, Wecker D, Lidar D, et al. Evidencefor quantum annealing with more than one hundred qubits. Nat Phys. (2014)10:218. doi: 10.1038/nphys290013. McGeoch C, Wang C. “Experimental evaluation of an adiabiatic quantumsystem for combinatorial optimization,” in CF’13. Ischia (2013 May 14–16).14. Roennow T, Wang Z, Job J, Boixo S, Isakov S, Wecker D, et al. Deﬁning anddetecting quantum speedup. arXiv:1401.2910 (2014).15. Johnston H. D-Wave sells second quantum computer - this time to NASA. PhysWorld (2013) 26:9.16. Bian Z, Chudak F, Macready W, Clark L, Gaitan F. Experimental deter-mination of ramsey numbers. Phys Rev Lett. (2013) 111:130505. doi:10.1103/PhysRevLett.111.13050517. Smolin J, Smith G. Classical signature of quantum annealing. arXiv:1305.4904(2013).18. Wang L, Roennow T, Boixo S, Isakov S, Wang Z, Wecker D, et al. Comment on:“Classical signature of quantum annealing.” arXiv:1305.5837 (2013).19. Shin S, Smith G, Smolin J, Vazirani U. How “Quantum” is the D-Wavemachine? arXiv:1401.7087 (2014).20. Zagoskin A. Quantum Engineering: Theory and Design of QuantumCoherent Structures. Cambridge: Cambridge University Press (2011). doi:10.1017/CBO978051184415721. Harris R, Johansson J, Berkley A, Johnson M, Lanting T, Han S, et al.Experimental demonstration of a robust and scalable ﬂux qubit. Phys Rev B(2010) 81:134510. doi: 10.1103/PhysRevB.81.13451022. Vinci W, Albash T, Mishra A, Warburton P, Lidar D. Distinguishingclassical and quantum models for the D-Wave device. arXiv:1403.4228(2014).23. PudenzK,AlbashT,LidarD.Error-correctedquantumannealingwith hundreds of qubits. Nat Comm. (2014) 5:3243. doi: 10.1038/ncomms424324. Sarandy M, Lidar D. Adiabatic quantum computation in open systems. PhysRev Lett. (2005) 95:250503. doi: 10.1103/PhysRevLett.95.25050325. Amin M, Truncik C, Averin D. Role of single-qubit decoherence timein adiabatic quantum computation. Phys Rev A (2009) 80:022303. doi:10.1103/PhysRevA.80.02230326. Izmalkov A, Grajcar M, Il’ichev E, Wagner T, Meyer HG, Smirnov A. et al.Evidence for entangled states of two coupled ﬂux qubits. Phys Rev Lett. (2004)93:049902. doi: 10.1103/PhysRevLett.93.04990227. Grajcar M, Izmalkov A, Il’ichev E. Possible implementation of adiabatic quan-tum algorithm with superconducting ﬂux qubits. Phys Rev B (2005) 71:144501.doi: 10.1103/PhysRevB.71.14450128. vanderPloegS,IzmalkovA,GrajcarM,HuebnerU,LinzenS,Uchaikin ST, et al. Adiabatic quantum computation with ﬂux qubits,ﬁrst experimental results. IEEE Trans Appl Supercond. (2007) 17:113. doi:10.1109/TASC.2007.89815629. Penrose R. The Emperor’s New Mind. Oxford: Oxford University Press (1999).30. Devoret M, Schoelkopf, R. superconducting circuits for quantum information:an outlook. Science (2013) 339:1169. doi: 10.1126/science.123193031. Fowler A, Mariantoni M, Martinis J, Cleland A. Surface codes: towards prac-tical large-scale quantum computation. Phys Rev A (2012) 2012:032324. doi:10.1103/PhysRevA.86.03232432. Barz S, Fitzsimons J, Kasheﬁ E, Walther P. Experimental veriﬁcation of quan-tum computation. Nat Phys. (2013) 9:727. doi: 10.1038/nphys2763
www.frontiersin.orgMay 2014 | Volume 2 | Article 33 | 3
Zagoskin et al.How to test the “quantumness” of a quantum computer?
33. Zagoskin A, Savel’ev S, Nori F. Modeling an adiabatic quantum computer
via an exact map to a gas of particles. Phys Rev Lett. (2007) 98:120503. doi:10.1103/PhysRevLett.98.120503
34. Georgescu I, Nori F. Quantum technologies: an old new story. Physics World
17 (2012).
35. Wecker D, Bauer B, Clark B, Hastings M, Troyer M. Can quantum chemistry
be performed on a small quantum computer? arXiv:1312.1695 (2013).
36. Georgescu I, Ashhab S, Nori F. Quantum simulation. Rev Mod Phys. (2014)
86:153. doi: 10.1103/RevModPhys.86.153
37. Schlosshauer M. Decoherence: and the Quantum-To-Classical Transition.
Berlin-Heidelberg: Springer (2007).
38. Lambert N, Chen Y, Chen Y, Li C, Chen G, Nori, F. Quantum biology. Nat
Phys. (2013) 9:10. doi: 10.1038/nphys2474
Conﬂict of Interest Statement: Alexandre M. Zagoskin is a co-founder andshareholder of D-Wave Systems Inc. Evgeni Il’ichev and Miroslav Grajcar werecollaborating with D-Wave Systems Inc. in the past. Neither of them collaborated
with D-Wave Systems Inc. after 2005. The authors declare that the research wasconducted in the absence of any commercial or ﬁnancial relationships that couldbe construed as a potential conﬂict of interest.
Received: 18 February 2014; paper pending published: 23 March 2014; accepted: 09May 2014; published online: 30 May 2014.Citation: Zagoskin AM, Il’ichev E, Grajcar M, Betouras JJ and Nori F (2014) Howto test the “quantumness” of a quantum computer? Front. Physics 2:33. doi: 10.3389/fphy.2014.00033This article was submitted to Interdisciplinary Physics, a section of the journalFrontiers in Physics.Copyright © 2014 Zagoskin, Il’ichev, Grajcar, Betouras and Nori. This is an open-access article distributed under the terms of the Creative Commons AttributionLicense (CC BY). The use, distribution or reproduction in other forums is permitted,provided the original author(s) or licensor are credited and that the original publica-tion in this journal is cited, in accordance with accepted academic practice. No use,distribution or reproduction is permitted which does not comply with these terms.
Frontiers in Physics | Interdisciplinary PhysicsMay 2014 | Volume 2 | Article 33 | 4