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.

Share

► 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.
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, 10.1038/​s41534-017-0018-2.
https://doi.org/10.1038/s41534-017-0018-2
arXiv:1702.03061

[3] A. W. Harrow and A. Montanaro, Quantum computational supremacy, Nature 549, 203-209 (2017), 10.1038/​nature23458.
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, 10.1038/​npjqi.2015.23.
https://doi.org/10.1038/npjqi.2015.23
arXiv:1511.04206

[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.
https://doi.org/10.1103/PhysRevLett.79.325
arXiv:quant-ph/9706033

[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.
https://doi.org/10.1137/S0097539796300933
arXiv:quant-ph/9701001

[8] R. B. Laughlin and D. Pines, The theory of everything, PNAS 97, 28-31 (2000), 10.1073/​pnas.97.1.28.
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.
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.
https://doi.org/10.1038/s41567-018-0124-x
arXiv:1608.00263

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

[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).
arXiv:1710.05867

[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.
https://doi.org/10.1103/PhysRevLett.117.060504
arXiv:1512.04600

[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.
https://doi.org/10.1038/nature13171
arXiv:1402.4848

[16] D. J. Bernstein, J. Buchmann, E. Dahmen, editors, Post-Quantum Cryptography, Springer (2009), 10.1007/​978-3-540-88702-7.
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, 10.1016/​j.tcs.2014.09.018.
https://doi.org/10.1016/j.tcs.2014.09.018
arXiv:quant-ph/0701168

[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.
https://doi.org/10.1038/srep20463
arXiv:1509.08435

[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.
https://doi.org/10.1038/s41586-018-0019-0
arXiv:1803.06219

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

[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.
https://doi.org/10.1103/RevModPhys.89.035002
arXiv:1611.04691

[22] J. Preskill, Quantum computing and the entanglement frontier, 25th Solvay Conference on Physics (2011), arXiv:1203.5813.
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).
arXiv:1411.4028

[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.
https://doi.org/10.1038/ncomms5213
arXiv:1509.04279

[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.
https://doi.org/10.1145/990308.990310
arXiv:cs/0111050

[27] Y. LeCun, Y. Bengio, and G. Hinton, Deep learning, Nature 521, 436-444 (2015), 10.1038/​nature14539.
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), 10.1126/​science.1252319.
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, 10.1088/​2058-9565/​aa7877.
https://doi.org/10.1088/2058-9565/aa7877
arXiv:1703.00622

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

[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.
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.
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.
https://doi.org/10.1103/PhysRevA.94.042318
arXiv:1607.03389

[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).
arXiv:1803.02047

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

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

[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.
https://doi.org/10.1038/nature23474
arXiv:1611.09347

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

[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.
https://doi.org/10.1103/PhysRevLett.103.150502
arXiv:0811.3171

[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.
https://doi.org/10.1103/PhysRevLett.110.250504
arXiv:1301.2340

[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.
https://doi.org/10.1103/PhysRevA.93.032324
arXiv:1512.05903

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

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

[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).
arXiv:1609.05537

[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).
arXiv:1710.02581

[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.
https://doi.org/10.1073/pnas.1619152114
arXiv:1605.03590

[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.
https://doi.org/10.1103/PhysRevA.92.062318
arXiv:1506.05135

[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).
arXiv:1706.05413

[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.
https://doi.org/10.1038/nature24622
arXiv:1707.04344

[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.
https://doi.org/10.1038/nature24654
arXiv:1708.01044

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

[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.
https://doi.org/10.1103/PhysRevA.94.052325
arXiv:1512

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

[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.
https://doi.org/10.1103/PhysRevA.86.032324
arXiv:1208.0928

[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.
https://doi.org/10.1038/npjqi.2015.1
arXiv:1501.02813

► Cited by (beta)

[1] Leonardo Novo, Shantanav Chakraborty, Masoud Mohseni, Yasser Omar, "Environment-assisted analog quantum search", Physical Review A 98, 022316 (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.)