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.”
BackgroundSimulating Quantum Computation by Contracting Tensor Networks
Markov, I. L., & Shi, Y. (2008) · SIAM Journal on Computing · doi:10.1137/050644756 · Cited by 472 · cited 2×
“Tensor network contraction techniques can be used to show that any output probability of any quantum circuit of depth D implemented on a 2d square lattice can be precisely evaluated classically in time O(2D √ n) [28], suggesting that if it were possible to implement arbitrary sparse IQP circuits in depth o( √ n) then…”
BackgroundMethodQuantum Supremacy through the Quantum Approximate Optimization Algorithm
Farhi, E., & Harrow, A. W. (2016) · arXiv · doi:10.48550/arxiv.1602.07674 · Cited by 331 · cited 2×
“The structure of the QAOA is very similar to an IQP circuit, and hardness of simulating the algorithm classically, up to small relative error, can be proven under similar assumptions to those for IQP circuits [20].”
MethodLearning Decision Trees Using the Fourier Spectrum
Kushilevitz, E., & Mansour, Y. (1993) · SIAM Journal on Computing · doi:10.1137/0222080 · Cited by 328
Quantum computing and the entanglement frontier
Preskill, J. (2012) · arXiv · doi:10.48550/arxiv.1203.5813 · Cited by 308 · cited 1×
“Over the last few years there has been significant attention devoted to devising experimental demonstrations of quantum supremacy [32]: namely a quantum computer solving a computational task that goes beyond what a classical machine could achieve.”
BackgroundClassical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
Bremner, M. J., Jozsa, R., & Shepherd, D. J. (2011) · Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.2010.0301 · Cited by 308 · cited 5×
“In [10] it was shown that IQP sampling, up to relative errors, could not be efficiently performed classically without a collapse in the polynomial hierarchy.”
BackgroundInfluentialSelf-citationAverage-Case Complexity Versus Approximate Simulation of Commuting Quantum Computations
Bremner, M. J., Montanaro, A., & Shepherd, D. J. (2016) · Physical Review Letters · doi:10.1103/physrevlett.117.080501 · Cited by 299 · cited 10×
“There is a family of commuting quantum circuits on n qubits where: with high probability, a random circuit picked from the family contains O(n log n) 2-qubit gates and can be implemented on a 2d square lattice in depth O( √ n log n); and a constant fraction of circuits picked from the family cannot be simulated classi…”
BackgroundInfluentialSelf-citationClassical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
Bremner, M. J., Jozsa, R., Shepherd, D. J., et al. (2010) · Cited by 216
Self-citationSufficient Conditions for Efficient Classical Simulation of Quantum Optics
Rahimi-Keshari, S., Ralph, T. C., & Caves, C. M. (2016) · Physical Review X · doi:10.1103/physrevx.6.021039 · Cited by 209 · cited 1×
“Kalai and Kindler have given evidence that suggests that, for small errors in the matrix U , boson sampling is classically simulable [24] (see also [23], and [33] for a recent study of more physicallymotivated noise models).”
BackgroundThe Computational Complexity of Linear OpticsPreprint
Aaronson, S., & Arkhipov, A. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1011.3245 · Cited by 209 · 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).”
MethodResultInfluentialEfficient distributed quantum computing
Beals, R., Brierley, S., Gray, O., Harrow, A. W., Kutin, S., Linden, N., Shepherd, D., & Stather, M. (2013) · Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.2012.0686 · Cited by 208 · cited 3×
“Third, we apply the results of [6] to show that”
BackgroundMethodInfluentialSelf-citationPolynomial time approximation schemes for dense instances of NP-hard problems
Arora, S., Karger, D., & Karpinski, M. (1995) · Proceedings of the twenty-seventh annual ACM symposium on Theory of computing - STOC '95 · doi:10.1145/225058.225140 · Cited by 199 · cited 2×
“It is known that there are a range of related #P-hard and NP-hard graph problems that admit an efficient approximation for random dense graphs [5, 3], while retaining their hardness on sparse graphs.”
BackgroundPolynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems
Arora, S., Karger, D., & Karpinski, M. (1999) · Journal of Computer and System Sciences · doi:10.1006/jcss.1998.1605 · Cited by 199
An optimal sorting algorithm for mesh connected computers
Schnorr, C. P., & Shamir, A. (1986) · Proceedings of the eighteenth annual ACM symposium on Theory of computing - STOC '86 · doi:10.1145/12130.12156 · Cited by 197 · cited 1×
“It was shown in [36] that there exists a sorting network on a 2d √ n × √ n lattice which has depth 3 √ n + o( √ n); this is close to optimal by diameter arguments.”
MethodArchitectures 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
Temporally unstructured quantum computation
Shepherd, D., & Bremner, M. J. (2009) · Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.2008.0443 · Cited by 135 · cited 3×
“Very similar, and more general, ideas about transformation of IQP circuits were introduced in [40, 39], albeit in slightly different language.”
BackgroundMethodSelf-citationA Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
Farhi, E., Goldstone, J., & Gutmann, S. (2014) · arXiv · doi:10.48550/arxiv.1412.6062 · Cited by 131 · 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…”
MethodQuantum 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 129
Scrambling speed of random quantum circuitsPreprint
Brown, W., & Fawzi, O. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1210.6644 · Cited by 123 · cited 6×
“[13] W. Brown and O. Fawzi.”
BackgroundResultInfluentialDecoupling with Random Quantum Circuits
Brown, W., & Fawzi, O. (2015) · Communications in Mathematical Physics · doi:10.1007/s00220-015-2470-1 · Cited by 100 · cited 8×
“Our result thus saves an O(log(2) n) factor over [13].”
BackgroundResultInfluentialGaussian Noise Sensitivity and BosonSamplingPreprint
Kalai, G., & Kindler, G. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1409.3093 · Cited by 82 · cited 9×
“The results of [24] cannot simply be averaged over S to obtain a similar low-degree polynomial approximation to Dbs, as they do not take the normalisation term in (1) into account, nor the possibility of repeated columns in S.”
BackgroundResultInfluentialDirect 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 79 · cited 1×
“An IQP verification procedure was proposed in [23], but this requires the preparation of states going beyond the IQP model.”
MethodNew Limits on Fault-Tolerant Quantum Computation
Buhrman, H., Cleve, R., Laurent, M., Linden, N., Schrijver, A., & Unger, F. (2006) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2006.50 · Cited by 75 · cited 1×
“A number of authors have provided converses to this, in a variety of different models [34, 43, 14, 25].”
BackgroundHardness 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 · cited 1×
“There are several intermediate quantum computing models which could be used to demonstrate quantum supremacy, including simple linear-optical circuits (the boson sampling problem [1]); the one clean qubit model [30]; and commuting quantum circuits, a model known as “IQP” [40, 10].”
BackgroundBosonSampling is robust against small errors in the network matrix
Arkhipov, A. (2015) · Physical Review A · doi:10.1103/physreva.92.062326 · Cited by 59
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
Classical simulability, entanglement breaking, and quantum computation thresholds
Virmani, S., Huelga, S. F., & Plenio, M. B. (2005) · Physical Review A · doi:10.1103/physreva.71.042328 · Cited by 51 · cited 1×
“t-tolerance states that there is a constant noise threshold below which universal quantum computation is possible. A number of authors have provided converses to this, in a variety of dierent models [34, 43,14,25]. These works show that, if a quantum circuit experiences sucient noise, either it is simulable classicall…”
BackgroundShchesnovich, V. S. (2015) · Physical Review A · doi:10.1103/physreva.91.063842 · Cited by 43
The distribution of the maximum degree of a random graph
Bollobás, B. (1980) · Discrete Mathematics · doi:10.1016/0012-365x(80)90054-0 · Cited by 40 · cited 1×
“[8]); here we give an elementary upper bound.”
BackgroundAn upper bound on the threshold quantum decoherence rate
Razborov, A. A. (2004) · Quantum Information and Computation · doi:10.26421/qic4.3-7 · Cited by 40
Simulating Quantum Circuits with Sparse Output DistributionsPreprint
Schwarz, M., & den Nest, M. V. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1310.6749 · Cited by 38 · cited 8×
“Interestingly, it was shown by Schwarz and Van den Nest [37] that IQP circuits can be simulated classically (with a similar notion of simulation to that considered here) if the output probability distribution p is close to sparse.”
BackgroundMethodInfluentialKalai, G. (2016) · Notices of the American Mathematical Society · doi:10.1090/noti1380 · Cited by 38 · cited 2×
“Kalai and Kindler have given evidence that suggests that, for small errors in the matrix U , boson sampling is classically simulable [24] (see also [23], and [33] for a recent study of more physicallymotivated noise models).”
BackgroundComputational quantum-classical boundary of noisy commuting quantum circuits
Fujii, K., & Tamate, S. (2016) · Scientific Reports · doi:10.1038/srep25598 · Cited by 37 · cited 7×
“Fujii and Tamate’s result shows that it is classically hard to sample from the noisy output distribution p̃ of arbitrary IQP circuits up to a small relative error in each probability.”
BackgroundInfluentialError Suppression for Hamiltonian-Based Quantum Computation Using Subsystem Codes
Marvian, M., & Lidar, D. A. (2017) · Physical Review Letters · doi:10.1103/physrevlett.118.030504 · Cited by 34 · cited 1×
“The idea of encoding a Hamiltonian in this way with a classical or quantum code has previously been used to protect adiabatic quantum algorithms against noise (see [29] and references therein).”
MethodBinary Matroids and Quantum Probability DistributionsPreprint
Shepherd, D. J. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1005.1744 · Cited by 26 · cited 4×
“It is shown in [39] that any gate in such a circuit, even acting on all n qubits, can be replaced with poly(n) gates from the same family acting on at most 3 qubits each without changing the output of the circuit.”
BackgroundMethodInfluentialSelf-citationAn upper bound on the threshold quantum decoherence rate
Razborov, A. A. (2004) · CERN Document Server (European Organization for Nuclear Research) · doi:10.5555/2011617.2011624 · Cited by 25
Block Interpolation: A Framework for Tight Exponential-Time Counting Complexity
Curticapean, R. (2015) · Information and Computation · doi:10.1007/978-3-662-47672-7_31 · Cited by 20 · cited 2×
“Standard tensor network contraction techniques would allow any output probability of the above circuits on a square lattice to be classically computed in time O(2D √ n), so achieving a similar hardness result for D = o( √ n) would violate the counting exponential time hypothesis [9, 15].”
BackgroundResultUpper Bounds on the Noise Threshold for Fault-Tolerant Quantum Computing
Kempe, J., Regev, O., Unger, F., & de Wolf, R. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-70575-8_69 · 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 · cited 3×
“It was also shown by Leverrier and Garćıa-Patrón [28], and independently Kalai and Kindler [25], that, for considerably smaller levels of imperfection (e.g. 1/n), the output of the boson sampling circuit is far from the intended output.”
BackgroundPolynomial time randomised approximation schemes for the Tutte polynomial of dense graphs
Alon, N., FRIEZE, A. M., & Welsh, D. J. A. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365708 · Cited by 13 · cited 2×
“It is known that there are a range of related #P-hard and NP-hard graph problems that admit an efficient approximation for random dense graphs [5, 3], while retaining their hardness on sparse graphs.”
BackgroundThe Quantum Computer Puzzle (Expanded Version)Preprint
Kalai, G. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1605.00992 · Cited by 8 · cited 2×
“Kalai and Kindler have given evidence that suggests that, for small errors in the matrix U , boson sampling is classically simulable [24] (see also [23], and [33] for a recent study of more physicallymotivated noise models).”
BackgroundNew Limits on Fault-Tolerant Quantum ComputationPreprint
Buhrman, H., Cleve, R., Laurent, M., et al. (2006) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0604141 · Cited by 8 · cited 1×
“A number of authors have provided converses to this, in a variety of different models [34, 43, 14, 25].”
BackgroundArchitectures for quantum simulation showing quantum supremacyPreprint
Bermejo-Vega, J., Hangleiter, D., Schwarz, M., Raussendorf, R., & Eisert, J. (2017) · arXiv (Cornell University) · Cited by 4
Fine-Grained Dichotomies for the Tutte Plane and Boolean #CSP
Brand, C., Dell, H., & Roth, M. (2018) · Algorithmica · doi:10.1007/s00453-018-0472-z · Cited by 3 · cited 2×
“Standard tensor network contraction techniques would allow any output probability of the above circuits on a square lattice to be classically computed in time O (2 D √ n ) , so achieving a similar hardness result for D = o ( √ n ) would violate the counting exponential time hypothesis [9, 15].”
BackgroundResultComputational quantum-classical boundary of complex and noisy quantum systemsPreprint
Fujii, K., & Tamate, S. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1406.6932 · Cited by 3
Analysis of circuit imperfections in BosonSamplingPreprint
Leverrier, A., & García−Patrón, R. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1309.4687 · Cited by 1
An Upper Bound on the Threshold Quantum Decoherence RatePreprint
Razborov, A. A. (2003) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0310136 · Cited by 1 · cited 5×
“Perhaps the most relevant of these results to the case of IQP circuits is that of Razborov [35], which considers arbitrary quantum circuits containing gates of fan-in at most k, and a model where depolarising noise with rate larger than 1−1/k is applied to each qubit after each layer of gates in the circuit.”
BackgroundInfluentialUpper Bounds on the Noise Threshold for Fault-tolerant Quantum ComputingPreprint
Kempe, J., Regev, O., Unger, F., et al. (2008) · arXiv (Cornell University) · doi:10.48550/arxiv.0802.1464
Classical simulatability, entanglement breaking, and quantum computation thresholds
Virmani, S., Huelga, S. F., & Plenio, M. B. (2004) · CERN Document Server (European Organization for Nuclear Research) · doi:10.48550/arxiv.quant-ph/0408076 · cited 1×
“t-tolerance states that there is a constant noise threshold below which universal quantum computation is possible. A number of authors have provided converses to this, in a variety of dierent models [34, 43,14,25]. These works show that, if a quantum circuit experiences sucient noise, either it is simulable classicall…”
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-citation
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.
