1Centre for Quantum Information and Communication, Ecole Polytechnique de Bruxelles, CP 165, Université Libre de Bruxelles, 1050 Brussels, Belgium
2Electromagnetism and Matter Physics Department, University of Granada, Granada, Spain
3Carlos I Institute of Theoretical and Matter Physics, University of Granada, Granada, Spain
4Free University of Berlin, Berlin, Germany
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
The problem of sampling outputs of quantum circuits has been proposed as a candidate for demonstrating a quantum computational advantage (sometimes referred to as quantum “supremacy”). In this work, we investigate whether quantum advantage demonstrations can be achieved for more physically-motivated sampling problems, related to measurements of physical observables. We focus on the problem of sampling the outcomes of an energy measurement, performed on a simple-to-prepare product quantum state – a problem we refer to as energy sampling. For different regimes of measurement resolution and measurement errors, we provide complexity theoretic arguments showing that the existence of efficient classical algorithms for energy sampling is unlikely. In particular, we describe a family of Hamiltonians with nearest-neighbour interactions on a 2D lattice that can be efficiently measured with high resolution using a quantum circuit of commuting gates (IQP circuit), whereas an efficient classical simulation of this process should be impossible. In this high resolution regime, which can only be achieved for Hamiltonians that can be $textit{exponentially fast-forwarded}$, it is possible to use current theoretical tools tying quantum advantage statements to a polynomial-hierarchy collapse whereas for lower resolution measurements such arguments fail. Nevertheless, we show that efficient classical algorithms for low-resolution energy sampling can still be ruled out if we assume that quantum computers are strictly more powerful than classical ones. We believe our work brings a new perspective to the problem of demonstrating quantum advantage and leads to interesting new questions in Hamiltonian complexity.
Featured image: (Left) Scheme representing an energy measurement of a quantum state, as well as the different parameters that characterize it. By repeating the measurement process we can reconstruct a probability distribution containing important information about the quantum system (right). Our work argues that sampling from such probability distributions is hard for classical computers. (Image by Mayec Rancel)
Popular summary
In our work, we focus on showing quantum advantage for the task of measuring the energy of a quantum system or, more precisely, of sampling outcomes of measurements of a Hamiltonian on a quantum state. This is a fundamental task in quantum mechanics that allows us to learn about the Hamiltonian describing a given quantum system which determines, for example, how it evolves in time or its properties at a given temperature. Inspired by recent results about the complexity of sampling from quantum circuits, we give strong evidence that quantum devices are much faster than classical computers at simulating this measurement process.
One of the main parameters describing an energy measurement is its resolution i.e., how accurately we can measure the energy. We show that, for certain families of Hamiltonians, there are efficient quantum energy measurement protocols that reach a very high resolution, unlikely to be reached by classical simulations. Importantly, this quantum advantage still holds even if the quantum measurement is affected by a limited amount of noise, opening up the possibility for implementations in near-term noisy quantum devices. We also give complexity-theoretic arguments showing that even more coarse-grained energy measurements, with much lower resolution, should be hard to simulate with classical computers. Namely, we show that if a classical computer were able to approximately simulate any such measurement, it would also be able to do any quantum computation efficiently, which is believed to be impossible.
Overall, we believe our work contributes towards strengthening the belief that no present or future classical algorithm can beat quantum devices for the task of simulating quantum physics. Furthermore, it can potentially inspire new theoretical and experimental demonstrations of quantum advantage for other physically-motivated problems.
► BibTeX data
► References
[1] Christian Gross and Immanuel Bloch. Quantum simulations with ultracold atoms in optical lattices. Science, 357 (6355): 995–1001, 2017. ISSN 0036-8075. 10.1126/science.aal3837.
https://doi.org/10.1126/science.aal3837
[2] Hannes Bernien, Sylvain Schwartz, Alexander Keesling, Harry Levine, Ahmed Omran, Hannes Pichler, Soonwon Choi, Alexander S. Zibrov, Manuel Endres, Markus Greiner, Vladan Vuletić, and Mikhail D. Lukin. Probing many-body dynamics on a 51-atom quantum simulator. Nature, 551: 579–584, 2017. 10.1038/nature24622.
https://doi.org/10.1038/nature24622
[3] 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. Nature, 551: 601–604, 2017. 10.1038/nature24654.
https://doi.org/10.1038/nature24654
[4] Nicolai Friis, Oliver Marty, Christine Maier, Cornelius Hempel, Milan Holzäpfel, Petar Jurcevic, Martin B. Plenio, Marcus Huber, Christian Roos, Rainer Blatt, and Ben Lanyon. Observation of entangled states of a fully controlled 20-qubit system. Phys. Rev. X, 8: 021012, 2018. 10.1103/PhysRevX.8.021012.
https://doi.org/10.1103/PhysRevX.8.021012
[5] C. Neill, P. Roushan, K. Kechedzhi, S. Boixo, S. V. Isakov, V. Smelyanskiy, R. Barends, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, A. Dunsworth, A. Fowler, B. Foxen, R. Graff, E. Jeffrey, J. Kelly, E. Lucero, A. Megrant, J. Mutus, M. Neeley, C. Quintana, D. Sank, A. Vainsencher, J. Wenner, T. C. White, H. Neven, and J. M. Martinis. A blueprint for demonstrating quantum supremacy with superconducting qubits. Science, pages 195–199, 2018. 10.1126/science.aao4309.
https://doi.org/10.1126/science.aao4309
[6] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al. Quantum supremacy using a programmable superconducting processor. Nature, 574 (7779): 505–510, 2019. 10.1038/s41586-019-1666-5.
https://doi.org/10.1038/s41586-019-1666-5
[7] Rajibul Islam, Ruichao Ma, Philipp M. Preiss, M. Eric Tai, Alexander Lukin, Matthew Rispoli, and Markus Greiner. Measuring entanglement entropy in a quantum many-body system. Nature, 528: 77–83, 2015. 10.1038/nature15750.
https://doi.org/10.1038/nature15750
[8] Tiff Brydges, Andreas Elben, Petar Jurcevic, Benoit Vermersch, Christine Maier, Ben P. Lanyon, Peter Zoller, Rainer Blatt, and Christian F. Roos. Probing rényi entanglement entropy via randomized measurements. Science, 364: 260–263, 2019. 10.1126/science.aau4963.
https://doi.org/10.1126/science.aau4963
[9] Adam M. Kaufman, M. Eric Tai, Alexander Lukin, Matthew Rispoli, Robert Schittko, Philipp M. Preiss, and Markus Greiner. Quantum thermalization through entanglement in an isolated many-body system. Science, 353: 794–800, 2016. 10.1126/science.aaf6725.
https://doi.org/10.1126/science.aaf6725
[10] Alexander Keesling, Ahmed Omran, Harry Levine, Hannes Bernien, Hannes Pichler, Soonwon Choi, Rhine Samajdar, Sylvain Schwartz, Pietro Silvi, Subir Sachdev, Peter Zoller, Manuel Endres, Markus Greiner, Vladan Vuletić, and Mikhail D. Lukin. Quantum kibble–zurek mechanism and critical dynamics on a programmable rydberg simulator. Nature, 568: 207–211, 2019. 10.1038/s41586-019-1070-1.
https://doi.org/10.1038/s41586-019-1070-1
[11] Jae-yoon Choi, Sebastian Hild, Johannes Zeiher, Peter Schauß, Antonio Rubio-Abadal, Tarik Yefsah, Vedika Khemani, David A. Huse, Immanuel Bloch, and Christian Gross. Exploring the many-body localization transition in two dimensions. Science, 352 (6293): 1547–1552, June 2016. 10.1126/science.aaf8834.
https://doi.org/10.1126/science.aaf8834
[12] Matthew Rispoli, Alexander Lukin, Robert Schittko, Sooshin Kim, M. Eric Tai, Julian Léonard, and Markus Greiner. Quantum critical behaviour at the many-body localization transition. Nature, 2019. 10.1038/s41586-019-1527-2.
https://doi.org/10.1038/s41586-019-1527-2
[13] Martin Gärttner, Justin G. Bohnet, Arghavan Safavi-Naini, Michael L. Wall, Bollinger John J., and Ana Maria Rey. Measuring out-of-time-order correlations and multiple quantum spectra in a trapped-ion quantum magnet. Nature Physics, 13: 781–786, 2017. 10.1038/nphys4119.
https://doi.org/10.1038/nphys4119
[14] B. Vermersch, A. Elben, L. M. Sieberer, N. Y. Yao, and P. Zoller. Probing scrambling using statistical correlations between randomized measurements. Phys. Rev. X, 9: 021061, Jun 2019. 10.1103/PhysRevX.9.021061.
https://doi.org/10.1103/PhysRevX.9.021061
[15] KJ Satzinger, Y Liu, A Smith, C Knapp, M Newman, C Jones, Z Chen, C Quintana, X Mi, A Dunsworth, et al. Realizing topologically ordered states on a quantum processor. arXiv preprint arXiv:2104.01180, 2021.
arXiv:2104.01180
[16] Giulia Semeghini, Harry Levine, Alexander Keesling, Sepehr Ebadi, Tout T Wang, Dolev Bluvstein, Ruben Verresen, Hannes Pichler, Marcin Kalinowski, Rhine Samajdar, et al. Probing topological spin liquids on a programmable quantum simulator. arXiv preprint arXiv:2104.04119, 2021.
arXiv:2104.04119
[17] S. Trotzky, Y.-A. Chen, A. Flesch, I. P. McCulloch, U. Schollwöck, J. Eisert, and I. Bloch. Probing the relaxation towards equilibrium in an isolated strongly correlated one-dimensional Bose gas. Nature Phys., 8: 325–330, 2012. 10.1038/nphys2232.
https://doi.org/10.1038/nphys2232
[18] S. Braun, M. Friesdorf, J. S. Hodgman, M. Schreiber, J. P. Ronzheimer, A. Riera, M. del Rey, I. Bloch, J. Eisert, and U. Schneider. Emergence of coherence and the dynamics of quantum phase transitions. PNAS, 112: 3641–3646, March 2015. 10.1073/pnas.1408861112.
https://doi.org/10.1073/pnas.1408861112
[19] Ewin Tang. A quantum-inspired classical algorithm for recommendation systems. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 217–228. ACM, 2019. 10.1145/3313276.3316310.
https://doi.org/10.1145/3313276.3316310
[20] Scott Aaronson and Alex Arkhipov. The computational complexity of linear optics. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC ’11, page 333–342, New York, NY, USA, 2011. Association for Computing Machinery. ISBN 9781450306911. 10.1145/1993636.1993682.
https://doi.org/10.1145/1993636.1993682
[21] Michael J. Bremner, Ashley Montanaro, and Dan J. Shepherd. Average-case complexity versus approximate simulation of commuting quantum computations. Phys. Rev. Lett., 117: 080501, Aug 2016. 10.1103/PhysRevLett.117.080501.
https://doi.org/10.1103/PhysRevLett.117.080501
[22] Sergio Boixo, Sergei V. Isakov, Vadim N. Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J. Bremner, John M. Martinis, and Hartmut Neven. Characterizing quantum supremacy in near-term devices. Nature Physics, page 1, April 2018. ISSN 1745-2481. 10.1038/s41567-018-0124-x.
https://doi.org/10.1038/s41567-018-0124-x
[23] Xun Gao, Sheng-Tao Wang, and L.-M. Duan. Quantum supremacy for simulating a translation-invariant ising spin model. Phys. Rev. Lett., 118: 040502, Jan 2017. 10.1103/PhysRevLett.118.040502.
https://doi.org/10.1103/PhysRevLett.118.040502
[24] Juan Bermejo-Vega, Dominik Hangleiter, Martin Schwarz, Robert Raussendorf, and Jens Eisert. Architectures for quantum simulation showing a quantum speedup. Phys. Rev. X, 8: 021010, Apr 2018. 10.1103/PhysRevX.8.021010.
https://doi.org/10.1103/PhysRevX.8.021010
[25] Aram W Harrow and Ashley Montanaro. Quantum computational supremacy. Nature, 549 (7671): 203, 2017. 10.1038/nature23458.
https://doi.org/10.1038/nature23458
[26] John Preskill. Quantum Computing in the NISQ era and beyond. Quantum, 2: 79, August 2018. ISSN 2521-327X. 10.22331/q-2018-08-06-79.
https://doi.org/10.22331/q-2018-08-06-79
[27] Michael J. Bremner, Ashley Montanaro, and Dan J. Shepherd. Achieving quantum supremacy with sparse and noisy commuting quantum computations. Quantum, 1: 8, April 2017. 10.22331/q-2017-04-25-8.
https://doi.org/10.22331/q-2017-04-25-8
[28] J. Miller, S. Sanders, and A. Miyake. Quantum supremacy in constant-time measurement-based computation: A unified architecture for sampling and verification. Phys. Rev. A, 96 (6): 062320, December 2017. 10.1103/PhysRevA.96.062320.
https://doi.org/10.1103/PhysRevA.96.062320
[29] Scott Aaronson and Lijie Chen. Complexity-theoretic foundations of quantum supremacy experiments. In Proceedings of the 32Nd Computational Complexity Conference, CCC ’17, pages 22:1–22:67, Germany, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. ISBN 978-3-95977-040-8. 10.4230/LIPIcs.CCC.2017.22.
https://doi.org/10.4230/LIPIcs.CCC.2017.22
[30] D. Hangleiter, M. Kliesch, M. Schwarz, and J. Eisert. Direct certification of a class of quantum simulations. Quantum Sci. Technol., 2 (1): 015004, 2017. ISSN 2058-9565. 10.1088/2058-9565/2/1/015004.
https://doi.org/10.1088/2058-9565/2/1/015004
[31] A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani. Quantum supremacy and the complexity of random circuit sampling. Nature Phys., 15: 159–163, March 2019. 10.1038/s41567-018-0318-2.
https://doi.org/10.1038/s41567-018-0318-2
[32] Abhinav Deshpande, Bill Fefferman, Minh C. Tran, Michael Foss-Feig, and Alexey V. Gorshkov. Dynamical Phase Transitions in Sampling Complexity. Physical Review Letters, 121 (3): 030501, July 2018. 10.1103/PhysRevLett.121.030501.
https://doi.org/10.1103/PhysRevLett.121.030501
[33] Gopikrishnan Muraleedharan, Akimasa Miyake, and Ivan H. Deutsch. Quantum computational supremacy in the sampling of bosonic random walkers on a one-dimensional lattice. New Journal of Physics, 21 (5): 055003, May 2019. ISSN 1367-2630. 10.1088/1367-2630/ab0610. arXiv: 1805.01858.
https://doi.org/10.1088/1367-2630/ab0610
[34] Nishad Maskara, Abhinav Deshpande, Minh C. Tran, Adam Ehrenberg, Bill Fefferman, and Alexey V. Gorshkov. Complexity phase diagram for interacting and long-range bosonic Hamiltonians. arXiv:1906.04178, June 2019.
arXiv:1906.04178
[35] A Yu Kitaev. Quantum measurements and the abelian stabilizer problem. arXiv:quant-ph/9511026, 1995.
arXiv:quant-ph/9511026
[36] Daniel S. Abrams and Seth Lloyd. Quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors. Phys. Rev. Lett., 83: 5162–5165, Dec 1999. 10.1103/PhysRevLett.83.5162.
https://doi.org/10.1103/PhysRevLett.83.5162
[37] Dayou Yang, Andrey Grankin, Lukas M Sieberer, Denis V Vasilyev, and Peter Zoller. Quantum non-demolition measurement of a many-body hamiltonian. Nature communications, 11 (1): 1–8, 2020. 10.1038/s41467-020-14489-5.
https://doi.org/10.1038/s41467-020-14489-5
[38] Joonsuk Huh, Gian Giacomo Guerreschi, Borja Peropadre, Jarrod R McClean, and Alán Aspuru-Guzik. Boson sampling for molecular vibronic spectra. Nature Photonics, 9 (9): 615, 2015. 10.1038/nphoton.2015.153.
https://doi.org/10.1038/nphoton.2015.153
[39] Craig S. Hamilton, Regina Kruse, Linda Sansoni, Sonja Barkhofen, Christine Silberhorn, and Igor Jex. Gaussian boson sampling. Phys. Rev. Lett., 119: 170501, Oct 2017. 10.1103/PhysRevLett.119.170501.
https://doi.org/10.1103/PhysRevLett.119.170501
[40] Vincenzo Barone (Editor). Computational Strategies for Spectroscopy: from Small Molecules to Nano Systems. Wiley, Hoboken, New Jersey, USA, 2012. ISBN 0470470178.
[41] Fabrizio Santoro, Roberto Improta, Alessandro Lami, Julien Bloino, and Vincenzo Barone. Effective method to compute franck-condon integrals for optical spectra of large molecules in solution. The Journal of Chemical Physics, 126 (8): 084509, 2007. 10.1063/1.2437197.
https://doi.org/10.1063/1.2437197
[42] Pawel Wocjan and Shengyu Zhang. Several natural bqp-complete problems. arXiv:quant-ph/0606179, 2006.
arXiv:quant-ph/0606179
[43] Dominik Janzing, Pawel Wocjan, and Shengyu Zhang. A single-shot measurement of the energy of product states in a translation invariant spin chain can replace any quantum computation. New Journal of Physics, 10 (9): 093004, 2008. 10.1088/1367-2630/10/9/093004.
https://doi.org/10.1088/1367-2630/10/9/093004
[44] Yosi Atia and Dorit Aharonov. Fast-forwarding of hamiltonians and exponentially precise measurements. Nature communications, 8 (1): 1572, 2017. 10.1038/s41467-017-01637-7.
https://doi.org/10.1038/s41467-017-01637-7
[45] John Von Neumann. Mathematical foundations of quantum mechanics: New edition. Princeton university press, 2018.
[46] Y. Aharonov, S. Massar, and S. Popescu. Measuring energy, estimating hamiltonians, and the time-energy uncertainty relation. Phys. Rev. A, 66: 052107, Nov 2002. 10.1103/PhysRevA.66.052107.
https://doi.org/10.1103/PhysRevA.66.052107
[47] Pawel Wocjan, Dominik Janzing, Thomas Decker, and Thomas Beth. Measuring 4-local n-qubit observables could probabilistically solve PSPACE. arXiv:quant-ph/0308011, 2003.
arXiv:quant-ph/0308011
[48] Dan Shepherd and Michael J. Bremner. Temporally unstructured quantum computation. Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 465 (2105): 1413–1439, 2009. ISSN 1364-5021. 10.1098/rspa.2008.0443.
https://doi.org/10.1098/rspa.2008.0443
[49] Tomoyuki Morimae, Keisuke Fujii, and Joseph F. Fitzsimons. Hardness of classically simulating the one-clean-qubit model. Phys. Rev. Lett., 112: 130502, Apr 2014. 10.1103/PhysRevLett.112.130502.
https://doi.org/10.1103/PhysRevLett.112.130502
[50] Tomoyuki Morimae. Hardness of classically sampling the one-clean-qubit model with constant total variation distance error. Phys. Rev. A, 96: 040302, Oct 2017. 10.1103/PhysRevA.96.040302.
https://doi.org/10.1103/PhysRevA.96.040302
[51] Alexei Yu Kitaev, Alexander Shen, and Mikhail N Vyalyi. Classical and quantum computation. Number 47. American Mathematical Soc., 2002.
[52] Andrew M. Childs, Enrico Deotto, Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Andrew J. Landahl. Quantum search by measurement. Phys. Rev. A, 66: 032314, Sep 2002. 10.1103/PhysRevA.66.032314.
https://doi.org/10.1103/PhysRevA.66.032314
[53] Seth Lloyd. Universal quantum simulators. Science, pages 1073–1078, 1996. 10.1126/science.273.5278.1073.
https://doi.org/10.1126/science.273.5278.1073
[54] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Simulating hamiltonian dynamics with a truncated taylor series. Phys. Rev. Lett., 114: 090502, Mar 2015a. 10.1103/PhysRevLett.114.090502.
https://doi.org/10.1103/PhysRevLett.114.090502
[55] R. Somma, G. Ortiz, J. E. Gubernatis, E. Knill, and R. Laflamme. Simulating physical phenomena by quantum networks. Phys. Rev. A, 65: 042323, Apr 2002. 10.1103/PhysRevA.65.042323.
https://doi.org/10.1103/PhysRevA.65.042323
[56] Rolando D Somma. Quantum eigenvalue estimation via time series analysis. New Journal of Physics, 21 (12): 123025, 2019. 10.1088/1367-2630/ab5c60.
https://doi.org/10.1088/1367-2630/ab5c60
[57] P. Roushan, C. Neill, J. Tangpanitanon, V. M. Bastidas, A. Megrant, R. Barends, Y. Chen, Z. Chen, B. Chiaro, A. Dunsworth, A. Fowler, B. Foxen, M. Giustina, E. Jeffrey, J. Kelly, E. Lucero, J. Mutus, M. Neeley, C. Quintana, D. Sank, A. Vainsencher, J. Wenner, T. White, H. Neven, D. G. Angelakis, and J. Martinis. Spectroscopic signatures of localization with interacting photons in superconducting qubits. Science, 358 (6367): 1175–1179, 2017. ISSN 0036-8075. 10.1126/science.aao1401.
https://doi.org/10.1126/science.aao1401
[58] B. M. Terhal and D. P. DiVincenzo. Adaptive quantum computation, constant depth quantum circuits and arthur-merlin games. Quantum Inf. Comput., 4 (2): 134–145, 2004.
[59] Michael J. Bremner, Richard Jozsa, and Dan J. Shepherd. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 2010. ISSN 1364-5021. 10.1098/rspa.2010.0301.
https://doi.org/10.1098/rspa.2010.0301
[60] D. W. Berry, A. M. Childs, and R. Kothari. Hamiltonian simulation with nearly optimal dependence on all parameters. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 792–809, Oct 2015b. 10.1109/FOCS.2015.54.
https://doi.org/10.1109/FOCS.2015.54
[61] Guang Hao Low and Isaac L. Chuang. Optimal hamiltonian simulation by quantum signal processing. Phys. Rev. Lett., 118: 010501, Jan 2017. 10.1103/PhysRevLett.118.010501.
https://doi.org/10.1103/PhysRevLett.118.010501
[62] Guang Hao Low and Isaac L. Chuang. Hamiltonian Simulation by Qubitization. Quantum, 3: 163, July 2019. ISSN 2521-327X. 10.22331/q-2019-07-12-163.
https://doi.org/10.22331/q-2019-07-12-163
[63] Shantanav Chakraborty, András Gilyén, and Stacey Jeffery. The Power of Block-Encoded Matrix Powers: Improved Regression Techniques via Faster Hamiltonian Simulation. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 33:1–33:14, Dagstuhl, Germany, 2019. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. ISBN 978-3-95977-109-2. 10.4230/LIPIcs.ICALP.2019.33.
https://doi.org/10.4230/LIPIcs.ICALP.2019.33
[64] D. Aharonov and M. Ben-Or. Fault-tolerant quantum computation with constant error. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, STOC ’97, page 176–188, New York, NY, USA, 1997. Association for Computing Machinery. ISBN 0897918886. 10.1145/258533.258579.
https://doi.org/10.1145/258533.258579
[65] Michael A Nielsen and Isaac Chuang. Quantum computation and quantum information, 2002.
[66] Jean-Paul Blaizot and Georges Ripka. Quantum theory of finite systems, volume 3. MIT press Cambridge, MA, 1986.
[67] VS Shchesnovich. The second quantization method for indistinguishable particles (lecture notes in physics, ufabc 2010). arXiv preprint arXiv:1308.3275, 2013.
arXiv:1308.3275
[68] Cristina Cirstoiu, Zoe Holmes, Joseph Iosue, Lukasz Cincio, Patrick J Coles, and Andrew Sornborger. Variational fast forwarding for quantum simulation beyond the coherence time. npj Quantum Information, 6 (1): 1–10, 2020. 10.1038/s41534-020-00302-0.
https://doi.org/10.1038/s41534-020-00302-0
[69] Daniel Gottesman. Stabilizer codes and quantum error correction. arXiv preprint quant-ph/9705052, 1997. 10.7907/rzr7-dt72.
https://doi.org/10.7907/rzr7-dt72
arXiv:quant-ph/9705052
[70] H. J. Briegel and R. Raussendorf. Persistent entanglement in arrays of interacting particles. Phys. Rev. Lett., 86: 910, 2001. 10.1103/PhysRevLett.86.910.
https://doi.org/10.1103/PhysRevLett.86.910
[71] R. Raussendorf and H. J. Briegel. A one-way quantum computer. Phys. Rev. Lett., 86: 5188–5191, May 2001. 10.1103/PhysRevLett.86.5188.
https://doi.org/10.1103/PhysRevLett.86.5188
[72] Dominik Hangleiter, Juan Bermejo-Vega, Martin Schwarz, and Jens Eisert. Anticoncentration theorems for schemes showing a quantum speedup. Quantum, 2: 65, May 2018. ISSN 2521-327X. 10.22331/q-2018-05-22-65.
https://doi.org/10.22331/q-2018-05-22-65
[73] R. M. Karp and R. J. Lipton. Some connections between nonuniform and uniform complexity classes. In Proc. 12th Annu. Symp. Theory Comput., STOC, pages 302–309. ACM, 1980. ISBN 0-89791-017-6. 10.1145/800141.804678.
https://doi.org/10.1145/800141.804678
[74] L. Fortnow. Beyond NP: The work and legacy of Larry Stockmeyer. In Proc. 37th Annu. Symp. Theory Comput., STOC, pages 120–127. ACM, 2005. 10.1145/1060590.1060609.
https://doi.org/10.1145/1060590.1060609
[75] S. Aaronson. P$neq$NP? Springer, 2016. 10.1007/978-3-319-32162-2.
https://doi.org/10.1007/978-3-319-32162-2
[76] Larry Stockmeyer. On approximation algorithms for # P. SIAM Journal on Computing, 14 (4): 849–861, 1985. 10.1137/0214060.
https://doi.org/10.1137/0214060
[77] Seinosuke Toda. PP is as hard as the polynomial-time hierarchy. SIAM J. Comput., 20 (5): 865–877, October 1991. ISSN 0097-5397. 10.1137/0220053.
https://doi.org/10.1137/0220053
[78] J. Haferkamp, D. Hangleiter, A. Bouland, B. Fefferman, J. Eisert, and J. Bermejo-Vega. Closing gaps of a quantum advantage with short-time hamiltonian dynamics. Phys. Rev. Lett., 125: 250501, Dec 2020. 10.1103/PhysRevLett.125.250501.
https://doi.org/10.1103/PhysRevLett.125.250501
[79] S. Aaronson. Quantum computing, postselection, and probabilistic polynomial-time. Proc. Roy. Soc. A, 461: 2063, 2005. ISSN 1364-5021. 10.1098/rspa.2005.1546.
https://doi.org/10.1098/rspa.2005.1546
[80] Dorit Aharonov, Wim Van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and Oded Regev. Adiabatic quantum computation is equivalent to standard quantum computation. SIAM review, 50 (4): 755–787, 2008. 10.1137/080734479.
https://doi.org/10.1137/080734479
[81] Subir Sachdev. Quantum Phase Transitions. Cambridge University Press, 2 edition, 2011. 10.1017/CBO9780511973765.
https://doi.org/10.1017/CBO9780511973765
[82] Yichen Huang and Xie Chen. Quantum circuit complexity of one-dimensional topological phases. Phys. Rev. B, 91: 195143, May 2015. 10.1103/PhysRevB.91.195143.
https://doi.org/10.1103/PhysRevB.91.195143
[83] Libor Caha, Zeph Landau, and Daniel Nagaj. Clocks in feynman’s computer and kitaev’s local hamiltonian: Bias, gaps, idling, and pulse tuning. Phys. Rev. A, 97: 062306, Jun 2018. 10.1103/PhysRevA.97.062306.
https://doi.org/10.1103/PhysRevA.97.062306
[84] Xiaotong Ni and Maarten Van Den Nest. Commuting quantum circuits: efficient classical simulations versus hardness results. Quantum Information & Computation, 13 (1-2): 54–72, 2013.
[85] Alexandra E. Moylett and Peter S. Turner. Quantum simulation of partially distinguishable boson sampling. Phys. Rev. A, 97: 062329, Jun 2018. 10.1103/PhysRevA.97.062329.
https://doi.org/10.1103/PhysRevA.97.062329
[86] C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani. Strengths and weaknesses of quantum computing. SIAM J. Comp., 26 (5): 1510–1523, 1997. 10.1137/S0097539796300933.
https://doi.org/10.1137/S0097539796300933
[87] Hakop Pashayan, Stephen D. Bartlett, and David Gross. From estimation of quantum probabilities to simulation of quantum circuits. Quantum, 4: 223, January 2020. ISSN 2521-327X. 10.22331/q-2020-01-13-223.
https://doi.org/10.22331/q-2020-01-13-223
[88] Dorit Aharonov and Tomer Naveh. Quantum NP-a survey. arXiv preprint quant-ph/0210077, 2002.
arXiv:quant-ph/0210077
[89] H. T. Diep. Frustrated Spin Systems. World Scientific, 2004. ISBN 978-981-256-781-9.
[90] Toby S. Cubitt, Ashley Montanaro, and Stephen Piddock. Universal quantum Hamiltonians. Proceedings of the National Academy of Sciences, 115 (38): 9497–9502, September 2018. ISSN 0027-8424, 1091-6490. 10.1073/pnas.1804949115.
https://doi.org/10.1073/pnas.1804949115
[91] Ramis Movassagh. Cayley path and quantum computational supremacy: A proof of average-case #P-hardness of Random Circuit Sampling with quantified robustness. arXiv:1909.06210, September 2019.
arXiv:1909.06210
[92] Ramis Movassagh. Efficient unitary paths and quantum computational supremacy: A proof of average-case hardness of Random Circuit Sampling. arXiv:1810.04681, October 2018.
arXiv:1810.04681
[93] Dominik Hangleiter, Martin Kliesch, Jens Eisert, and Christian Gogolin. Sample complexity of device-independently certified “quantum supremacy”. Phys. Rev. Lett., 122: 210502, May 2019. 10.1103/PhysRevLett.122.210502.
https://doi.org/10.1103/PhysRevLett.122.210502
[94] Joseph F. Fitzsimons and Elham Kashefi. Unconditionally verifiable blind quantum computation. Phys. Rev. A, 96: 012303, Jul 2017. 10.1103/PhysRevA.96.012303.
https://doi.org/10.1103/PhysRevA.96.012303
[95] Joseph F. Fitzsimons, Michal Hajdušek, and Tomoyuki Morimae. Post hoc verification of quantum computation. Phys. Rev. Lett., 120: 040501, Jan 2018. 10.1103/PhysRevLett.120.040501.
https://doi.org/10.1103/PhysRevLett.120.040501
[96] Urmila Mahadev. Classical verification of quantum computations. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 259–267. IEEE, 2018. 10.1109/FOCS.2018.00033.
https://doi.org/10.1109/FOCS.2018.00033
[97] Roberto Oliveira and Barbara M Terhal. The complexity of quantum spin systems on a two-dimensional square lattice. Quantum Information & Computation, 8 (10): 900–924, 2008.
[98] David Gosset, Barbara M. Terhal, and Anna Vershynina. Universal adiabatic quantum computation via the space-time circuit-to-hamiltonian construction. Phys. Rev. Lett., 114: 140501, Apr 2015. 10.1103/PhysRevLett.114.140501.
https://doi.org/10.1103/PhysRevLett.114.140501
[99] Kevin K. H. Cheung and Michele Mosca. Decomposing Finite Abelian Groups. Quantum Info. Comput., 1 (3): 26–32, October 2001. ISSN 1533-7146. 10.5555/2011339.2011341.
https://doi.org/10.5555/2011339.2011341
[100] Juan Bermejo-Vega, Cedric Yen-Yu Lin, and Maarten Van den Nest. The computational power of normalizer circuits over black-box groups. arXiv:1409.4800.
arXiv:1409.4800
[101] Sevag Gharibian, Yichen Huang, Zeph Landau, and Seung Woo Shin. Quantum hamiltonian complexity. Foundations and Trends® in Theoretical Computer Science, 10 (3): 159–282, 2015. ISSN 1551-305X. 10.1561/0400000066.
https://doi.org/10.1561/0400000066
[102] Greg Kuperberg. How hard is it to approximate the jones polynomial? Theory of Computing, 11 (6): 183–219, 2015. 10.4086/toc.2015.v011a006.
https://doi.org/10.4086/toc.2015.v011a006
Cited by
[1] Cristina Cîrstoiu, Zoë Holmes, Joseph Iosue, Lukasz Cincio, Patrick J. Coles, and Andrew Sornborger, “Variational fast forwarding for quantum simulation beyond the coherence time”, npj Quantum Information 6, 82 (2020).
[2] Jacob L. Beckey, M. Cerezo, Akira Sone, and Patrick J. Coles, “Variational Quantum Algorithm for Estimating the Quantum Fisher Information”, arXiv:2010.10488.
[3] A. Roggero, “Spectral-density estimation with the Gaussian integral transform”, Physical Review A 102 2, 022409 (2020).
[4] Jirawat Tangpanitanon, Supanut Thanasilp, Ninnat Dangniam, Marc-Antoine Lemonde, and Dimitris G. Angelakis, “Expressibility and trainability of parametrized analog quantum systems for machine learning applications”, Physical Review Research 2 4, 043364 (2020).
[5] Jirawat Tangpanitanon, Supanut Thanasilp, Marc-Antoine Lemonde, Ninnat Dangiam, and Dimitris G. Angelakis, “Quantum supremacy in driven quantum many-body systems”, arXiv:2002.11946.
[6] Rawad Mezher, Joe Ghalbouni, Joseph Dgheim, and Damian Markham, “Fault-tolerant quantum speedup from constant depth quantum circuits”, arXiv:2005.11539.
[7] Abhinav Deshpande, Alexey V. Gorshkov, and Bill Fefferman, “The importance of the spectral gap in estimating ground-state energies”, arXiv:2007.11582.
The above citations are from SAO/NASA ADS (last updated successfully 2021-06-02 16:30:47). The list may be incomplete as not all publishers provide suitable and complete citation data.
Could not fetch Crossref cited-by data during last attempt 2021-06-02 16:30:45: Could not fetch cited-by data for 10.22331/q-2021-06-02-465 from Crossref. This is normal if the DOI was registered recently.
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.
Coinsmart. Beste Bitcoin-Börse in Europa
Source: https://quantum-journal.org/papers/q-2021-06-02-465/
