Quantum Computing in the NISQ era and beyond

John Preskill

Institute for Quantum Information and Matter and Walter Burke Institute for Theoretical Physics, California Institute of Technology, Pasadena CA 91125, USA

Noisy Intermediate-Scale Quantum (NISQ) technology will be available in the near future. Quantum computers with 50-100 qubits may be able to perform tasks which surpass the capabilities of today's classical digital computers, but noise in quantum gates will limit the size of quantum circuits that can be executed reliably. NISQ devices will be useful tools for exploring many-body quantum physics, and may have other useful applications, but the 100-qubit quantum computer will not change the world right away - we should regard it as a significant step toward the more powerful quantum technologies of the future. Quantum technologists should continue to strive for more accurate quantum gates and, eventually, fully fault-tolerant quantum computing.

► BibTeX data

► References

[1] P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Rev. 41, 303-332 (1999), 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, 10.1038/​s41534-017-0018-2.

[3] A. W. Harrow and A. Montanaro, Quantum computational supremacy, Nature 549, 203-209 (2017), 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, 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, 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, 10.1137/​S0097539796300933.

[8] R. B. Laughlin and D. Pines, The theory of everything, PNAS 97, 28-31 (2000), 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), 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, 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, 10.1038/​nature13171.

[16] D. J. Bernstein, J. Buchmann, E. Dahmen, editors, Post-Quantum Cryptography, Springer (2009), 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, 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, 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, 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, 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, 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, 10.1145/​990308.990310.

[27] Y. LeCun, Y. Bengio, and G. Hinton, Deep learning, Nature 521, 436-444 (2015), 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), 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, 10.1088/​2058-9565/​aa7877.

[30] T. Albash and D. A. Lidar, Adiabatic quantum computing, Rev. Mod. Phys. 90, 015002 (2018), arXiv:1611.04471, 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, 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, 10.1038/​nature23474.

[38] S. Aaronson, Read the fine print, Nature Physics 11, 291-293 (2015), 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, 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, 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, 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, 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, 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, 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), 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, 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, 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, 10.1038/​npjqi.2015.1.

► Cited by (beta)

[1] Pak Hong Leung, Kenneth R. Brown, "Entangling an arbitrary pair of qubits in a long ion crystal", Physical Review A 98, 032318 (2018).

[2] Adam Bouland, Bill Fefferman, Chinmay Nirkhe, Umesh Vazirani, "On the complexity and verification of quantum random circuit sampling", Nature Physics (2018).

[3] Daiqin Su, Krishna Kumar Sabapathy, Casey R. Myers, Haoyu Qi, Christian Weedbrook, Kamil Brádler, "Implementing quantum algorithms on temporal photonic cluster states", Physical Review A 98, 032316 (2018).

[4] Marek Pechal, Patricio Arrangoiz-Arriola, Amir H Safavi-Naeini, "Superconducting circuit quantum computing with nanomechanical resonators as storage", Quantum Science and Technology 4, 015006 (2018).

[5] Leonardo Novo, Shantanav Chakraborty, Masoud Mohseni, Yasser Omar, "Environment-assisted analog quantum search", Physical Review A 98, 022316 (2018).

[6] N. Klco, E. F. Dumitrescu, A. J. McCaskey, T. D. Morris, R. C. Pooser, M. Sanz, E. Solano, P. Lougovski, M. J. Savage, "Quantum-classical computation of Schwinger model dynamics using quantum computers", Physical Review A 98, 032331 (2018).

(The above data is from Crossref's cited-by service. Unfortunately not all publishers provide suitable and complete citation data so that some citing works or bibliographic details may be missing.)