Quantum Computing in the NISQ era and beyond

This article is the result of an uneasy compromise. I hope the content provides a useful overview for technically informed readers, but I’ve tried to minimize jargon and technical details which could be distracting or off-putting for a broader audience. I have not attempted to compile a comprehensive list of references; instead I have referred to just a few papers that amplify or clarify points I wanted to make, or that might provide instructive further reading. I apologize to many colleagues whose highly valuable contributions are not properly acknowledged here.

Let me now summarize the main points I’ve tried to convey.

Now is a privileged time in the history of science and technology, as we are witnessing the opening of the NISQ era (where NISQ = noisy intermediate-scale quantum). We’ll soon have the opportunity to experiment with NISQ technology to see what it can do. Perhaps NISQ will allow us to speed up the time to solution for problems of broad interest in the near future, but we don’t know yet whether that will happen.

We have some specific ideas of things we’d like to try, such as hybrid quantum-classical algorithms for solving optimization problems, both classical and quantum ones.

We can expect that, once we have quantum computers to experiment with, the development of quantum algorithms will accelerate. Perhaps new heuristics will be discovered for solving useful problems, although we may not be able to explain why these heuristics work so well, at least not right away.

Although we probably won’t be able to use full-blown quantum error correction to protect

NISQ-era devices from noise, we should design near-term quantum algorithms with noise resilience in mind. Clever design of noise-resilient algorithms may extend the computational power of NISQ devices.

Classical computers are especially bad at simulating the dynamics of highly entangled many-particle quantum systems; therefore quantum dynamics is a particularly promising arena where quantum computers may have a significant advantage over classical ones.

We should continue to focus on building quantum hardware with lower gate error rates.

Improved quantum gate accuracy will lower the overhead cost of quantum error correction when it is eventually implemented. In the nearer term, more accurate gates will allow us to execute larger quantum circuits, and so extend the power of NISQ technology.

NISQ is not likely to change the world all by itself. Instead, the primary goal for near-term quantum platforms should be to pave the way for bigger payoffs which will be realized by more advanced quantum devices down the road.

The truly transformative quantum technologies of the future are probably going to have to be fault tolerant, and because of the very hefty overhead cost of quantum error correction, the era of fault-tolerant quantum computing may still be rather distant. No one really knows how long it will take to get there. As the quantum community eagerly seizes the impending opportunity to experiment with NISQ devices, we must not lose sight of the essential longer-term goal: hastening the onset of the fault-tolerant era.

I’ve adopted a cautionary stance in these remarks, because I think we should face the onset of the NISQ era with well-grounded expectations. But please don’t misunderstand me — like many of my colleagues, I’m eagerly anticipating the discoveries that will ensue as the NISQ era unfolds over the next few years. Quantum technology is rife with exhilarating opportunities, and surely many rousing surprises lie ahead. But the challenges we face are still formidable. All quantumists should appreciate that our field can fulfill its potential only through sustained, inspired effort over decades. If we pay that price, the ultimate rewards will more than vindicate our efforts.

This article is based on a Keynote Address delivered at Quantum Computing for Business on 5 December 2017. I thank Matt Johnson for organizing this stimulating meeting and inviting me to participate. My remarks here have been influenced by discussions with many colleagues, too many to list. But I’ve especially benefited from insights due to Scott Aaronson, Sergio Boixo, Fernando Brandão, Elizabeth Crosson, Toby Cubitt, Eddie Farhi, Steve Flammia, David Gosset, Daniel Gottesman, Stephen Jordan, Jordan Kerenidis, Isaac Kim, Seth Lloyd, Shaun Maguire, Oskar Painter, David Poulin, Peter Shor, Brian Swingle, Matthias Troyer, Umesh Vazirani, and Thomas Vidick. Some of this work was done while I attended the 2017 program on Quantum Physics of Information at the Kavli Institute for Theoretical Physics (KITP). I gratefully acknowledge support from ARO, DOE, IARPA, NSF, and the Simons Foundation. The Institute for Quantum Information and Matter (IQIM) is an NSF Physics Frontiers Center.

[1] P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Rev. 41, 303-332 (1999), https://doi.org/10.1137/S0036144598347011.

[2] A. P. Lund, M. J. Bremner, and T. C. Ralph, Quantum sampling problems, BosonSampling, and quantum supremacy, npj Quantum Information 3: 15 (2017), arXiv:1702.03061, https://doi.org/10.1038/s41534-017-0018-2.

