Practical quantum advantage in quantum simulation

  • Ladd, T. D. et al. Quantum computers. Nature 464, 45–53 (2010).

    CAS 
    PubMed 
    Article 
    ADS 

    Google Scholar 

  • Grumbling, E. & Horowitz, M. (eds) Quantum Computing: Progress and Prospects (National Academies Press, 2019).

  • Deutsch, I. H. Harnessing the power of the second quantum revolution. PRX Quantum 1, 020101 (2020).

    Article 

    Google Scholar 

  • Nielsen, M. & Chuang, I. Quantum Computation and Quantum Information 10th anniversary edn (Cambridge Univ. Press, 2010).

  • Feynman, R. P. Simulating physics with computers. Int. J. Theor. Phys. 21, 467–488 (1982).

    MathSciNet 
    Article 

    Google Scholar 

  • Montanaro, A. Quantum algorithms: an overview. npj Quantum Inf. 2, 15023 (2016).

    Article 
    ADS 

    Google Scholar 

  • Aramon, M. et al. Physics-inspired optimization for quadratic unconstrained problems using a digital annealer. Front. Phys. 7, 48 (2019).

  • Gibney, E. Hello quantum world! Google publishes landmark quantum supremacy claim. Nature 574, 461–462 (2019).

    CAS 
    PubMed 
    Article 
    ADS 

    Google Scholar 

  • Arute, F. et al. Quantum supremacy using a programmable superconducting processor. Nature 574, 505–510 (2019). This article reports the demonstration of a quantum advantage with verification for a mathematical problem designed to test the quantum hardware.

    CAS 
    PubMed 
    Article 
    ADS 

    Google Scholar 

  • Zhong, H.-S. et al. Quantum computational advantage using photons. Science 370, 1460–1463 (2020).

    CAS 
    PubMed 
    Article 
    ADS 

    Google Scholar 

  • Cirac, J. I. & Zoller, P. Goals and opportunities in quantum simulation. Nat. Phys. 8, 264–266 (2012).

    CAS 
    Article 

    Google Scholar 

  • Georgescu, I. M., Ashhab, S. & Nori, F. Quantum simulation. Rev. Mod. Phys. 86, 153–185 (2014).

    Article 
    ADS 

    Google Scholar 

  • Reiher, M., Wiebe, N., Svore, K. M., Wecker, D. & Troyer, M. Elucidating reaction mechanisms on quantum computers. Proc. Natl Acad. Sci. USA 114, 7555–7560 (2017).

    CAS 
    PubMed 
    PubMed Central 
    Article 
    ADS 

    Google Scholar 

  • Quintanilla, J. & Hooley, C. The strong-correlations puzzle. Phys. World 22, 32–37 (2009).

    Article 

    Google Scholar 

  • Childs, A. M., Maslov, D., Nam, Y., Ross, N. J. & Su, Y. Toward the first quantum simulation with quantum speedup. Proc. Natl Acad. Sci. USA 115, 9456–9461 (2018).

    MathSciNet 
    CAS 
    PubMed 
    PubMed Central 
    MATH 
    Article 
    ADS 

    Google Scholar 

  • Lloyd, S. Universal quantum simulators. Science 273, 1073–1078 (1996). This article discusses in detail how digital quantum simulation could be implemented on quantum computers, and forms the basis for the fault-tolerant quantum simulation protocols discussed here.

    MathSciNet 
    CAS 
    PubMed 
    MATH 
    Article 
    ADS 

    Google Scholar 

  • Roffe, J. Quantum error correction: an introductory guide. Contemp. Phys. 60, 226–245 (2019).

    Article 
    ADS 

    Google Scholar 

  • Preskill, J. Quantum computing in the NISQ era and beyond. Quantum 2, 79 (2018).

    Article 

    Google Scholar 

  • Buluta, I. & Nori, F. Quantum simulators. Science 326, 108–111 (2009).

    CAS 
    PubMed 
    Article 
    ADS 

    Google Scholar 

  • Browaeys, A. & Lahaye, T. Many-body physics with individually controlled Rydberg atoms. Nat. Phys. 16, 132–142 (2020).

    CAS 
    Article 

    Google Scholar 

  • Gross, C. & Bloch, I. Quantum simulations with ultracold atoms in optical lattices. Science 357, 995–1001 (2017).

    CAS 
    PubMed 
    Article 
    ADS 

    Google Scholar 

  • Greiner, M., Mandel, O., Esslinger, T., Hänsch, T. W. & Bloch, I. Quantum phase transition from a superfluid to a Mott insulator in a gas of ultracold atoms. Nature 415, 39–44 (2002). This article demonstrates the first analogue quantum simulation of a strongly correlated quantum system, making use of cold atoms in optical lattices.

    CAS 
    PubMed 
    Article 
    ADS 

    Google Scholar 

  • Houck, A. A., Türeci, H. E. & Koch, J. On-chip quantum simulation with superconducting circuits. Nat. Phys. 8, 292–299 (2012).

    CAS 
    Article 

    Google Scholar 

  • Hartmann, M. J. Quantum simulation with interacting photons. J. Opt. 18, 104005 (2016).

    Article 
    ADS 

    Google Scholar 

  • Blatt, R. & Roos, C. F. Quantum simulations with trapped ions. Nat. Phys. 8, 277–284 (2012).

    CAS 
    Article 

    Google Scholar 

  • Monroe, C. et al. Programmable quantum simulations of spin systems with trapped ions. Rev. Mod. Phys. 93, 025001 (2021).

    MathSciNet 
    CAS 
    Article 
    ADS 

    Google Scholar 

  • Aspuru-Guzik, A. & Walther, P. Photonic quantum simulators. Nat. Phys. 8, 285–291 (2012).

    CAS 
    Article 

    Google Scholar 

  • White, A. G. Photonic quantum simulation. In 2014 OptoElectronics and Communication Conference and Australian Conference on Optical Fibre Technology 660–661 (Optica Publishing Group, 2014).

  • Choi, J.-y et al. Exploring the many-body localization transition in two dimensions. Science 352, 1547–1552 (2016). This paper provides an important recent demonstration of the use of analogue quantum simulators with cold atoms in optical lattices to explore the dynamics of interacting particles in a disordered system, which is intractable to classical computation.

    MathSciNet 
    CAS 
    PubMed 
    MATH 
    Article 
    ADS 

    Google Scholar 

  • Chiu, C. S. et al. String patterns in the doped Hubbard model. Science 365, 251–256 (2019).

    MathSciNet 
    CAS 
    PubMed 
    MATH 
    Article 
    ADS 

    Google Scholar 

  • Koepsell, J. et al. Imaging magnetic polarons in the doped Fermi–Hubbard model. Nature 572, 358–362 (2019).

    CAS 
    PubMed 
    Article 
    ADS 

    Google Scholar 

  • Semeghini, G. et al. Probing topological spin liquids on a programmable quantum simulator. Science 374, 1242–1247 (2021).

  • Satzinger, K. J. et al. Realizing topologically ordered states on a quantum processor. Science374, 1237–1241 (2021).

  • Bluvstein, D. et al. Controlling quantum many-body dynamics in driven Rydberg atom arrays. Science 371, 1355–1359 (2021). This article demonstrates the state of the art for observing many-body dynamics in an analogue quantum simulator with neutral atom arrays and Rydberg excitations.

    MathSciNet 
    CAS 
    PubMed 
    MATH 
    Article 
    ADS 

    Google Scholar 

  • Scholl, P. et al. Quantum simulation of 2D antiferromagnets with hundreds of Rydberg atoms. Nature 595, 233–238 (2021). This article demonstrates analogue quantum simulation of dynamics with 196 spins using neutral atoms in tweezer arrays.

    CAS 
    PubMed 
    Article 
    ADS 

    Google Scholar 

  • Zhang, J. et al. Observation of a many-body dynamical phase transition with a 53-qubit quantum simulator. Nature 551, 601–604 (2017).

    CAS 
    PubMed 
    PubMed Central 
    Article 
    ADS 

    Google Scholar 

  • Zhang, J. et al. Observation of a discrete time crystal. Nature 543, 217–220 (2017).

    CAS 
    PubMed 
    Article 
    ADS 

    Google Scholar 

  • Barreiro, J. T. et al. An open-system quantum simulator with trapped ions. Nature 470, 486–491 (2011).

    CAS 
    PubMed 
    Article 
    ADS 

    Google Scholar 

  • Altman, E. et al. Quantum simulators: architectures and opportunities. PRX Quantum 2, 017003 (2021).

    Article 

    Google Scholar 

  • LeBlanc, J. P. F. et al. Solutions of the two-dimensional Hubbard model: benchmarks and results from a wide range of numerical algorithms. Phys. Rev. X 5, 041041 (2015).

    Google Scholar 

  • Zheng, B.-X. et al. Stripe order in the underdoped region of the two-dimensional Hubbard model. Science 358, 1155–1160 (2017).

    MathSciNet 
    CAS 
    PubMed 
    MATH 
    Article 
    ADS 

    Google Scholar 

  • Bauer, B. et al. The ALPS project release 2.0: open source software for strongly correlated systems. J. Stat. Mech. 2011, P05001 (2011).

    Google Scholar 

  • Becca, F. & Sorella, S. Quantum Monte Carlo Approaches for Correlated Systems (Cambridge Univ. Press, 2017).

  • Werner, P., Oka, T. & Millis, A. J. Diagrammatic Monte Carlo simulation of nonequilibrium systems. Phys. Rev. B 79, 035320 (2009).

    Article 
    ADS 
    CAS 

    Google Scholar 

  • Troyer, M. & Wiese, U.-J. Computational complexity and fundamental limitations to fermionic quantum Monte Carlo simulations. Phys. Rev. Lett. 94, 170201 (2005).

    PubMed 
    Article 
    ADS 
    CAS 

    Google Scholar 

  • Eisert, J. Entangling power and quantum circuit complexity. Phys. Rev. Lett.127, 020501 (2021).

  • Swingle, B., Bentsen, G., Schleier-Smith, M. & Hayden, P. Measuring the scrambling of quantum information. Phys. Rev. A 94, 040302 (2016).

    MathSciNet 
    Article 
    ADS 

    Google Scholar 

  • Hatano, N. & Suzuki, M. in Quantum Annealing and Other Optimization Methods (eds Das, A. & Chakrabarti, B. K.) 37–68 (Lecture Notes in Physics, Springer, 2005).

  • Childs, A. M., Su, Y., Tran, M. C., Wiebe, N. & Zhu, S. Theory of Trotter error with commutator scaling. Phys. Rev. X 11, 011020 (2021).

    CAS 

    Google Scholar 

  • Heyl, M., Hauke, P. & Zoller, P. Quantum localization bounds trotter errors in digital quantum simulation. Sci. Adv. 5, eaau8342 (2019).

    PubMed 
    PubMed Central 
    Article 
    ADS 

    Google Scholar 

  • Wecker, D., Bauer, B., Clark, B. K., Hastings, M. B. & Troyer, M. Gate-count estimates for performing quantum chemistry on small quantum computers. Phys. Rev. A 90, 022305 (2014).

    Article 
    ADS 
    CAS 

    Google Scholar 

  • Wecker, D. et al. Solving strongly correlated electron models on a quantum computer. Phys. Rev. A 92, 062318 (2015).

    Article 
    ADS 
    CAS 

    Google Scholar 

  • Kliesch, M., Gogolin, C. & Eisert, J. Lieb–Robinson Bounds and the Simulation of Time-Evolution of Local Observables in Lattice Systems 301–318 (Springer, 2014).

  • Schollwöck, U. The density-matrix renormalization group in the age of matrix product states. Ann. Phys. 326, 96–192 (2011).

    MathSciNet 
    MATH 
    Article 
    ADS 
    CAS 

    Google Scholar 

  • Verstraete, F., Murg, V. & Cirac, J. I. Matrix product states, projected entangled pair states, and variational renormalization group methods for quantum spin systems. Adv. Phys. 57, 143–224 (2008).

    Article 
    ADS 

    Google Scholar 

  • Vidal, G. Efficient simulation of one-dimensional quantum many-body systems. Phys. Rev. Lett. 93, 040502 (2004). This article introduced classical simulation of one-dimensional many-body systems using matrix product states, which provide the present state of the art in classical simulation of quench dynamics in strongly interacting systems.

    PubMed 
    Article 
    ADS 
    CAS 

    Google Scholar 

  • Amico, L., Fazio, R., Osterloh, A. & Vedral, V. Entanglement in many-body systems. Rev. Mod. Phys. 80, 517–576 (2008).

    MathSciNet 
    CAS 
    MATH 
    Article 
    ADS 

    Google Scholar 

  • Albash, T. & Lidar, D. A. Adiabatic quantum computation. Rev. Mod. Phys. 90, 015002 (2018).

    MathSciNet 
    Article 
    ADS 

    Google Scholar 

  • Kempe, J., Kitaev, A. & Regev, O. The complexity of the local Hamiltonian problem. SIAM J. Comput. 35, 1070–1097 (2006).

    MathSciNet 
    MATH 
    Article 

    Google Scholar 

  • Poggi, P. M., Lysne, N. K., Kuper, K. W., Deutsch, I. H. & Jessen, P. S. Quantifying the sensitivity to errors in analog quantum simulation. PRX Quantum 1, 020308 (2020).

    Article 

    Google Scholar 

  • Lanyon, B. P. et al. Universal digital quantum simulation with trapped ions. Science 334, 57–61 (2011).

    CAS 
    PubMed 
    Article 
    ADS 

    Google Scholar 

  • Martinez, E. A. et al. Real-time dynamics of lattice gauge theories with a few-qubit quantum computer. Nature 534, 516–519 (2016).

    CAS 
    PubMed 
    Article 
    ADS 

    Google Scholar 

  • Berry, D. W., Childs, A. M., Cleve, R., Kothari, R. & Somma, R. D. Simulating Hamiltonian dynamics with a truncated taylor series. Phys. Rev. Lett. 114, 090502 (2015).

    PubMed 
    Article 
    ADS 
    CAS 

    Google Scholar 

  • Haah, J., Hastings, M. B., Kothari, R. & Low, G. H. Quantum algorithm for simulating real time evolution of lattice Hamiltonians. SIAM J. Comput. FOCS18-250-FOCS18-284 (2021).

  • Aharonov, D. & Ta-Shma, A. Adiabatic quantum state generation and statistical zero knowledge. In Proc. Thirty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’03 20–29 (Association for Computing Machinery, 2003).

  • Low, G. H. & Chuang, I. L. Hamiltonian simulation by qubitization. Quantum 3, 163 (2019).

    Article 

    Google Scholar 

  • Flannigan, S. et al. Propagation of errors and quantitative quantum simulation with quantum advantage. Preprint at https://arxiv.org/abs/2204.13644 (2022).

  • Morgado, M. & Whitlock, S. Quantum simulation and computing with rydberg-interacting qubits. AVS Quantum Sci. 3, 023501 (2021).

    CAS 
    Article 
    ADS 

    Google Scholar 

  • Poulin, D. et al. The Trotter step size required for accurate quantum simulation of quantum chemistry. Quantum Inf. Comput. 15, 361–384 (2015).

    MathSciNet 
    CAS 

    Google Scholar 

  • Sornborger, A. T. & Stewart, E. D. Higher-order methods for simulations on quantum computers. Phys. Rev. A 60, 1956–1965 (1999).

    CAS 
    Article 
    ADS 

    Google Scholar 

  • Hastings, M. B., Wecker, D., Bauer, B. & Troyer, M. Improving quantum algorithms for quantum chemistry. Quantum Inf. Comput. 15, 1–21 (2015).

    MathSciNet 
    CAS 

    Google Scholar 

  • Bocharov, A., Roetteler, M. & Svore, K. M. Efficient synthesis of universal repeat-until-success quantum circuits. Phys. Rev. Lett. 114, 080502 (2015).

    PubMed 
    Article 
    ADS 
    CAS 

    Google Scholar 

  • Gidney, C. Halving the cost of quantum addition. Quantum 2, 74 (2018).

    Article 

    Google Scholar 

  • Carrasco, J., Elben, A., Kokail, C., Kraus, B. & Zoller, P. Theoretical and experimental perspectives of quantum verification. PRX Quantum 2, 010102 (2021).

    Article 

    Google Scholar 

  • Eisert, J. et al. Quantum certification and benchmarking. Nat. Rev. Phys. 2, 382–390 (2020).

    Article 

    Google Scholar 

  • Elben, A. et al. Cross-platform verification of intermediate scale quantum devices. Phys. Rev. Lett. 124, 010504 (2020).

    CAS 
    PubMed 
    Article 
    ADS 

    Google Scholar 

  • Bairey, E., Arad, I. & Lindner, N. H. Learning a local Hamiltonian from local measurements. Phys. Rev. Lett. 122, 020504 (2019).

    CAS 
    PubMed 
    Article 
    ADS 

    Google Scholar 

  • Evans, T. J., Harper, R. & Flammia, S. T. Scalable Bayesian Hamiltonian learning. Preprint at https://arxiv.org/abs/1912.07636 (2019).

  • Li, Z., Zou, L. & Hsieh, T. H. Hamiltonian tomography via quantum quench. Phys. Rev. Lett. 124, 160502 (2020).

    CAS 
    PubMed 
    Article 
    ADS 

    Google Scholar 

  • Valenti, A., van Nieuwenburg, E., Huber, S. & Greplova, E. Hamiltonian learning for quantum error correction. Phys. Rev. Res. 1, 033092 (2019).

    CAS 
    Article 

    Google Scholar 

  • Wang, J. et al. Experimental quantum Hamiltonian learning. Nat. Phys. 13, 551–555 (2017).

    Article 
    CAS 

    Google Scholar 

  • Abanin, D. A., Altman, E., Bloch, I. & Serbyn, M. Colloquium: Many-body localization, thermalization, and entanglement. Rev. Mod. Phys. 91, 021001 (2019).

    MathSciNet 
    CAS 
    Article 
    ADS 

    Google Scholar 

  • Ozawa, T. et al. Topological photonics. Rev. Mod. Phys. 91, 015006 (2019).

    MathSciNet 
    CAS 
    Article 
    ADS 

    Google Scholar 

  • Turner, C. J., Michailidis, A. A., Abanin, D. A., Serbyn, M. & Papić, Z. Weak ergodicity breaking from quantum many-body scars. Nat. Phys. 14, 745–749 (2018).

    CAS 
    Article 

    Google Scholar 

  • Bañuls, M. C. et al. Simulating lattice gauge theories within quantum technologies. Eur. Phys. J. D 74, 165 (2020).

    Article 
    ADS 
    CAS 

    Google Scholar 

  • Bentsen, G. et al. Treelike interactions and fast scrambling with cold atoms. Phys. Rev. Lett. 123, 130601 (2019).

    CAS 
    PubMed 
    Article 
    ADS 

    Google Scholar 

  • Periwal, A. et al. Programmable interactions and emergent geometry in an atomic array. Nature 600, 630–635 (2021).

  • Argüello-Luengo, J., González-Tudela, A., Shi, T., Zoller, P. & Cirac, J. I. Analogue quantum chemistry simulation. Nature 574, 215–218 (2019).

    PubMed 
    Article 
    ADS 
    CAS 

    Google Scholar 

  • Cubitt, T., Montanaro, A. & Piddock, S. Universal quantum Hamiltonians. Proc. Natl Acad. Sci. USA 115, 9497–9502 (2018).

  • Zhou, L. & Aharonov, D. Strongly universal Hamiltonian simulators. Preprint at https://arxiv.org/abs/2102.02991 (2021).

  • Kaubruegger, R. et al. Variational spin-squeezing algorithms on programmable quantum sensors. Phys. Rev. Lett. 123, 260505 (2019).

    CAS 
    PubMed 
    Article 
    ADS 

    Google Scholar 

  • Liu, H. et al. Prospects of quantum computing for molecular sciences. Mater. Theory 6, 11 (2022).

  • Bassman, L. et al. Simulating quantum materials with digital quantum computers. Quant. Sci. Technol. 6, 043002 (2021).

  • Ma, H., Govoni, M. & Galli, G. Quantum simulations of materials on near-term quantum computers. npj Comput. Mater. 6, 85 (2020).

    Article 
    ADS 

    Google Scholar 

  • Rieger, H. in Quantum Annealing and Other Optimization Methods (eds Das, A. & Chakrabarti, B. K.) 299–324 (Lecture Notes in Physics, Springer, 2005).

  • Hauke, P., Katzgraber, H. G., Lechner, W., Nishimori, H. & Oliver, W. D. Perspectives of quantum annealing: methods and implementations. Rep. Prog. Phys. 83, 054401 (2020).

    CAS 
    PubMed 
    Article 
    ADS 

    Google Scholar 

  • Lamata, L., Parra-Rodriguez, A., Sanz, M. & Solano, E. Digital-analog quantum simulations with superconducting circuits. Adv. Phys. X 3, 1457981 (2018).

    Google Scholar 

  • Brydges, T. et al. Probing Rényi entanglement entropy via randomized measurements. Science 364, 260–263 (2019).

    CAS 
    PubMed 
    Article 
    ADS 

    Google Scholar 

  • Kokail, C. et al. Self-verifying variational quantum simulation of lattice models. Nature 569, 355–360 (2019). This article reports the demonstration of an analogue quantum simulator being used for variational quantum simulation, demonstrating a self-verified solution to a model from high-energy physics.

    CAS 
    PubMed 
    Article 
    ADS 

    Google Scholar 

  • Babukhin, D. V., Zhukov, A. A. & Pogosov, W. V. Hybrid digital-analog simulation of many-body dynamics with superconducting qubits. Phys. Rev. A 101, 052337 (2020).

    CAS 
    Article 
    ADS 

    Google Scholar 

  • Arrazola, I., Pedernales, J. S., Lamata, L. & Solano, E. Digital-analog quantum simulation of spin models in trapped ions. Sci. Rep. 6, 30534 (2016).

    CAS 
    PubMed 
    PubMed Central 
    Article 
    ADS 

    Google Scholar 

  • Kokail, C., van Bijnen, R., Elben, A., Vermersch, B. & Zoller, P. Entanglement Hamiltonian tomography in quantum simulation. Nat. Phys. 17, 936–942 (2021).

  • Joshi, M. K. et al. Quantum information scrambling in a trapped-ion quantum simulator with tunable range interactions. Phys. Rev. Lett. 124, 240505 (2020).

    CAS 
    PubMed 
    Article 
    ADS 

    Google Scholar 

  • Henriet, L. et al. Quantum computing with neutral atoms. Quantum 4, 327 (2020).

    Article 

    Google Scholar 

  • Cerezo, M. et al. Variational quantum algorithms. Nat. Rev. Phys. 3, 625–644 (2021).

  • Zhou, L., Wang, S.-T., Choi, S., Pichler, H. & Lukin, M. D. Quantum approximate optimization algorithm: performance, mechanism, and implementation on near-term devices. Phys. Rev. X 10, 021067 (2020).

    CAS 

    Google Scholar 

  • Biamonte, J. et al. Quantum machine learning. Nature 549, 195–202 (2017).

    CAS 
    PubMed 
    Article 
    ADS 

    Google Scholar 

  • Huang, H.-Y. et al. Power of data in quantum machine learning. Nat. Commun. 12, 2631 (2021).

  • Bloch, I., Dalibard, J. & Nascimbène, S. Quantum simulations with ultracold quantum gases. Nat. Phys. 8, 267–276 (2012).

    CAS 
    Article 

    Google Scholar 

  • Schäfer, F., Fukuhara, T., Sugawa, S., Takasu, Y. & Takahashi, Y. Tools for quantum simulation with ultracold atoms in optical lattices. Nat. Rev. Phys. 2, 411–425 (2020).

    Article 
    CAS 

    Google Scholar 

  • The Hubbard model at half a century. Nat. Phys. 9, 523 (2013).

  • Essler, F. H. L., Frahm, H., Göhmann, F., Klümper, A. & Korepin, V. E. The One-Dimensional Hubbard Model (Cambridge Univ. Press, 2005).

  • Lee, P. A., Nagaosa, N. & Wen, X.-G. Doping a Mott insulator: physics of high-temperature superconductivity. Rev. Mod. Phys. 78, 17–85 (2006).

    CAS 
    Article 
    ADS 

    Google Scholar 

  • von Burg, V. et al. Quantum computing enhanced computational catalysis. Phys. Rev. Res. 3, 033055 (2021).

    Article 

    Google Scholar 

  • Bauer, B., Bravyi, S., Motta, M. & Chan, G. K.-L. Quantum algorithms for quantum chemistry and quantum materials science. Chem. Rev. 120, 12685–12717 (2020).

    CAS 
    PubMed 
    Article 

    Google Scholar 

  • Mobile Computing