The DOI matches its Crossref record; 369 of the 377 references it cites were found in a registry or an index.
Computational advantage of quantum random sampling
Open accessAbstract
Quantum computers have improved and recent experiments have claimed quantum advantage -- completion of a computational task that is evidently hard for any conventional computer. The problem solved is that of obtaining samples, by quantum measurement, from a certain probability distribution. This review shows in what precise way quantum random sampling can be seen as a computation. It explains what that computation solves, in what way it outperforms classical computations, and what methods of verification are available. Quantum random sampling becomes a first test of the presumed exponential computational advantage of quantum computers over classical ones.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“At the same time, because the classical difficulty of sampling from the outputs of random quantum circuits has been extremely well studied over the past decade100, RCS provides a well-vetted benchmark for the computational power of a quantum computer.”
From A 98-qubit trapped-ion quantum computer with all-to-all connectivity (2026) · cites this paper as [100]
Citations
Cites
Items 201–369 of 369
Architectures for Quantum Simulation Showing a Quantum Speedup
Bermejo-Vega, J., Hangleiter, D., Schwarz, M., Raussendorf, R., & Eisert, J. (2018) · Physical Review X · doi:10.1103/physrevx.8.021010 · Cited by 122
Self-citationGaussian boson sampling using threshold detectors
Quesada, N., Arrazola, J. M., & Killoran, N. (2018) · Physical Review A · doi:10.1103/physreva.98.062322 · Cited by 120
Closing the "quantum supremacy" gap
Liu, Y., Liu, X., Li, F., Fu, H., Yang, Y., Song, J., Zhao, P., Wang, Z., Peng, D., Chen, H., et al. (2021) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1145/3458817.3487399 · Cited by 120
Random quantum circuits are approximate unitary t -designs in depth O(nt5+o(1))
Haferkamp, J. (2022) · Quantum · doi:10.22331/q-2022-09-08-795 · Cited by 114
How many entries of a typical orthogonal matrix can be approximated by independent normals?
Jiang, T. (2006) · The Annals of Probability · doi:10.1214/009117906000000205 · Cited by 112
Theory of Quantum System Certification
Kliesch, M., & Roth, I. (2021) · Refubium (Universitätsbibliothek der Freien Universität Berlin) · doi:10.17169/refubium-32392 · Cited by 112
Simulating boson sampling in lossy architectures
García−Patrón, R., Renema, J. J., & Shchesnovich, V. S. (2019) · Quantum · doi:10.22331/q-2019-08-05-169 · Cited by 111
A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device
Brakerski, Z., Christiano, P. F., Mahadev, U., Vazirani, U. V., & Vidick, T. (2018) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2018.00038 · Cited by 111
Measuring the similarity of graphs with a Gaussian boson sampler
Schuld, M., Brádler, K., Israel, R., Su, D., & Gupt, B. (2020) · Physical Review A · doi:10.1103/physreva.101.032314 · Cited by 109
Random Quantum Circuits Anticoncentrate in Log Depth
Dalzell, A. M., Hunter-Jones, N., & Brandão, F. G. S. L. (2022) · PRX Quantum · doi:10.1103/prxquantum.3.010333 · Cited by 107
Random Bosonic States for Robust Quantum Metrology
Oszmaniec, M., Augusiak, R., Gogolin, C., Kołodyński, J., Acín, A., & Lewenstein, M. (2016) · Physical Review X · doi:10.1103/physrevx.6.041044 · Cited by 106
The permanent of a square matrix
Glynn, D. G. (2010) · European Journal of Combinatorics · doi:10.1016/j.ejc.2010.01.010 · Cited by 106
Quantum computational advantage via high-dimensional Gaussian boson sampling
Deshpande, A., Mehta, A., Vincent, T., Quesada, N., Hinsche, M., Ioannou, M., Madsen, L., Lavoie, J., Qi, H., Eisert, J., et al. (2022) · Science Advances · doi:10.1126/sciadv.abi7894 · Cited by 106
Self-citationPost hoc Verification of Quantum Computation
Fitzsimons, J. F., Hajdušek, M., & Morimae, T. (2018) · Physical Review Letters · doi:10.1103/physrevlett.120.040501 · Cited by 103
Gaussian boson sampling for perfect matchings of arbitrary graphs
Brádler, K., Dallaire-Demers, P.-L., Rebentrost, P., Su, D., & Weedbrook, C. (2018) · Physical Review A · doi:10.1103/physreva.98.032310 · Cited by 102
Statistical benchmark for BosonSampling
Walschaers, M., Kuipers, J., Urbina, J.-D., Mayer, K., Tichy, M. C., Richter, K., & Buchleitner, A. (2016) · New Journal of Physics · doi:10.1088/1367-2630/18/3/032001 · Cited by 102
Williams, V. V. (2015) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.ipec.2015.17 · Cited by 99
Reliable quantum certification of photonic state preparations
Aolita, L., Gogolin, C., Kliesch, M., & Eisert, J. (2015) · Nature Communications · doi:10.1038/ncomms9498 · Cited by 98
Self-citationInterference of identical particles from entanglement to boson-sampling
Tichy, M. C. (2014) · Journal of Physics B Atomic Molecular and Optical Physics · doi:10.1088/0953-4075/47/10/103001 · Cited by 98
Two Algorithmic Results for the Traveling Salesman Problem
Barvinok, A. I. (1996) · Mathematics of Operations Research · doi:10.1287/moor.21.1.65 · Cited by 97
What Can Quantum Optics Say about Computational Complexity Theory?
Rahimi-Keshari, S., Lund, A. P., & Ralph, T. C. (2015) · Physical Review Letters · doi:10.1103/physrevlett.114.060501 · Cited by 96
Quantum Supremacy for Simulating a Translation-Invariant Ising Spin Model
Gao, X., Wang, S.-T., & Duan, L. (2017) · Physical Review Letters · doi:10.1103/physrevlett.118.040502 · Cited by 96
An Automatic Inequality Prover and Instance Optimal Identity Testing
Valiant, G., & Valiant, P. (2017) · SIAM Journal on Computing · doi:10.1137/151002526 · Cited by 94
Permanents in linear optical networks
Scheel, S. (2004) · arXiv · doi:10.48550/arxiv.quant-ph/0406127 · Cited by 94
Factoring using $2n+2$ qubits with Toffoli based modular multiplication
Haner, T., Roetteler, M., & Svore, K. M. (2017) · Quantum Information and Computation · doi:10.26421/qic17.7-8-7 · Cited by 90
Classical simulation of photonic linear optics with lost particles
Oszmaniec, M., & Brod, D. J. (2018) · New Journal of Physics · doi:10.1088/1367-2630/aadfa8 · Cited by 89
General method for extracting the quantum efficiency of dispersive qubit readout in circuit QED
Bultink, C. C., Tarasinski, B., Haandbæk, N., Poletto, S., Haider, N., Michalak, D. J., Bruno, A., & DiCarlo, L. (2018) · Applied Physics Letters · doi:10.1063/1.5015954 · Cited by 89
How many qubits are needed for quantum computational supremacy?
Dalzell, A. M., Harrow, A. W., Koh, D. E., & La Placa, R. L. (2020) · Quantum · doi:10.22331/q-2020-05-11-264 · Cited by 88
The boundary for quantum advantage in Gaussian boson sampling
Bulmer, J. F. F., Bell, B. A., Chadwick, R. S., Jones, A. E., Moise, D., Rigazzi, A., Thorbecke, J., Haus, U.-U., Van Vaerenbergh, T., Patel, R. B., et al. (2022) · Science Advances · doi:10.1126/sciadv.abl9236 · Cited by 88
Regimes of Classical Simulability for Noisy Gaussian Boson Sampling
Qi, H., Brod, D. J., Quesada, N., & García-Patrón, R. (2020) · Physical Review Letters · doi:10.1103/physrevlett.124.100502 · Cited by 87
Verification of Many-Qubit States
Takeuchi, Y., & Morimae, T. (2018) · Physical Review X · doi:10.1103/physrevx.8.021060 · Cited by 87
Efficient parallelization of tensor network contraction for simulating quantum computation
Huang, C., Zhang, F., Newman, M., Ni, X., Ding, D., Cai, J., Gao, X., Wang, T., Wu, F., Zhang, G., et al. (2021) · Nature Computational Science · doi:10.1038/s43588-021-00119-7 · Cited by 86
Demonstration of quantum volume 64 on a superconducting quantum computing system
Jurcevic, P., Javadi-Abhari, A., Bishop, L. S., Lauer, I., Bogorin, D. F., Brink, M., Capelluto, L., Günlük, O., Itoko, T., Kanazawa, N., et al. (2021) · Quantum Science and Technology · doi:10.1088/2058-9565/abe519 · Cited by 85
Experimental statistical signature of many-body quantum interference
Giordani, T., Flamini, F., Pompili, M., Viggianiello, N., Spagnolo, N., Crespi, A., Osellame, R., Wiebe, N., Walschaers, M., Buchleitner, A., et al. (2018) · Nature Photonics · doi:10.1038/s41566-018-0097-4 · Cited by 83
Guo, C., Liu, Y., Xiong, M., Xue, S., Fu, X., Huang, A., Qiang, X., Xu, P., Liu, J., Zheng, S., et al. (2019) · Physical Review Letters · doi:10.1103/physrevlett.123.190501 · Cited by 82
Gupt, B., Izaac, J., & Quesada, N. (2019) · The Journal of Open Source Software · doi:10.21105/joss.01705 · Cited by 82
Determining acceptance possibility for a quantum computation is hard for the polynomial hierarchy
Fenner, S., Green, F., Homer, S., & Pruim, R. J. (1999) · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rspa.1999.0485 · Cited by 80
Certifying the Building Blocks of Quantum Computers from Bell’s Theorem
Sekatski, P., Bancal, J.-D., Wagner, S., & Sangouard, N. (2018) · Physical Review Letters · doi:10.1103/physrevlett.121.180505 · Cited by 78
The detectability lemma and quantum gap amplification
Aharonov, D., Arad, I., Landau, Z. A., & Vazirani, U. V. (2009) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1536414.1536472 · Cited by 77
Direct certification of a class of quantum simulations
Hangleiter, D., Kliesch, M., Schwarz, M., & Eisert, J. (2017) · Quantum Science and Technology · doi:10.1088/2058-9565/2/1/015004 · Cited by 77
Self-citationQuantum computing and polynomial equations over Z_2
Dawson, C. M., Haselgrove, H. L., Hines, A. P., Mortimer, D., Nielsen, M. A., & Osborne, T. J. (2005) · Quantum Information and Computation · doi:10.26421/qic5.2-2 · Cited by 77
BosonSampling with lost photons
Aaronson, S., & Brod, D. J. (2016) · Physical Review A · doi:10.1103/physreva.93.012335 · Cited by 76
Shchesnovich, V. S. (2014) · Physical Review A · doi:10.1103/physreva.89.022333 · Cited by 75
A Faster Hafnian Formula for Complex Matrices and Its Benchmarking on a Supercomputer
Björklund, A., Gupt, B., & Quesada, N. (2019) · ACM Journal of Experimental Algorithmics · doi:10.1145/3325111 · Cited by 74
Simulating realistic non-Gaussian state preparation
Quesada, N., Helt, L. G., Izaac, J., Arrazola, J. M., Shahrokhshahi, R., Myers, C. R., & Sabapathy, K. K. (2019) · Physical Review A · doi:10.1103/physreva.100.022341 · Cited by 73
A benchmark test of boson sampling on Tianhe-2 supercomputer
Wu, J., Liu, Y., Zhang, B., Jin, X., Wang, Y., Wang, H., & Yang, X. (2018) · National Science Review · doi:10.1093/nsr/nwy079 · Cited by 73
Liquid-state NMR simulations of quantum many-body problems
Negrevergne, C., Somma, R. D., Ortíz, G., Knill, E., & Laflamme, R. (2005) · Physical Review A · doi:10.1103/physreva.71.032344 · Cited by 71
Efficient Verification of Hypergraph States
Zhu, H., & Hayashi, M. (2019) · Physical Review Applied · doi:10.1103/physrevapplied.12.054047 · Cited by 71
Cai, J., Pavan, A., & Sivakumar, D. (1999) · Lecture notes in computer science · doi:10.1007/3-540-49116-3_8 · Cited by 70
Nonstabilizerness determining the hardness of direct fidelity estimation
Leone, L., Oliviero, S. F. E., & Hamma, A. (2023) · Physical Review A · doi:10.1103/physreva.107.022429 · Cited by 70
Hardness of Classically Simulating the One-Clean-Qubit Model
Morimae, T., Fujii, K., & Fitzsimons, J. F. (2014) · Physical Review Letters · doi:10.1103/physrevlett.112.130502 · Cited by 70
Impossibility of Classically Simulating One-Clean-Qubit Model with Multiplicative Error
Fujii, K., Kobayashi, H., Morimae, T., Nishimura, H., Tamate, S., & Tani, S. (2018) · Physical Review Letters · doi:10.1103/physrevlett.120.200502 · Cited by 67
A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
Linial, N., Samorodnitsky, A., & Wigderson, A. (1998) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/276698.276880 · Cited by 67
Boundaries of quantum supremacy via random circuit sampling
Zlokapa, A., Villalonga, B., Boixo, S., & Lidar, D. A. (2023) · npj Quantum Information · doi:10.1038/s41534-023-00703-x · Cited by 66
Fault-Tolerant Operation of a Quantum Error-Correction Code
Egan, L., Debroy, D. M., Noel, C., Risinger, A., Zhu, D., Biswas, D., Newman, M., Li, M., Brown, K. R., Cetina, M., et al. (2020) · arXiv · doi:10.48550/arxiv.2009.11482 · Cited by 65
Pan, F. P., Zhou, P., Li, S., & Zhang, P. (2020) · Physical Review Letters · doi:10.1103/physrevlett.125.060503 · Cited by 65
Improved upper bounds on the stabilizer rank of magic states
Qassim, H., Pashayan, H., & Gosset, D. (2021) · Quantum · doi:10.22331/q-2021-12-20-606 · Cited by 65
Computing the Permanent of (Some) Complex Matrices
Barvinok, A. I. (2015) · Foundations of Computational Mathematics · doi:10.1007/s10208-014-9243-7 · Cited by 64
Verification of hypergraph states
Morimae, T., Takeuchi, Y., & Hayashi, M. (2017) · Physical Review A · doi:10.1103/physreva.96.062321 · Cited by 63
Exact simulation of Gaussian boson sampling in polynomial space and exponential time
Quesada, N., & Arrazola, J. M. (2020) · Physical Review Research · doi:10.1103/physrevresearch.2.023005 · Cited by 63
Oszmaniec, M., Dangniam, N., Morales, M. E. S., & Zimborás, Z. (2022) · PRX Quantum · doi:10.1103/prxquantum.3.020328 · Cited by 63
Classically verifiable quantum advantage from a computational Bell test
Kahanamoku–Meyer, G. D., Choi, S., Vazirani, U. V., & Yao, N. Y. (2022) · Nature Physics · doi:10.1038/s41567-022-01643-7 · Cited by 62
Contracting projected entangled pair states is average-case hard
Haferkamp, J., Hangleiter, D., Eisert, J., & Gluza, M. (2020) · Physical Review Research · doi:10.1103/physrevresearch.2.013010 · Cited by 62
Self-citationQuantum approximate optimization with Gaussian boson sampling
Arrazola, J. M., Bromley, T. R., & Rebentrost, P. (2018) · Physical Review A · doi:10.1103/physreva.98.012322 · Cited by 61
Oracle separation of BQP and PH
Raz, R., & Tal, A. (2019) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3313276.3316315 · Cited by 61
Hamiltonian quantum cellular automata in one dimension
Nagaj, D., & Wocjan, P. (2008) · Physical Review A · doi:10.1103/physreva.78.032311 · Cited by 59
All Pure Fermionic Non-Gaussian States Are Magic States for Matchgate Computations
Hebenstreit, M., Jozsa, R., Kraus, B., Strelchuk, S., & Yoganathan, M. (2019) · Physical Review Letters · doi:10.1103/physrevlett.123.080503 · Cited by 59
The Complexity of Approximating complex-valued Ising and Tutte partition functions
Goldberg, L. A., & Guo, H. (2017) · Computational Complexity · doi:10.1007/s00037-017-0162-2 · Cited by 59
Efficient Verification of Hypergraph States
Zhu, H., & Hayashi, M. (2019) · Kölner Universitäts PublikationsServer (Universität zu Köln) · Cited by 59
Commuting quantum circuits and complexity of Ising partition functions
Fujii, K., & Morimae, T. (2017) · New Journal of Physics · doi:10.1088/1367-2630/aa5fdb · Cited by 58
Anticoncentration theorems for schemes showing a quantum speedup
Hangleiter, D., Bermejo-Vega, J., Schwarz, M., & Eisert, J. (2018) · Quantum · doi:10.22331/q-2018-05-22-65 · Cited by 58
Self-citationBoson sampling with Gaussian measurements
Chakhmakhchyan, L., & Cerf, N. J. (2017) · Physical Review A · doi:10.1103/physreva.96.032326 · Cited by 57
Average case complexity under the universal distribution equals worst-case complexity
Li, M., & Vitanyi, P. M. B. (1992) · Information Processing Letters · doi:10.1016/0020-0190(92)90138-l · Cited by 56
Direct certification of a class of quantum simulations
Hangleiter, D., Kliesch, M., Schwarz, M., & Eisert, J. (2017) · Refubium (Universitätsbibliothek der Freien Universität Berlin) · doi:10.17169/refubium-2421 · Cited by 56
Self-citationQuantum advantage of unitary Clifford circuits with magic state inputs
Yoganathan, M., Jozsa, R., & Strelchuk, S. (2019) · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rspa.2018.0427 · Cited by 55
Classical simulation of lossy boson sampling using matrix product operators
Oh, C., Noh, K., Fefferman, B., & Jiang, L. (2021) · Physical Review A · doi:10.1103/physreva.104.022407 · Cited by 55
Gurvits, & Samorodnitsky (2002) · Discrete & Computational Geometry · doi:10.1007/s00454-001-0083-2 · Cited by 55
Continuous-variable sampling from photon-added or photon-subtracted squeezed states
Chabaud, U., Douce, T., Markham, D., van Loock, P., Kashefi, E., & Ferrini, G. (2017) · Physical Review A · doi:10.1103/physreva.96.062307 · Cited by 55
Franck-Condon factors by counting perfect matchings of graphs with loops
Quesada, N. (2019) · The Journal of Chemical Physics · doi:10.1063/1.5086387 · Cited by 54
Quantum Simulators, Continuous-Time Automata, and Translationally Invariant Systems
Vollbrecht, K. G. H., & Cirac, J. I. (2008) · Physical Review Letters · doi:10.1103/physrevlett.100.010501 · Cited by 53
Dynamical Phase Transitions in Sampling Complexity
Deshpande, A., Fefferman, B., Tran, M. C., Foss‐Feig, M., & Gorshkov, A. V. (2018) · Physical Review Letters · doi:10.1103/physrevlett.121.030501 · Cited by 52
Noise and the Frontier of Quantum Supremacy
Bouland, A., Fefferman, B., Landau, Z. A., & Liu, Y. (2022) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs52979.2021.00127 · Cited by 52
Point processes with Gaussian boson sampling
Jahangiri, S., Arrazola, J. M., Quesada, N., & Killoran, N. (2020) · Physical review. E · doi:10.1103/physreve.101.022134 · Cited by 51
BosonSampling is robust against small errors in the network matrix
Arkhipov, A. (2015) · Physical Review A · doi:10.1103/physreva.92.062326 · Cited by 49
Fidelity Witnesses for Fermionic Quantum Simulations
Gluza, M., Kliesch, M., Eisert, J., & Aolita, L. (2018) · Physical Review Letters · doi:10.1103/physrevlett.120.190501 · Cited by 49
Self-citationUnbiased simulation of near-Clifford quantum circuits
Bennink, R. S., Ferragut, E. M., Humble, T. S., Laska, J. A., Nutaro, J. J., Pleszkoch, M. G., & Pooser, R. C. (2017) · Physical Review A · doi:10.1103/physreva.95.062337 · Cited by 49
Beating Brute Force for Systems of Polynomial Equations over Finite Fields
Lokshtanov, D., Paturi, R., Tamaki, S., Williams, R., & Yu, H. (2017) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611974782.143 · Cited by 49
Quadratic Speed-Up for Simulating Gaussian Boson Sampling
Quesada, N., Chadwick, R. S., Bell, B. A., Arrazola, J. M., Vincent, T., Qi, H., & García−Patrón, R. (2022) · PRX Quantum · doi:10.1103/prxquantum.3.010306 · Cited by 48
Anticoncentration theorems for schemes showing a quantum speedup
Hangleiter, D., Bermejo-Vega, J., Schwarz, M., & Eisert, J. (2018) · Refubium (Universitätsbibliothek der Freien Universität Berlin) · doi:10.17169/refubium-250 · Cited by 48
Self-citationTight Bounds on the Convergence of Noisy Random Circuits to the Uniform Distribution
Deshpande, A., Niroula, P., Shtanko, O., Gorshkov, A. V., Fefferman, B., & Gullans, M. J. (2022) · PRX Quantum · doi:10.1103/prxquantum.3.040329 · Cited by 48
Bounds for polynomials with a unit discrete norm
Rakhmanov, E. A. (2007) · Annals of Mathematics · doi:10.4007/annals.2007.165.55 · Cited by 48
Classical simulation of Gaussian quantum circuits with non-Gaussian input states
Chabaud, U., Ferrini, G., Grosshans, F., & Markham, D. (2021) · Physical Review Research · doi:10.1103/physrevresearch.3.033018 · Cited by 47
Morimae, T. (2017) · Physical Review A · doi:10.1103/physreva.96.040302 · Cited by 46
Sample Complexity of Device-Independently Certified “Quantum Supremacy”
Hangleiter, D., Kliesch, M., Eisert, J., & Gogolin, C. (2019) · Physical Review Letters · doi:10.1103/physrevlett.122.210502 · Cited by 46
Self-citationExplicit Lower Bounds on Strong Quantum Simulation
Huang, C., Newman, M., & Szegedy, M. (2020) · IEEE Transactions on Information Theory · doi:10.1109/tit.2020.3004427 · Cited by 46
Quantum simulation of thermodynamics in an integrated quantum photonic processor
Somhorst, F. H. B., van der Meer, R., Anguita, M. C., Schadow, R., Snijders, H., de Goede, M., Kassenberg, B., Venderbosch, P., Taballione, C., Epping, J. P., et al. (2023) · Nature Communications · doi:10.1038/s41467-023-38413-9 · Cited by 46
Self-citationThe Complexity of Bipartite Gaussian Boson Sampling
Grier, D., Brod, D. J., Arrazola, J. M., Alonso, M. B. D. A., & Quesada, N. (2022) · Quantum · doi:10.22331/q-2022-11-28-863 · Cited by 46
Validating quantum-classical programming models with tensor network simulations
McCaskey, A., Dumitrescu, E., Chen, M., Lyakh, D. I., & Humble, T. S. (2018) · PLoS ONE · doi:10.1371/journal.pone.0206704 · Cited by 45
Classical Simulation of Boson Sampling Based on Graph Structure
Oh, C., Lim, Y., Fefferman, B., & Jiang, L. (2022) · Physical Review Letters · doi:10.1103/physrevlett.128.190501 · Cited by 44
A Simple Protocol for Certifying Graph States and Applications in Quantum Networks
Markham, D., & Krause, A. (2020) · Cryptography · doi:10.3390/cryptography4010003 · Cited by 43
Arkhipov, A., & Kuperberg, G. (2012) · Geometry and topology monographs · doi:10.2140/gtm.2012.18.1 · Cited by 42
Distributed Computing and Cryptography
Joan Feigenbaum, A., & Merritt, M. (1991) · DIMACS series in discrete mathematics and theoretical computer science · doi:10.1090/dimacs/002 · Cited by 42
Benchmarking of Gaussian boson sampling using two-point correlators
Phillips, D. S., Walschaers, M., Renema, J. J., Walmsley, I. A., Treps, N., & Sperling, J. (2019) · Physical Review A · doi:10.1103/physreva.99.023836 · Cited by 42
Closing Gaps of a Quantum Advantage with Short-Time Hamiltonian Dynamics
Haferkamp, J., Hangleiter, D., Bouland, A., Fefferman, B., Eisert, J., & Bermejo-Vega, J. (2020) · Physical Review Letters · doi:10.1103/physrevlett.125.250501 · Cited by 41
Self-citationPolynomial simulations of decohered quantum computers
Aharonov, D., & Ben-Or, M. (2002) · Proceedings of 37th Conference on Foundations of Computer Science · doi:10.1109/sfcs.1996.548463 · Cited by 41
Quantum algorithms for classical lattice models
De las Cuevas, G., Dür, W., Van den Nest, M., & Martin-Delgado, M. A. (2011) · New Journal of Physics · doi:10.1088/1367-2630/13/9/093021 · Cited by 40
Approximating vibronic spectroscopy with imperfect quantum optics
Clements, W. R., Renema, J. J., Eckstein, A., Valido, A. A., Lita, A., Gerrits, T., Nam, S. W., Kolthammer, W. S., Huh, J., & Walmsley, I. A. (2018) · Journal of Physics B: Atomic, Molecular and Optical Physics · doi:10.1088/1361-6455/aaf031 · Cited by 39
Generating a statet-design by diagonal quantum circuits
Nakata, Y., Koashi, M., & Murao, M. (2014) · New Journal of Physics · doi:10.1088/1367-2630/16/5/053043 · Cited by 39
Classically simulating near-term partially-distinguishable and lossy boson sampling
Moylett, A. E., García−Patrón, R., Renema, J. J., & Turner, P. S. (2019) · Quantum Science and Technology · doi:10.1088/2058-9565/ab5555 · Cited by 38
Compressive Gate Set Tomography
Brieger, R., Roth, I., & Kliesch, M. (2023) · PRX Quantum · doi:10.1103/prxquantum.4.010325 · Cited by 38
Efficient verification of boson sampling
Chabaud, U., Grosshans, F., Kashefi, E., & Markham, D. (2021) · Quantum · doi:10.22331/q-2021-11-15-578 · Cited by 37
Simulating complex networks in phase space: Gaussian boson sampling
Drummond, P. D., Opanchuk, B., Dellios, A. S., & Reid, M. D. (2022) · Physical Review A · doi:10.1103/physreva.105.012427 · Cited by 36
Quantum machine learning with adaptive linear optics
Chabaud, U., Markham, D., & Sohbi, A. (2021) · Quantum · doi:10.22331/q-2021-07-05-496 · Cited by 36
Quantum advantage of unitary Clifford circuits with magic state inputs
Yoganathan, M., Jozsa, R., Strelchuk, S., et al. (2019) · Cambridge University Engineering Department Publications Database · Cited by 35
Noise in boson sampling and the threshold of efficient classical simulatability
Shchesnovich, V. S. (2019) · Physical Review A · doi:10.1103/physreva.100.012340 · Cited by 34
Quantum circuits and low-degree polynomials over F 2
Montanaro, A. (2017) · Journal of Physics A Mathematical and Theoretical · doi:10.1088/1751-8121/aa565f · Cited by 34
Simulability of partially distinguishable superposition and Gaussian boson sampling
Renema, J. J. (2020) · Physical Review A · doi:10.1103/physreva.101.063840 · Cited by 34
Dynamical structure factors of dynamical quantum simulators
Baez, M. L., Goihl, M., Haferkamp, J., Bermejo-Vega, J., Gluza, M., & Eisert, J. (2020) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.2006103117 · Cited by 34
Self-citationTraining Gaussian boson sampling distributions
Banchi, L., Quesada, N., & Arrazola, J. M. (2020) · Physical Review A · doi:10.1103/physreva.102.012417 · Cited by 33
Quantum-Teleportation-Inspired Algorithm for Sampling Large Random Quantum Circuits
Chen, M.-C., Li, R., Gan, L., Zhu, X., Yang, G., Lu, C., & Pan, J.-W. (2020) · Physical Review Letters · doi:10.1103/physrevlett.124.080502 · Cited by 33
On the permanent of random Bernoulli matrices
Tao, T., & Vu, V. (2008) · Advances in Mathematics · doi:10.1016/j.aim.2008.09.006 · Cited by 32
Verifying Random Quantum Circuits with Arbitrary Geometry Using Tensor Network States Algorithm
Guo, C., Zhao, Y., & Huang, H.-L. (2021) · Physical Review Letters · doi:10.1103/physrevlett.126.070502 · Cited by 31
Simple proof of the detectability lemma and spectral gap amplification
Anshu, A., Arad, I., & Vidick, T. (2016) · Physical review. B./Physical review. B · doi:10.1103/physrevb.93.205142 · Cited by 31
Miller, J., Sanders, S. K., & Miyake, A. (2017) · Physical Review A · doi:10.1103/physreva.96.062320 · Cited by 29
Approximating vibronic spectroscopy with imperfect quantum optics
Valido, A. A., Clements, W. R., Renema, J. J., Eckstein, A., Lita, A. E., Gerrits, T., Nam, S. W., Kolthammer, W. S., Huh, J., & Walmsley, I. A. (2018) · BURJC Digital (King Juan Carlos University) · doi:10.1088/1361-6455/aaf03 · Cited by 29
Generalized concurrence in boson sampling
Chin, S., & Huh, J. (2018) · Scientific Reports · doi:10.1038/s41598-018-24302-5 · Cited by 28
Muraleedharan, G., Miyake, A., & Deutsch, I. (2019) · New Journal of Physics · doi:10.1088/1367-2630/ab0610 · Cited by 28
Verifying commuting quantum computations via fidelity estimation of weighted graph states
Hayashi, M., & Takeuchi, Y. (2019) · New Journal of Physics · doi:10.1088/1367-2630/ab3d88 · Cited by 28
Exact boson sampling using Gaussian continuous-variable measurements
Lund, A. P., Rahimi-Keshari, S., & Ralph, T. C. (2017) · Physical Review A · doi:10.1103/physreva.96.022301 · Cited by 27
Universal bound on sampling bosons in linear optics and its computational implications
Yung, M., Gao, X., & Huh, J. (2019) · National Science Review · doi:10.1093/nsr/nwz048 · Cited by 27
Universal two-body-Hamiltonian quantum computing
Nagaj, D. (2012) · Physical Review A · doi:10.1103/physreva.85.032330 · Cited by 26
Classical benchmarking of Gaussian Boson Sampling on the Titan supercomputer
Gupt, B., Arrazola, J. M., Quesada, N., & Bromley, T. R. (2020) · Quantum Information Processing · doi:10.1007/s11128-020-02713-6 · Cited by 26
Shchesnovich, V. S. (2013) · International Journal of Quantum Information · doi:10.1142/s0219749913500457 · Cited by 26
Quantum supremacy and hardness of estimating output probabilities of quantum circuits
Kondo, Y., Mori, R., & Movassagh, R. (2022) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs52979.2021.00126 · Cited by 26
Efficient computation of permanents, with applications to Boson sampling and random matrices
Lundow, P. H., & Markström, K. (2022) · Journal of Computational Physics · doi:10.1016/j.jcp.2022.110990 · Cited by 25
Complexity Phase Diagram for Interacting and Long-Range Bosonic Hamiltonians
Maskara, N., Deshpande, A., Ehrenberg, A., Tran, M. C., Fefferman, B., & Gorshkov, A. V. (2022) · Physical Review Letters · doi:10.1103/physrevlett.129.150604 · Cited by 25
Counting Perfect Matchings as Fast as Ryser∗Preprint
(2016) · Cited by 25
Depth-efficient proofs of quantumness
Liu, Z., & Gheorghiu, A. (2022) · Quantum · doi:10.22331/q-2022-09-19-807 · Cited by 23
Approximating the Permanent of a Random Matrix with Vanishing Mean
Eldar, L., & Mehraban, S. A. (2018) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2018.00012 · Cited by 22
Cryptographic one-way function based on boson sampling
Nikolopoulos, G. M. (2019) · Quantum Information Processing · doi:10.1007/s11128-019-2372-9 · Cited by 21
Distinguishing noisy boson sampling from classical simulations
Shchesnovich, V. S. (2021) · Quantum · doi:10.22331/q-2021-03-29-423 · Cited by 21
Randomized benchmarking under different gate sets
Boone, K., Carignan-Dugas, A., Wallman, J. J., & Emerson, J. (2019) · Physical Review A · doi:10.1103/physreva.99.032329 · Cited by 20
Approximating permanents and hafnians
Barvinok, A. I. (2017) · Discrete Analysis · doi:10.19086/da.1244 · Cited by 20
Simple heuristics for efficient parallel tensor contraction and quantum circuit simulation
Schutski, R., Khakhulin, T., Oseledets, I. V., & Kolmakov, D. (2020) · Physical Review A · doi:10.1103/physreva.102.062614 · Cited by 20
Experimental Demonstration of Gaussian Boson Sampling with Displacement
Thekkadath, G., Sempere-Llagostera, S., Bell, B. A., Patel, R. B., Kim, M. S., & Walmsley, I. A. (2022) · PRX Quantum · doi:10.1103/prxquantum.3.020336 · Cited by 19
Self-Consistent Calibration of Quantum-Gate Sets
Cerfontaine, P., Otten, R., & Bluhm, H. (2020) · RWTH Publications (RWTH Aachen) · Cited by 18
Test of Quantumness with Small-Depth Quantum CircuitsPreprint
Hirahara, S., & Gall, F. L. (2021) · arXiv (Cornell University) · doi:10.4230/lipics.mfcs.2021.59 · Cited by 18
Analysis of circuit imperfections in BosonSampling
Leverrier, A., & Garcia-Patron, R. (2015) · Quantum Information and Computation · doi:10.26421/qic15.5-6-8 · Cited by 17
Self-Consistent Calibration of Quantum-Gate Sets
Cerfontaine, P., Otten, R., & Bluhm, H. (2020) · Physical Review Applied · doi:10.1103/physrevapplied.13.044071 · Cited by 17
The entries of circular orthogonal ensembles
Jiang, T. (2009) · Journal of Mathematical Physics · doi:10.1063/1.3152217 · Cited by 16
Analog Quantum Simulation of Non-Condon Effects in Molecular Spectroscopy
Jnane, H., Sawaya, N. P. D., Peropadre, B., Aspuru‐Guzik, A., García−Patrón, R., & Huh, J. (2021) · ACS Photonics · doi:10.1021/acsphotonics.1c00059 · Cited by 16
Nonadaptive fault-tolerant verification of quantum supremacy with noise
Kapourniotis, T., & Datta, A. (2019) · Quantum · doi:10.22331/q-2019-07-12-164 · Cited by 15
Validating and certifying stabilizer states
Kalev, A., Kyrillidis, A., & Linke, N. M. (2019) · Physical Review A · doi:10.1103/physreva.99.042337 · Cited by 15
Quantum advantage from energy measurements of many-body quantum systems
Novo, L., Bermejo-Vega, J., & García−Patrón, R. (2021) · Quantum · doi:10.22331/q-2021-06-02-465 · Cited by 14
Huang, Z., Rohde, P. P., Berry, D. W., Kok, P., Dowling, J. P., & Lupo, C. (2021) · Quantum · doi:10.22331/q-2021-04-28-447 · Cited by 14
Fine-grained quantum computational supremacy
Morimae, T., & Tamaki, S. (2019) · Quantum Information and Computation · doi:10.26421/qic19.13-14-2 · Cited by 14
Statistical Aspects of the Quantum Supremacy Demonstration
Rinott, Y., Shoham, T., & Kalai, G. (2022) · Statistical Science · doi:10.1214/21-sts836 · Cited by 11
List Decoding in Average-Case Complexity and Pseudorandomness
Guruswami, V. (2006) · IEEE Information Theory Workshop (ITW) · doi:10.1109/itw.2006.1633776 · Cited by 11
Aaghabali, M., Akbari, S., Friedland, S., Markström, K., & Tajfirouz, Z. (2014) · European Journal of Combinatorics · doi:10.1016/j.ejc.2014.11.001 · Cited by 9
Classical simulation of boson sampling with sparse output
Roga, W., & Takeoka, M. (2020) · Scientific Reports · doi:10.1038/s41598-020-71892-0 · Cited by 9
Fault-tolerant quantum speedup from constant depth quantum circuits
Mezher, R., Ghalbouni, J., Dgheim, J., & Markham, D. (2020) · Physical Review Research · doi:10.1103/physrevresearch.2.033444 · Cited by 8
Robust Polynomial Regression up to the Information Theoretic Limit
Kane, D. M., Karmalkar, S., & Price, E. (2017) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2017.43 · Cited by 8
Computing permanents of complex diagonally dominant matrices and tensors
Barvinok, A. I. (2019) · Israel Journal of Mathematics · doi:10.1007/s11856-019-1896-0 · Cited by 8
A game of quantum advantage: linking verification and simulation
França, D. S., & García−Patrón, R. (2022) · Quantum · doi:10.22331/q-2022-06-30-753 · Cited by 7
Efficient verification of anticoncentrated quantum states
Bennink, R. S. (2021) · npj Quantum Information · doi:10.1038/s41534-021-00455-6 · Cited by 7
Multimode metrology via scattershot sampling
Guanzon, J. J., Lund, A. P., & Ralph, T. C. (2021) · Physical Review A · doi:10.1103/physreva.104.032607 · Cited by 4
Fault-tolerant quantum data locking
Huang, Z., Kok, P., & Lupo, C. (2021) · Physical Review A · doi:10.1103/physreva.103.052611 · Cited by 4
Gaussian phase sensitivity of boson-sampling-inspired strategies
Valido, A. A., & García‐Ripoll, J. J. (2021) · Physical Review A · doi:10.1103/physreva.103.032613 · Cited by 2
Flagged first, then by citations
8 of the 377 references couldn’t be matched to a known paper.
Research works printed but not linked: 13
- 10.4086/toc.2013.v009a004 · DOI
- Aaronson, S., 2017, Proceeding of the 32nd Computational Complexity Conference (CCC 2017), Riga, 2017
- Barak, B., 2021, Proceedings of the 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), 2021
- 10.1002/(SICI)1098-2418(1999010)14:1<29::AID-RSA2>3.0.CO;2-X · DOI
- Bernstein, E., 1993, Proceedings of the 25th Annual ACM Symposium on the Theory of Computing (STOC ’93), San Diego, 1993
- Björklund, A., 2012, Proceedings of the 2012 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’12), Kyoto, 2012, 10.1137/1.9781611973099.73 · DOI
- Bouland, A., 2018, Proceedings of the 33rd Computational Complexity Conference (CCC 2018), San Diego, 2018
- Clifford, P., 2018, Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’18), New Orleans, 2018, 10.1137/1.9781611975031.10 · DOI
- de Finetti, B., 1937, Ann. Inst. Henri Poincaré, 7, 1
- 10.4086/toc.2015.v011a006 · DOI
- 10.1126/science.abi8378 · DOI
- 10.1038/s41534-018-0113-z · DOI
- 10.1038/s41534-018-0113-z · DOI
Cited by
Sorted by citations
Deng, Y., Gu, Y.-C., Liu, H.-L., Gong, S.-Q., Su, H., Zhang, Z.-J., Tang, H., Jia, M.-H., Xu, J., Chen, M.-C., et al. (2023) · Physical Review Letters · doi:10.1103/physrevlett.131.150601 · Cited by 176
Introduction to Haar Measure Tools in Quantum Information: A Beginner's Tutorial
Mele, A. A. (2024) · Quantum · doi:10.22331/q-2024-05-08-1340 · Cited by 237
Towards provably efficient quantum algorithms for large-scale machine-learning models
Liu, J., Liu, M., Liu, J.-P., Ye, Z., Wang, Y., Alexeev, Y., Eisert, J., & Jiang, L. (2024) · Nature Communications · doi:10.1038/s41467-023-43957-x · Cited by 117
Self-citationUnderstanding quantum machine learning also requires rethinking generalization
Gil-Fuster, E., Eisert, J., & Bravo-Prieto, C. (2024) · Nature Communications · doi:10.1038/s41467-024-45882-z · Cited by 109
Self-citationBenchmarking quantum computers
Proctor, T. J., Young, K. C., Baczewski, A., & Blume-Kohout, R. (2025) · Nature Reviews Physics · doi:10.1038/s42254-024-00796-z · Cited by 116
Metadata
- Authors
- Hangleiter, D., & Eisert, J.
- Affiliations
- National Institute of Standards and Technology (US)
- Corresponding author
- Hangleiter, Dominik
- Venue
- Reviews of Modern Physics
- Publisher
- American Physical Society (APS)
- Published
- 2023-07-20
- Volume
- 95
- Issue
- 3
- ISSN
- 0034-6861 (ISSN-L)
- 1539-0756
- OpenAlex
- W4384935381
- Cited by
- 145
- References
- 377
- Citations by year
- 2026: 29 · 2025: 66 · 2024: 36 · 2023: 12
- FWCI
- 12.66
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Licence
- Locations
- Reviews of Modern Physics (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- Refubium (Universitätsbibliothek der Freien Universität Berlin) (submittedVersion)
- HZB Repository (Helmholtz-Zentrum Berlin für Materialien und Energie GmbH (HZB)) (submittedVersion)
- Fraunhofer-Publica (Fraunhofer-Gesellschaft) (submittedVersion)
- arXiv (Cornell University)
- Universitätsbibliothek der FU Berlin Hochschulschriftenstelle u. Dokumentenserver
- Funders
- U.S. Department of Defense
- Simons Institute for the Theory of Computing, University of California Berkeley
- Deutsche Forschungsgemeinschaft (CRC 183, EI 519/21-1)
- Bundesministerium für Bildung und Forschung
- QuantERA
- Einstein Stiftung Berlin
- Horizon 2020 Framework Programme (817482)
- German Federal Ministry of Economics and Climate Protection
- Munich Quantum Valley
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Mechanics and Applications
- Keywords
- quantum advantage, quantum measurement, probability distributions
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