[3] A. W. Harrow and A. Montanaro, Quantum computational supremacy, Nature 549, 203-209 (2017), https://doi.org/10.1038/nature23458.

[4] S. P. Jordan, Quantum algorithm zoo, http://math.nist.gov/quantum/zoo/.

[5] A. Montanaro, Quantum algorithms: an overview, npj Quantum Information, 15023 (2016), arXiv:1511.04206, https://doi.org/10.1038/npjqi.2015.23.

[6] L. Grover, Quantum mechanics helps in searching for a needle in a haystack, Phys. Rev. Lett. 79, 325 (1997), arXiv:quant-ph/9706033, https://doi.org/10.1103/PhysRevLett.79.325.

[7] C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani, Strengths and weaknesses of quantum computing, SIAM J. Comput. 26, 1510-1523 (1997), arXiv:quant-ph/9701001, https://doi.org/10.1137/S0097539796300933.

[8] R. B. Laughlin and D. Pines, The theory of everything, PNAS 97, 28-31 (2000), https://doi.org/10.1073/pnas.97.1.28.

[9] R. P. Feynman, Simulating physics with computers, Int. J. Theor. Physics 21, 467-488 (1982).

[10] D. Gottesman, An introduction to quantum error correction and fault-tolerant quantum computation, Proceedings of Symposia in Applied Matthematics 68 (2010), arXiv:0904.2557.

[11] S. Boixo, S. V. Isakov, V. N. Smelyansky, R. Babbush, N. Ding, Z. Jiang, M. J.

Bremner, J. M. Martinis, and H. Neven, Characterizing quantum supremacy in near-term devices, Nature Physics 14, 595-600 (2018), arXiv:1608.00263 (2016), https://doi.org/10.1038/s41567-018-0124-x.

[12] S. Aaronson and L. Chen, Complexity-theoretic foundations of quantum supremacy experiments, arXiv:1612.05903 (2017).

[13] E. Pednault, J. A. Gunnels, G. Nannicini, L. Horesh, T. Magerlein, E. Solomonik, and R. Wisnieff, Breaking the 49-qubit barrier in the simulation of quantum circuits, arXiv:1710.05867 (2017).

[14] C. J. Ballance, T. P. Harty, N. M. Linke, M. A. Sepiol, and D. M. Lucas, High-fidelity quantum logic gates using trapped-ion hyperfine qubits, Phys. Rev. Lett. 117, 060504 (2016), arXiv:1512.04600, https://doi.org/10.1103/PhysRevLett.117.060504.

[15] R. Barends, J. Kelly, A. Megrant, A. Veitia, D. Sank, E. Jeffrey, T. C. White, J.

Mutus, A. G. Fowler, B. Campbell, Y. Chen, Z. Chen, B. Chiaro, A. Dunsworth, C. Neill, P. O’Malley, P. Roushan, A. Vainsencher, J. Wenner, A. N. Korotkov, A. N. Cleland, and J. M. Martinis, Superconducting quantum circuits at the surface code threshold for fault tolerance, Nature 508, 500-503 (2014), arXiv:1402.4848, https://doi.org/10.1038/nature13171.

[16] D. J. Bernstein, J. Buchmann, E. Dahmen, editors, Post-Quantum Cryptography, Springer (2009), https:/doi.org/10.1007/978-3-540-88702-7.

[17] R. Alléaume, C. Branciard, J. Bouda, T. Debuisschert, M. Dianati, N. Gisin, M.

Godfrey, P. Grangier, T. Länger, N. Lütkenhaus, C. Monyk, P. Painchault, M. Peev, A. Poppe, T. Pornin, J. Rarity, R. Renner, G. Ribordy, M. Riguidel, L. Salvail, A. Shields, H. Weinfurter, and A. Zeilinger, Using quantum key distribution for cryptographic purposes: a survey, Theoretical Computer Science 560, 62-81 (2014), arXiv:quant-ph/0701168, https://doi.org/10.1016/j.tcs.2014.09.018.

[18] S. Muralidharan, L. Li, J. Kim, N Lütkenhaus, M. D. Lukin, and L. Jiang, Efficient long distance quantum communication, Scientific Reports 6, 20463 (2016), arXiv:1509.08435, https://doi.org/10.1038/srep20463.

[19] P. Bierhorst, E. Knill, S. Glancy, Y. Zhang, A. Mink, S. Jordan, A. Rommal, Y.-K.

