The DOI matches its Crossref record; 58 of the 58 references it cites were found in a registry or an index.
Achieving quantum supremacy with sparse and noisy commuting quantum computations
Open accessAbstract
The class of commuting quantum circuits known as IQP (instantaneous quantum polynomial-time) has been shown to be hard to simulate classically, assuming certain complexity-theoretic conjectures. Here we study the power of IQP circuits in the presence of physically motivated constraints. First, we show that there is a family of sparse IQP circuits that can be implemented on a square lattice of n qubits in depth O(sqrt(n) log n), and which is likely hard to simulate classically. Next, we show that, if an arbitrarily small constant amount of noise is applied to each qubit at the end of any IQP circuit whose output probability distribution is sufficiently anticoncentrated, there is a polynomial-time classical algorithm that simulates sampling from the resulting distribution, up to constant accuracy in total variation distance. However, we show that purely classical error-correction techniques can be used to design IQP circuits which remain hard to simulate classically, even in the presence of arbitrary amounts of noise of this form. These results demonstrate the challenges faced by experiments designed to demonstrate quantum supremacy over classical computation, and how these challenges can be overcome.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Figures
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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?
The source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“the bitstring distribution of IQP circuits with randomly applied {CCZ, CZ, Z} gates (random degree-3 polynomials) is known to be classically hard to simulate20,101.”
From Logical quantum processor based on reconfigurable atom arrays (2024) · cites this paper as [101]
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Diestel, R. (1997) · Cited by 5,082
Richardson, T., & Urbanke, R. (2008) · Cambridge University Press eBooks · doi:10.1017/cbo9780511791338 · Cited by 2,271 · cited 1×
“Explicit codes which almost achieve Shannon’s nonconstructive bound, and have efficient decoding algorithms, are known; for example, low-density parity check codes and certain concatenated codes [35].”
BackgroundA Quantum Approximate Optimization Algorithm
Farhi, E., Goldstone, J., & Gutmann, S. (2014) · arXiv · doi:10.48550/arxiv.1411.4028 · Cited by 1,789 · cited 1×
“pproximate hs|H⊗n|ψiup to very high accuracy. One particular case which is tempting to address is the \quantum approximate optimization algorithm" (QAOA) invented by Farhi, Goldstone and Gutmann [18,19]. This algorithm has been proposed to oer a route towards proving quantum supremacy [20]. In the simplest versio…”
MethodOn the Power of Quantum Computation
Simon, D. R. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539796298637 · Cited by 1,295
Characterizing quantum supremacy in near-term devices
Boixo, S., Isakov, S. V., Smelyanskiy, V. N., Babbush, R., Ding, N., Jiang, Z., Bremner, M. J., Martinis, J. M., & Neven, H. (2018) · Nature Physics · doi:10.1038/s41567-018-0124-x · Cited by 1,175 · cited 2×
“notion in itself would be sucient for a complexity-theoretic hardness argument, it is thus plausible that our results could be extended to noncommuting circuits. It should also be noted that recent [7] numerical evidence suggests that anticoncentration can be achieved on a square lattice with circuits of depth O( √ n)…”
BackgroundSelf-citationConcentration of Measure for the Analysis of Randomized Algorithms
Dubhashi, D. P., & Panconesi, A. (2009) · Cambridge University Press eBooks · doi:10.1017/cbo9780511581274 · Cited by 945 · cited 2×
“The degree of v1 is the number of edges incident to v1; each edge is present with probability p; so by a Chernoff bound argument [17]”
BackgroundMethodO'Donnell, R. (2014) · Cambridge University Press eBooks · doi:10.1017/cbo9781139814782 · Cited by 932
The computational complexity of linear optics
Aaronson, S., & Arkhipov, A. (2011) · Proceedings of the forty-third annual ACM symposium on Theory of computing · doi:10.1145/1993636.1993682 · Cited by 874 · cited 6×
“On the other hand, it was shown by Arkhipov [3] (see also [39]) that if = o(1/n2), the `1 distance between the noisy distribution and the original distribution is o(1).”
MethodResultInfluentialDiestel, R. (2010) · Graduate Texts in Mathematics · doi:10.1007/978-3-642-14279-6 · Cited by 714
PP is as Hard as the Polynomial-Time Hierarchy
Toda, S. (1991) · SIAM Journal on Computing · doi:10.1137/0220053 · Cited by 665 · cited 1×
“If this conjecture holds, then the existence of such a classical sampler would imply collapse of the polynomial hierarchy [42], a complexity-theoretic consequence considered very unlikely; see [11] for more.”
Background
Cited by
Supervised learning with quantum-enhanced feature spaces
Havlíček, V., Córcoles, A. D., Temme, K., Harrow, A. W., Kandala, A., Chow, J. M., & Gambetta, J. M. (2019) · Nature · doi:10.1038/s41586-019-0980-2 · Cited by 2,572
“There are convincing arguments that indicate that even very sim-∗ ple circuits are hard to simulate by classical computational means [12, 13].”
BackgroundCharacterizing quantum supremacy in near-term devices
Boixo, S., Isakov, S. V., Smelyanskiy, V. N., Babbush, R., Ding, N., Jiang, Z., Bremner, M. J., Martinis, J. M., & Neven, H. (2018) · Nature Physics · doi:10.1038/s41567-018-0124-x · Cited by 1,175
Self-citationLogical quantum processor based on reconfigurable atom arrays
Bluvstein, D., Evered, S. J., Geim, A. A., Li, S. H., Zhou, H., Manovitz, T., Ebadi, S., Cain, M., Kalinowski, M., Hangleiter, D., et al. (2024) · Nature · doi:10.1038/s41586-023-06927-3 · Cited by 1,119
“The IQP circuits are a good setting for quantum-advantage-type experiments, as the bitstring distribution of IQP circuits with randomly applied {CCZ, CZ, Z} gates (random degree-3 polynomials) is known to be classically hard to simulate 20,101 .”
MethodMachine learning & artificial intelligence in the quantum domain: a review of recent progress
Dunjko, V., & Briegel, H. J. (2018) · Reports on Progress in Physics · doi:10.1088/1361-6633/aab406 · Cited by 1,055
Quantum computational supremacy
Harrow, A. W., & Montanaro, A. (2017) · Nature · doi:10.1038/nature23458 · Cited by 702
Self-citationFrom the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
Hadfield, S., Wang, Z., O’Gorman, B., Rieffel, E. G., Venturelli, D., & Biswas, R. (2019) · Algorithms · doi:10.3390/a12020034 · Cited by 772
“Results for IQP circuits, whose close structural similarities with QAOA circuits have already provided insights [17], and whose advanced status with respect to error analysis and fault tolerance [47, 48] are likely to prove especially useful.”
BackgroundA Survey on quantum computing technology
Gyongyosi, L., & Imre, S. (2019) · Computer Science Review · doi:10.1016/j.cosrev.2018.11.002 · Cited by 646
Quantum computing: A taxonomy, systematic review and future directions
Gill, S. S., Kumar, A., Singh, H., Singh, M., Kaur, K., Usman, M., & Buyya, R. (2022) · Software: Practice and Experience · doi:10.1002/spe.3039 · Cited by 476
“Quantum gates can be deployed in various arrangements such as shallow circuits [21], and instantaneous quantum polynomial-time circuit [22] depending upon the applications.”
BackgroundA blueprint for demonstrating quantum supremacy with superconducting qubits
Neill, C., Roushan, P., Kechedzhi, K., Boixo, S., Isakov, S. V., Smelyanskiy, V., Megrant, A., Chiaro, B., Dunsworth, A., Arya, K., et al. (2018) · Science · doi:10.1126/science.aao4309 · Cited by 458
Quantum advantage with shallow circuits
Bravyi, S., Gosset, D., & König, R. (2018) · Science · doi:10.1126/science.aar3106 · Cited by 406
Strawberry Fields: A Software Platform for Photonic Quantum Computing
Killoran, N., Izaac, J., Quesada, N., Bergholm, V., Amy, M., & Weedbrook, C. (2019) · Quantum · doi:10.22331/q-2019-03-11-129 · Cited by 323
Expressive power of parametrized quantum circuits
Du, Y., Hsieh, M.-H., Liu, T., & Tao, D. (2020) · Physical Review Research · doi:10.1103/physrevresearch.2.033125 · Cited by 318
On the complexity and verification of quantum random circuit sampling
Bouland, A., Fefferman, B., Nirkhe, C., & Vazirani, U. (2019) · Nature Physics · doi:10.1038/s41567-018-0318-2 · Cited by 287
Rényi Entropies from Random Quenches in Atomic Hubbard and Spin Models
Elben, A., Vermersch, B., Dalmonte, M., Cirac, J. I., & Zoller, P. (2018) · Physical Review Letters · doi:10.1103/physrevlett.120.050406 · Cited by 257
Limitations of optimization algorithms on noisy quantum devices
Stilck França, D., & García-Patrón, R. (2021) · Nature Physics · doi:10.1038/s41567-021-01356-3 · Cited by 232
Variational Quantum Monte Carlo Method with a Neural-Network Ansatz for Open Quantum Systems
Nagy, A., & Savona, V. (2019) · Physical Review Letters · doi:10.1103/physrevlett.122.250501 · Cited by 227
Challenges and Opportunities of Near-Term Quantum Computing Systems
Corcoles, A. D., Kandala, A., Javadi-Abhari, A., McClure, D. T., Cross, A. W., Temme, K., Nation, P. D., Steffen, M., & Gambetta, J. M. (2020) · Proceedings of the IEEE · doi:10.1109/jproc.2019.2954005 · Cited by 203
“If the quantum algorithm can be efficiently simulated on classical hardware [112]–[118], it cannot provide a computational advantage.”
BackgroundQuantum sampling problems, BosonSampling and quantum supremacy
Lund, A. P., Bremner, M. J., & Ralph, T. C. (2017) · npj Quantum Information · doi:10.1038/s41534-017-0018-2 · Cited by 183
“Intriguingly, this class of errors can be corrected without the full arsenal of fault tolerance, retrieving supremacy for additive error approximations requiring only operations from IQP albeit with a cost in terms of gates and qubits.(49) This suggests that unambiguous quantum supremacy may yet require error correcti…”
BackgroundInfluentialSelf-citationClassical boson sampling algorithms with superior performance to near-term experiments
Neville, A., Sparrow, C., Clifford, R., Johnston, E., Birchall, P. M., Montanaro, A., & Laing, A. (2017) · Nature Physics · doi:10.1038/nphys4270 · Cited by 178
“For example, it was shown in [44] that a class of quantum circuits whose output probability distributions are likely to be hard to sample from classically becomes easy in the presence of noise.”
BackgroundSelf-citationVillalonga, B., Boixo, S., Nelson, B. C., Henze, C. E., Rieffel, E. G., Biswas, R., & Mandrà, S. (2019) · npj Quantum Information · doi:10.1038/s41534-019-0196-1 · Cited by 219
The Born supremacy: quantum advantage and training of an Ising Born machine
Coyle, B., Mills, D., Danos, V., & Kashefi, E. (2020) · npj Quantum Information · doi:10.1038/s41534-020-00288-9 · Cited by 155
Establishing the quantum supremacy frontier with a 281 Pflop/s simulation
Villalonga, B., Lyakh, D. I., Boixo, S., Neven, H., Humble, T. S., Biswas, R., Rieffel, E. G., Ho, A., & Mandrà, S. (2020) · Quantum Science and Technology · doi:10.1088/2058-9565/ab7eeb · Cited by 200
“This proposal also counts with the strongest theoretical support in complexity theory for an exponential separation between classical and quantum computation [19, 37].”
BackgroundComputational advantage of quantum random sampling
Hangleiter, D., & Eisert, J. (2023) · Reviews of Modern Physics · doi:10.1103/revmodphys.95.035001 · Cited by 145
Quantum advantage with noisy shallow circuits
Bravyi, S., Gosset, D., König, R., & Tomamichel, M. (2020) · Nature Physics · doi:10.1038/s41567-020-0948-z · Cited by 144
Efficient Classical Simulation of Random Shallow 2D Quantum Circuits
Napp, J. C., Placa, R. L. L., Dalzell, A. M., Brandão, F. G. S. L., & Harrow, A. W. (2022) · Physical Review X · doi:10.1103/physrevx.12.021021 · Cited by 193
“A long line of work has shown that it is worst-case hard to either sample from the output distributions of quantum circuits or compute their output probabilities with an exponentially small error [1,5,6,8,9,50,51].”
BackgroundTheory of Quantum System Certification
Kliesch, M., & Roth, I. (2021) · PRX Quantum · doi:10.1103/prxquantum.2.010201 · Cited by 237
Compiling quantum circuits to realistic hardware architectures using temporal planners
Venturelli, D., Do, M., Rieffel, E. G., & Frank, J. (2017) · Quantum Science and Technology · doi:10.1088/2058-9565/aaa331 · Cited by 159
“We will also compare with other approaches to this compilation problem such as sorting networks (Beals et al. 2013) (Brierley 2015) (Bremner, Montanaro, and Shepherd 2016), and develop more advanced compilation methods building on the various strengths of the temporal planning approaches and other…”
BackgroundMethodHarrow, A. W., & Mehraban, S. A. (2023) · Communications in Mathematical Physics · doi:10.1007/s00220-023-04675-z · Cited by 250
Quantifying Quantum Speedups: Improved Classical Simulation From Tighter Magic Monotones
Seddon, J. R., Regula, B., Pashayan, H., Ouyang, Y., & Campbell, E. T. (2021) · PRX Quantum · doi:10.1103/prxquantum.2.010345 · Cited by 202
“[11] M.”
BackgroundRecent Advances for Quantum Neural Networks in Generative Learning
Tian, J., Sun, X., Du, Y., Zhao, S., Liu, Q., Zhang, K., Yi, W., Huang, W., Wang, C., Wu, X., et al. (2023) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2023.3272029 · Cited by 189
“works [80], [81], [82], [83] have proven the advantage of quantum computing over a classical computer on some tasks from the perspective of computational complexity theory.”
BackgroundTheory 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
Efficient classical simulation of noisy random quantum circuits in one dimension
Noh, K., Jiang, L., & Fefferman, B. (2020) · Quantum · doi:10.22331/q-2020-09-11-318 · Cited by 172
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 136
“[16,18,20,22]—is somewhat more natural than stating it in terms of additive ones, as in Ref.”
BackgroundMethodInfluentialFast-forwarding of Hamiltonians and exponentially precise measurements
Atia, Y., & Aharonov, D. (2017) · Nature Communications · doi:10.1038/s41467-017-01637-7 · Cited by 157
On the Representation of Boolean and Real Functions as Hamiltonians for Quantum Computing
Hadfield, S. (2021) · ACM Transactions on Quantum Computing · doi:10.1145/3478519 · Cited by 140
Hamiltonian simulation algorithms for near-term quantum hardware
Clinton, L., Bausch, J., & Cubitt, T. S. (2021) · Nature Communications · doi:10.1038/s41467-021-25196-0 · Cited by 123
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 161
“[30,31] for noisy-circuit simulation and the algorithm in Ref.”
MethodQuantum Supremacy Is Both Closer and Farther than It AppearsPreprint
Markov, I. L., Fatima, A., Isakov, S. V., & Boixo, S. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1807.10749 · Cited by 159
“Quantum Supremacy entails an inherently adversarial protocol that asymmetrically favors quantum computers — a computational problem is being selected that can be solved by quantum yet not classical computers [1, 2, 3, 4, 5, 6, 7, 8, 9].”
BackgroundExpressive power of parametrized quantum circuits
Du, Y., Hsieh, M.-H., Liu, T., & Tao, D. (2018) · UTS ePRESS (University of Technology Sydney) · Cited by 99
NISQ Computers: A Path to Quantum Supremacy
AbuGhanem, M., & Eleuch, H. (2024) · IEEE Access · doi:10.1109/access.2024.3432330 · Cited by 116
A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling
Aharonov, D., Gao, X., Landau, Z. A., Liu, Y., & Vazirani, U. V. (2023) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3564246.3585234 · Cited by 252
“Finally, the sampling algorithm follows from a general sampling-to-computing reduction of [12].”
MethodInfluentialTemperature Scaling Law for Quantum Annealing Optimizers
Albash, T., Martín-Mayor, V., & Hen, I. (2017) · Physical Review Letters · doi:10.1103/physrevlett.119.110502 · Cited by 81
Pattern Recognition Techniques for Boson Sampling Validation
Agresti, I., Viggianiello, N., Flamini, F., Spagnolo, N., Crespi, A., Osellame, R., Wiebe, N., & Sciarrino, F. (2019) · Physical Review X · doi:10.1103/physrevx.9.011013 · Cited by 50
Do, M., Booth, K. E. C., Frank, J., Beck, J. C., Venturelli, D., & Rieffel, E. G. (2018) · NASA STI Repository (National Aeronautics and Space Administration) · Cited by 69
"Quantum Supremacy" and the Complexity of Random Circuit Sampling
Bouland, A., Fefferman, B., Nirkhe, C., & Vazirani, U. V. (2018) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.itcs.2019.15 · Cited by 142
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 85
“For the IQP model, the no-go result with the additive error approximation was proved by Bremner, Montanaro, and Shepherd [15,16].”
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
Beyond Bits: A Review of Quantum Embedding Techniques for Efficient Information Processing
Khan, M. A., Aman, M. N., & Sikdar, B. (2024) · IEEE Access · doi:10.1109/access.2024.3382150 · Cited by 88
“These existing limitations in fully quantum hardware, characterized by noise and errors, hinder the robust implementation of quantum encoding schemes [152], [153].”
BackgroundClassical algorithm for simulating experimental Gaussian boson sampling
Oh, C., Liu, M., Alexeev, Y., Fefferman, B., & Jiang, L. (2024) · Nature Physics · doi:10.1038/s41567-024-02535-8 · Cited by 159
Quantum 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 68
A Leap among Quantum Computing and Quantum Neural Networks: A Survey
Massoli, F. V., Vadicamo, L., Amato, G. M., & Falchi, F. (2022) · ACM Computing Surveys · doi:10.1145/3529756 · Cited by 94
“Moreover, it is clear that any claim about quantum supremacy must undertake a detailed analysis based on the most recent achievements in classical simulation algorithms [39, 102, 147].”
BackgroundBoundaries of quantum supremacy via random circuit sampling
Zlokapa, A., Boixo, S., & Lidar, D. (2020) · arXiv · doi:10.48550/arxiv.2005.02464 · Cited by 55
Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage
Gao, X., Kalinowski, M., Chou, C.-N., Lukin, M. D., Barak, B., & Choi, S. (2021) · arXiv · doi:10.48550/arxiv.2112.01657 · Cited by 54
Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage
Gao, X., Kalinowski, M., Chou, C.-N., Lukin, M. D., Barak, B., & Choi, S. (2024) · PRX Quantum · doi:10.1103/prxquantum.5.010334 · Cited by 118
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 83
Machine learning \& artificial intelligence in the quantum domainPreprint
Dunjko, V., & Briegel, H. J. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1709.02779 · Cited by 54
Efficient Classical Simulation of Clifford Circuits with Nonstabilizer Input States
Bu, K., & Koh, D. E. (2019) · Physical Review Letters · doi:10.1103/physrevlett.123.170502 · Cited by 68
From estimation of quantum probabilities to simulation of quantum circuits
Pashayan, H., Bartlett, S. D., & Gross, D. (2020) · Quantum · doi:10.22331/q-2020-01-13-223 · Cited by 74
“An example of a notion of approximate weak simulation that we argue is too weak requires that the classical algorithm sample from a distribution that is within some small fixed constant L 1 -norm of the target distribution [24, 25, 9, 10, 11, 36, 16].”
BackgroundMethodInfluentialAnticoncentration 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
Application-Motivated, Holistic Benchmarking of a Full Quantum Computing Stack
Mills, D., Sivarajah, S., Scholten, T. L., & Duncan, R. (2021) · Quantum · doi:10.22331/q-2021-03-22-415 · Cited by 73
Quantum 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 73
“in [3,4,7,26]) and conjectured to hold for others (e.”
BackgroundSample 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 67
“However, most known proofs of anti-concentration [11, 16, 20, 25] (with the notable exception of Morimae’s hardness result [44]4) rely on the Paley-Zygmund inequality”
MethodAnalog errors in Ising machines
Albash, T., Martín-Mayor, V., & Hen, I. (2019) · Quantum Science and Technology · doi:10.1088/2058-9565/ab13ea · Cited by 57
Experimental Quantum Advantage with Quantum Coupon Collector
Zhou, M.-G., Cao, X., Lu, Y.-S., Wang, Y., Bao, Y., Jia, Z.-Y., Fu, Y., Yin, H., & Chen, Z. (2022) · Research · doi:10.34133/2022/9798679 · Cited by 46
Temporal Planning for Compilation of Quantum Approximate Optimization Circuits
Venturelli, D., Do, M., Rieffel, E. G., & Frank, J. (2017) · International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2017/620 · Cited by 53
“…Svore, 2014; Smith et al., 2016a; Steiger et al., 2016a; Devitt, 2016; Barends et al., 2016], few approaches have been explored for compiling idealized quantum circuits to realistic quantum hardware [Beals et al., 2013; Brierly, 2015; Bremner et al., 2016], leaving the problem open for innovation.”
BackgroundResultQuantum fluctuation theorem for error diagnostics in quantum annealers
Gardas, B., & Deffner, S. (2018) · Scientific Reports · doi:10.1038/s41598-018-35264-z · Cited by 54
Gachechiladze, M., Gühne, O., & Miyake, A. (2019) · Physical Review A · doi:10.1103/physreva.99.052304 · Cited by 41
Quantum fluctuation theorem for error diagnostics in quantum annealers
Gardas, B., & Deffner, S. (2018) · Maryland Shared Open Access Repository (USMAI Consortium) · doi:10.13016/m2dnnc-0frj · Cited by 39
Application-motivated, holistic benchmarking of a full quantum computing stack
Mills, D., Sivarajah, S., Scholten, T. L., & Duncan, R. (2021) · Strathprints: The University of Strathclyde institutional repository (University of Strathclyde) · Cited by 40
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 81
“In some cases noise can render the simulation of certain quantum circuits substantially easier (e.g. [BMS17, ZSW20]).”
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 63
Fast-forwarding of Hamiltonians and exponentially precise measurements
Atia, Y., & Aharonov, D. (2017) · RePEc: Research Papers in Economics · Cited by 43
State preparation by shallow circuits using feed forward
Buhrman, H., Folkertsma, M., Loff, B., & Neumann, N. M. P. (2024) · Quantum · doi:10.22331/q-2024-12-09-1552 · Cited by 75
“Classical simulation of IQP circuits implies the collapse of the polynomial hierarchy to the third level, which is not believed to be true [BMS17].”
Quantum semi-supervised generative adversarial network for enhanced data classification
Nakaji, K., & Yamamoto, N. (2021) · Scientific Reports · doi:10.1038/s41598-021-98933-6 · Cited by 47
“In particular, based on the possible higher expressibility of quantum circuits over the classical one, which has been proven theoretically and demonstrated experimentally [8–12], the quantum machine learning is expected to provide alternative subroutines to improve the performance.”
BackgroundQuantum 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
Scalable quantum processor noise characterization
Hamilton, K. E., Kharazi, T., Morris, T., McCaskey, A., Bennink, R. S., & Pooser, R. C. (2020) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce49297.2020.00060 · Cited by 57
“While fault tolerance and error corrected qubits are necessary for many large-scale quantum algorithms, recent studies have suggested that quantum processors with 50-60 qubits and sufficiently low error rates can out-perform classical computers at certain problems [2], [3], [4].”
BackgroundEvaluation of QAOA based on the approximation ratio of individual samples
Larkin, J. M., Jonsson, M., Justice, D., & Guerreschi, G. G. (2022) · Quantum Science and Technology · doi:10.1088/2058-9565/ac6973 · Cited by 54
Quantum computing basics, applications and future perspectives
Balamurugan, K. S., Sivakami, A., Mathankumar, M., Prasad, Y. J. D. S., & Ahmad, I. (2024) · Journal of Molecular Structure · doi:10.1016/j.molstruc.2024.137917 · Cited by 54
Simulating Noisy Variational Quantum Algorithms: A Polynomial Approach
Shao, Y., Wei, F., Cheng, S., & Liu, Z. (2024) · Physical Review Letters · doi:10.1103/physrevlett.133.120603 · Cited by 99
Quantum Kitchen Sinks: An algorithm for machine learning on near-term quantum computersPreprint
Wilson, C. M., Otterbach, J., Tezak, N., Smith, R., Polloreno, A., Karalekas, P. J., Heidel, S., Alam, M., Crooks, G. E., & Silva, M. P. D. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1806.08321 · Cited by 79
“The first strategy leads straightforwardly to a quantum advantage argument if the parameterized circuits used are hard to simulate [33–36].”
BackgroundQuantum Circuit Compilation: An Emerging Application for Automated Reasoning
Venturelli, D., Minh, N., O’Gorman, B., Frank, J., Rieffel, E. G., Booth, K. E. C., Nguyen, T. L., Narayan, P., & Nanda, S. (2019) · Cited by 46
Measurement-Driven Phase Transition within a Volume-Law Entangled PhasePreprint
Vijay, S. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2005.03052 · Cited by 86
Superconducting quantum computers: who is leading the future?
AbuGhanem, M. (2025) · EPJ Quantum Technology · doi:10.1140/epjqt/s40507-025-00405-7 · Cited by 59
Variational Quantum Circuits for Machine Learning. An Application for the Detection of Weak Signals
Griol-Barres, I., Milla, S., Cebrián, A., Mansoori, Y., & Millet, J. (2021) · Applied Sciences · doi:10.3390/app11146427 · Cited by 40
“In addition, there are strong arguments showing that circuits of great simplicity are difficult to simulate on conventional computers [81,82].”
BackgroundInfluentialThe hardness of random quantum circuits
Movassagh, R. (2023) · Nature Physics · doi:10.1038/s41567-023-02131-2 · Cited by 61
“In their seminal work, Terhal and DiVincenzo 37 proved the existence of such circuits for constant-depth (four) circuits and Bremner et al. proved it for IQP circuits with depth √ n (ref.”
BackgroundFurther extensions of Clifford circuits and their classical simulation complexities
Koh, D. E. (2017) · Quantum Information and Computation · doi:10.26421/qic17.3-4-5 · Cited by 49
“Similar results have been obtained for IQP circuits [13,14,25], and it will be interesting to prove similar hardness results for extended Clifford circuits.”
ResultEfficient classical simulation of noisy quantum computationPreprint
Gao, X., & Duan, L. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1810.03176 · Cited by 107
“The Fourier spectrum analysis [16] has been used recently for classical simulation of noisy quantum dynamics from the Ising interaction [17, 18].”
BackgroundMethodA Polynomial-Time Classical Algorithm for Noisy Quantum Circuits
Schuster, T., Yin, C., Gao, X., & Yao, N. Y. (2025) · Physical Review X · doi:10.1103/xct1-7kf2 · Cited by 148
Kumar, N., Kerenidis, I., & Diamanti, E. (2019) · Nature Communications · doi:10.1038/s41467-019-12139-z · Cited by 44
“(9), we find that the probability of a click in the correct detector at each time slot is,”
BackgroundBugu, S., Ozaydin, F., & Kodera, T. (2020) · Scientific Reports · doi:10.1038/s41598-020-79295-x · Cited by 30
Miller, J., Sanders, S. K., & Miyake, A. (2017) · Physical Review A · doi:10.1103/physreva.96.062320 · Cited by 35
“An alternative proposal which circumvents this bottleneck is the family of instantaneous quantum polynomial-time (IQP) protocols [5, 8, 15], where sampling distributions arise from single-qubit measurements on the output of low-depth commuting quantum circuits.”
BackgroundMethodBooth, K. E. C., Do, M., Beck, J. C., Rieffel, E. G., Venturelli, D., & Frank, J. (2018) · Proceedings of the International Conference on Automated Planning and Scheduling · doi:10.1609/icaps.v28i1.13920 · Cited by 77
Effects of quantum resources and noise on the statistical complexity of quantum circuits
Bu, K., Koh, D. E., Li, L., Luo, Q., & Zhang, Y. (2023) · Quantum Science and Technology · doi:10.1088/2058-9565/acb56a · Cited by 40
“While I can be efficiently simulated on a classical computer [27], IQP circuits formed from the gate set I + CCZ are hard to simulate classically [6, 8, 59], which motivates us to consider the set I CCZ of IQP circuits with at most k CCZ gates.”
Experimental study of Forrelation in nuclear spins
Li, H., Gao, X., Xin, T., Yung, M., & Long, G. (2017) · 中国科学通报:英文版 · doi:10.1016/j.scib.2017.03.006 · Cited by 23
Spoofing Cross-Entropy Measure in Boson Sampling
Oh, C., Jiang, L., & Fefferman, B. (2023) · Physical Review Letters · doi:10.1103/physrevlett.131.010401 · Cited by 37
Quantum supremacy and random circuitsPreprint
Movassagh, R. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1909.06210 · Cited by 83
Complexity Classification of Conjugated Clifford Circuits
Bouland, A., Fitzsimons, J. F., & Koh, D. E. (2017) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.ccc.2018.21 · Cited by 49
“Several of these models – namely Boson Sampling [AA11], IQP [BMS16a, BMS16b], Fourier Sampling [FU16], the one clean qubit model [Mor17], and random universal quantum circuits [BIS + 16, AC17, MB17] – additionally have been shown to be difficult to simulate to reasonable amounts of error under…”
BackgroundResultInfluentialQuantum simulation of partially distinguishable boson sampling
Moylett, A. E., & Turner, P. S. (2018) · Physical Review A · doi:10.1103/physreva.97.062329 · Cited by 29
“Numerous proposals have been made [4, 5], with perhaps the best known being Boson Sampling [6], which considers the complexity of sampling from the same probability distribution as n indistinguishable photons output from an m-mode linear optical interferometer, shown to be determined by matrix permanents [7].”
BackgroundQuantum supremacy: some fundamental concepts
Yung, M. (2018) · National Science Review · doi:10.1093/nsr/nwy072 · Cited by 24
Bugu, S., Bugu, S., Ozaydin, F., 小寺哲夫, & Kodera, T. (2020) · Tokyo Tech Research Repository (Tokyo Institute of Technology) · Cited by 21
Metadata
- Authors
- Bremner, M. J., Montanaro, A., & Shepherd, D. J.
- Affiliations
- University of Technology Sydney (AU)
- University of Bristol (GB)
- 3NCSC, Hubble Road, Cheltenham, UK
- Venue
- Quantum
- Published
- 2017-04-25
- Volume
- 1
- Pages
- 8
- ISSN
- 2521-327X (ISSN-L)
- OpenAlex
- W2528010580
- Cited by
- 191
- References
- 51
- Citations by year
- 2026: 9 · 2025: 15 · 2024: 22 · 2023: 14 · 2022: 15 · 2021: 26 · 2020: 24 · 2019: 23 · 2018: 27 · 2017: 16
- FWCI
- 14.68
- Type
- journal article
- Language
- en
- Open access
- gold
- doi.org
- Locations
- Quantum (publishedVersion, cc-by)
- arXiv (Cornell University) (submittedVersion)
- DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
- UTS ePRESS (University of Technology Sydney) (submittedVersion)
- Bristol Research (University of Bristol) (submittedVersion, cc-by)
- Explore Bristol Research (submittedVersion, cc-by)
- arXiv (Cornell University) (cc-by)
- Funders
- Engineering and Physical Sciences Research Council (EP/L021005/1)
- Australian Research Council (FT110101044, CE170100012)
- Centre of Excellence for Quantum Computation and Communication Technology, Australian Research Council (CE170100012)
- 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 many-body systems
- Keywords
- quantum advantage, IQP circuits, noisy quantum circuits, classical simulation, anti-concentration, total variation distance, square lattice
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.