Liu, B. Christensen, S. W. Nam, M. J. Stevens, and L. K. Shalm, Experimentally generated randomness certified by the impossibility of superluminal signals, Nature 556, 223-226 (2018), arXiv:1803.06219, https://doi.org/10.1038/s41586-018-0019-0.

[20] Z. Brakerski, P. Christiano, U. Mahadev, U. Vazirani, and T. Vidick, Certifiable randomness from a single quantum device, arXiv:1804.00640 (2018).

[21] C. L. Degen, F. Reinhard, and P. Cappellaro, Quantum sensing, Rev. Mod. Phys. 89, 035002 (2017), arXiv:1611.04691, https://doi.org/10.1103/RevModPhys.89.035002.

[22] J. Preskill, Quantum computing and the entanglement frontier, 25th Solvay Conference on Physics (2011), arXiv:1203.5813.

[23] S. Khot, Hardness of approximation, Proceedings of the International Congress of

Mathematicians (2014).

[24] E. Farhi, J. Goldstone, and S. Gutmann, A quantum approximate optimization algorithm, arXiv:1411.4028 (2014).

[25] J. R. McClean, J. Romero, R. Babbush, and A. Aspuru-Guzik, The theory of variational hybrid quantum-classical algorithms, New J. Phys. 18, 023023 (2016), arXiv:1509.04279, https://doi.org/10.1038/ncomms5213.

[26] D. A. Spielman and S.-H. Teng, Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time, Journal of the ACM 51, 385-463 (2004), arXiv:cs/0111050, https://doi.org/10.1145/990308.990310.

[27] Y. LeCun, Y. Bengio, and G. Hinton, Deep learning, Nature 521, 436-444 (2015), https://doi.org/10.1038/nature14539.

[28] T. F. Rønnow, Z. Wang, J. Job, S. Boixo, S. V. Isakov, D. Wecker, J. M. Martinis, D. A. Lidar, and M. Troyer, Defining and detecting quantum speedup, Science 345, 420-424 (2014), https://doi.org/10.1126/science.1252319.

[29] S. Mandrà, H. G. Katzgraber, and C. Thomas, The pitfalls of planar spin-glass benchmarks: raising the bar for quantum annealers (again), Quantum Sci. Technol. 2, 038501 (2017), arXiv:1703.00622, https://doi.org/10.1088/2058-9565/aa7877.

[30] T. Albash and D. A. Lidar, Adiabatic quantum computing, Rev. Mod. Phys. 90, 015002 (2018), arXiv:1611.04471, https://doi.org/10.1103/RevModPhys.90.015002.

[31] D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd, and O. Regev, Adiabatic quantum computation is equivalent to standard quantum computation, SIAM Rev. 50, 755-787 (2008), arXiv:quant-ph/0405098.

[32] S. Bravyi, D. DiVincenzo, R. I. Oliveira, and B. M. Terhal, The complexity of stoquastic local Hamiltonian problems, Quant. Inf. Comp. 8, 0361-0385 (2008), arXiv:quant-ph/0606140.

[33] M. Jarret, S. P. Jordan, and B. Lackey, Adiabatic optimization versus diffusion Monte Carlo, Phys. Rev. A 94, 042318 (2016), arXiv:1607.03389, https://doi.org/10.1103/PhysRevA.94.042318.

[34] A. D. King, J. Carrasquilla, I. Ozfidan, J. Raymond, E. Andriyash, A. Berkley, M.

Reis, T. M. Lanting, R. Harris, G. Poulin-Lamarre, A. Yu. Smirnov, C. Rich, F. Altomare, P. Bunyk, J. Whittaker, L. Swenson, E. Hoskinson, Y. Sato, M. Volkmann, E. Ladizinsky, M. Johnson, J. Hilton, and M. H. Amin, Observation of topological phenomena in a programmable lattice of 1,800 qubits, arXiv:1803.02047 (2018).

[35] I. H. Kim, Noise-resilient preparation of quantum many-body ground states, arXiv:1703.00032 (2017).

[36] I. H. Kim and B. Swingle, Robust entanglement renormalization on a noisy quantum computer, arXiv:1711.07500 (2017).

[37] J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd, Quantum machine learning, Nature 549, 195-202 (2017), arXiv:1611.09347, https://doi.org/10.1038/nature23474.

[38] S. Aaronson, Read the fine print, Nature Physics 11, 291-293 (2015), https://doi.org/10.1038/nphys3272.

[39] X. Gao, Z. Zhang, and L. Duan, An efficient quantum algorithm for generative machine learning, arXiv:1711.02038 (2017).

[40] A. W. Harrow, A. Hassidim, and S. Lloyd, Quantum algorithm for linear systems of equations, Phys. Rev. Lett. 103, 150502 (2009), arXiv:0811.3171, https://doi.org/10.1103/PhysRevLett.103.150502.

[41] B. D. Clader, B. C. Jacobs, and C. R. Sprouse, Preconditioned quantum linear system algorithm, Phys. Rev. Lett. 110, 250504 (2013), arXiv:1301.2340, https://doi.org/10.1103/PhysRevLett.110.250504.

[42] A. Montanaro and S. Pallister, Quantum algorithms and the finite element method, Phys. Rev. A 93, 032324 (2016), arXiv:1512.05903, https://doi.org/10.1103/PhysRevA.93.032324.

[43] P. C. S. Costa, S. Jordan, and A. Ostrander, Quantum algorithm for simulating the wave equation, arXiv:1711.05394 (2017).

[44] I. Kerenidis and A. Prakash, Quantum recommendation systems, arXiv:1603.08675 (2016).

[45] E. Tang, A quantum-inspired classical algorithm for recommendation systems, Electronic Colloquium on Computational Complexity, TR18-12 (2018).

[46] F. G. S. L. Brandão and K. Svore, Quantum speed-ups for semidefinite programming, Proceedings of FOCS 2017, arXiv:1609.05537 (2017).

[47] F. G. S. L. Brandão, A. Kalev, T. Li, C. Y.-Y. Lin, K. M. Svore, and X. Wu, Exponential quantum speed-ups for semidefinite programming with applications to quantum learning, arXiv:1710,02581 (2017).

[48] M. Reiher, N. Wiebe, K. M. Svore, D. Wecker, and M. Troyer, Elucidating reaction mechanisms on quantum computers, PNAS 117, 7555-7560 (2017), arXiv:1605.03590, https://doi.org/10.1073/pnas.1619152114.

[49] D. Wecker, M. B. Hastings, N. Wiebe, B. K. Clark, C. Nayak, and M. Troyer, Solving strongly correlated electron models on a quantum computer, Phys. Rev. A 92, 062310 (2015), arXiv:1506.05135, https://doi.org/10.1103/PhysRevA.92.062318.

[50] J. Olson, Y. Cao, J. Romero, P. Johnson, P.-L. Dallaire-Demers, N. Sawaya, P. Narang, I. Kivlichan, M. Wasielewski, A. Aspuru-Guzik, Quantum information and computation for chemistry, NSF Workshop Report, arXiv:1706.05413 (2017).

[51] H. Bernien, S. Schwartz, A. Keesling, H. Levine, A. Omran, H. Pichler, S. Choi, A. S. Zibrov, M. Endres, M. Greiner, V Vuletić, and M. D. Lukin, Probing many-body dynamics on a 51-atom quantum simulator, Nature 551, 579-584 (2017), arXiv:1707.04344, https://doi.org/10.1038/nature24622.

[52] J. Zhang, G. Pagano, P. W. Hess, A. Kyprianidis, P. Becker, H. Kaplan, A. V.

Gorshkov, Z.-X. Gong, and C. Monroe, Observation of a many-body dynamical phase transition with a 53-qubit quantum simulator, arXiv:1708.01044 (2017), https://doi.org/10.1038/nature24654.

[53] E. T. Campbell, B. M. Terhal, and C. Vuillot, The steep road towards robust and universal quantum computation, arXiv:1612.07330 (2016).

[54] J. J. Wallman and J. Emerson, Noise tailoring for scalable quantum computation via randomized compiling, Phys. Rev. A 94, 052325 (2016), arXiv:1512:01098, https://doi.org/10.1103/PhysRevA.94.052325.

[55] J. Combes, C. Granade, C. Ferrie, and S. T. Flammia, Logical randomized benchmarking, arXiv:1702.03688 (2017).

[56] A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, Surface codes:

towards practical large-scale quantum computation, Phys. Rev. A 86, 032324 (2012), arXiv:1208.0928, https://doi.org/10.1103/PhysRevA.86.032324.

[57] S. Das Sarma, M. Freedman, and C. Nayak, Majorana zero modes and topological quantum computation, npj Quantum Information 1, 15001 (2015), arXiv:1501.02813, https://doi.org/10.1038/npjqi.2015.1.