Architectures for Quantum Simulation Showing a Quantum Speedup
Open accessThe DOI matches its Crossref record; 31 of the 31 references it cites were found in a registry or an index.
Abstract
One of the main aims in the field of quantum simulation is to achieve a quantum speedup, often referred to as "quantum computational supremacy," referring to the experimental realization of a quantum device that computationally outperforms classical computers.In this work, we show that one can devise versatile and feasible schemes of two-dimensional, dynamical, quantum simulators showing such a quantum speedup, building on intermediate problems involving nonadaptive, measurement-based, quantum computation.In each of the schemes, an initial product state is prepared, potentially involving an element of randomness as in disordered models, followed by a short-time evolution under a basic translationally invariant Hamiltonian with simple nearest-neighbor interactions and a mere sampling measurement in a fixed basis.The correctness of the final-state preparation in each scheme is fully efficiently certifiable.We discuss experimental necessities and possible physical architectures, inspired by platforms of cold atoms in optical lattices and a number of others, as well as specific assumptions that enter the complexity-theoretic arguments.This work shows that benchmark settings exhibiting a quantum speedup may require little control, in contrast to universal quantum computing.Thus, our proposal puts a convincing experimental demonstration of a quantum speedup within reach in the near term.
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
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.
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
Raussendorf, R., & Briegel, H. J. (2001) · Physical Review Letters · doi:10.1103/physrevlett.86.5188 · Cited by 4,477 · cited 6×
“To prove this result, we assume basic knowledge of MBQC on cluster states [29,38].”
BackgroundInfluentialSelf-citationLloyd, S. (1996) · Science · doi:10.1126/science.273.5278.1073 · Cited by 3,088 · cited 1×
“The anticipated device of a universal quantum computer would solve problems for which no efficient classical algorithm is known, such as integer factorization [1] and simulating many-body Hamiltonian dynamics [2].”
BackgroundSurface codes: Towards practical large-scale quantum computation
Fowler, A. G., Mariantoni, M., Martinis, J. M., & Cleland, A. N. (2012) · Physical Review A · doi:10.1103/physreva.86.032324 · Cited by 3,059 · cited 1×
“However, the experimental realization of such a machine requires fault-tolerant protection of universal dynamics against arbitrary errors [3–5][6,7].”
BackgroundThe complexity of computing the permanent
Valiant, L. G. (1979) · Theoretical Computer Science · doi:10.1016/0304-3975(79)90044-6 · Cited by 2,705 · cited 1×
“Thus, accepting Conjecture 2 implies that approximating jZðα;βÞj2 for these models is as hard, on average, as any problem in #P [37].”
BackgroundQuantum simulations with ultracold quantum gases
Bloch, I., Dalibard, J., & Nascimbène, S. (2012) · Nature Physics · doi:10.1038/nphys2259 · Cited by 2,339 · cited 3×
“tum simulators [9,10] have the ability to outperform”
BackgroundSuperconducting quantum circuits at the surface code threshold for fault tolerance
Barends, R., Kelly, J., Megrant, A., Veitia, A., Sank, D., Jeffrey, E., White, T. C., Mutus, J., Fowler, A. G., Campbell, B., et al. (2014) · Nature · doi:10.1038/nature13171 · Cited by 1,733
Measurement-based quantum computation on cluster states
Raussendorf, R., Browne, D. E., & Briegel, H. J. (2003) · Physical Review A · doi:10.1103/physreva.68.022312 · Cited by 1,655 · cited 8×
“To prove this result, we assume basic knowledge of MBQC on cluster states [29,38].”
BackgroundMethodInfluentialSelf-citationQuantum many-body systems out of equilibrium
Eisert, J., Friesdorf, M., & Gogolin, C. (2015) · Nature Physics · doi:10.1038/nphys3215 · Cited by 1,255 · cited 1×
“tum simulators [9,10] have the ability to outperform”
BackgroundSelf-citationCharacterizing 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 10×
“For 1D nearest-neighbor layouts, the latter are expected to reach a chaotic Porter-Thomas-distributed regime [42–44] in depth D ∈ O ( n ) [84–86] (cf. numerically [18] for further discussion).”
BackgroundMethodResultInfluentialOn-chip quantum simulation with superconducting circuits
Houck, A. A., Türeci, H. E., & Koch, J. (2012) · Nature Physics · doi:10.1038/nphys2251 · Cited by 1,069
Trotzky, S., Chen, Y.-A., Flesch, A., McCulloch, I. P., Schollwöck, U., Eisert, J., & Bloch, I. (2012) · Nature Physics · doi:10.1038/nphys2232 · Cited by 1,058
Self-citationConditions for a class of entanglement transformations
Nielsen, M. A. (1999) · Physical Review Letters · doi:10.1103/physrevlett.83.436 · Cited by 1,036
Exploring the many-body localization transition in two dimensions
Choi, J.-Y., Hild, S., Zeiher, J., Schauß, P., Rubio-Abadal, A., Yefsah, T., Khemani, V., Huse, D. A., Bloch, I., & Gross, C. (2016) · Science · doi:10.1126/science.aaf8834 · Cited by 979 · cited 3×
“Disordered initial states can also be prepared [12,14,64].”
BackgroundInfluentialGoals and opportunities in quantum simulation
Cirac, J. I., & Zoller, P. (2012) · Nature Physics · doi:10.1038/nphys2275 · Cited by 891 · cited 1×
“We remain close to what one commonly conceives as a dynamical quantum simulator [9–11, 23 Our specific contributions are as follows.”
BackgroundProbing the Superfluid–to–Mott Insulator Transition at the Single-Atom Level
Bakr, W. S., Peng, A., Tai, M. E., Ma, R., Simon, J., Gillen, J. I., Fölling, S., Pollet, L., & Greiner, M. (2010) · Science · doi:10.1126/science.1192368 · Cited by 796
Entanglement of Atoms via Cold Controlled Collisions
Jaksch, D., Briegel, H.-J., Cirac, J. I., Gardiner, C. W., & Zoller, P. (1999) · Physical Review Letters · doi:10.1103/physrevlett.82.1975 · Cited by 795 · cited 2×
“Large-scale, translationally invariant, controlled-Z interactions—precisely of the type required for the preparation of cluster and graph states [38,57]—are feasible via controlled collisions [25,58].”
BackgroundControlled collisions for multi-particle entanglement of optically trapped atoms
Mandel, O., Greiner, M., Widera, A., Rom, T., Hänsch, T. W., & Bloch, I. (2003) · Nature · doi:10.1038/nature02008 · Cited by 789
Fault-Tolerant Quantum Computation with Constant Error Rate
Aharonov, D., & Ben-Or, M. (2008) · SIAM Journal on Computing · doi:10.1137/s0097539799359385 · Cited by 513 · cited 1×
“However, the experimental realization of such a machine requires fault-tolerant protection of universal dynamics against arbitrary errors [3–5], which incurs in prohibitive qubit overhead [6, 7] beyond reach in available quantum devices.”
BackgroundDirect Observation of Dirac Cones and a Flatband in a Honeycomb Lattice for Polaritons
Jacqmin, T., Carusotto, I., Sagnes, I., Abbarchi, M., Solnyshkov, D. D., Malpuech, G., Galopin, E., Lemaître, A., Bloch, J., & Amo, A. (2014) · Physical Review Letters · doi:10.1103/physrevlett.112.116402 · Cited by 509
Local Random Quantum Circuits are Approximate Polynomial-Designs
Brandão, F. G. S. L., Harrow, A. W., & Horodecki, M. (2016) · Communications in Mathematical Physics · doi:10.1007/s00220-016-2706-8 · Cited by 404 · cited 2×
“Universal random quantum circuits of increasing depth are known to approximate the Haar measure under various settings [44–46, 83, 86].”
BackgroundMethodology for quantum logic gate construction
Zhou, X., Leung, D. W., & Chuang, I. L. (2000) · Physical Review A · doi:10.1103/physreva.62.052316 · Cited by 355
Valence-bond states for quantum computation
Verstraete, F., & Cirac, J. I. (2004) · Physical Review A · doi:10.1103/physreva.70.060302 · Cited by 333
Random Quantum Circuits are Approximate 2-designs
Harrow, A. W., & Low, R. A. (2009) · Communications in Mathematical Physics · doi:10.1007/s00220-009-0873-6 · Cited by 324 · cited 2×
“As it is discussed further in appendix C, γ y,β × e and α are expected to converge to one for universal 1D nearest-neighbor circuits as n grows asymptotically [44–46 , 83 ] for a constant ε ≥ 0 .”
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 3×
“[16,18,20,22]—is somewhat more natural than stating it in terms of additive ones, as in Ref.”
BackgroundMethodAverage-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
Novel Schemes for Measurement-Based Quantum Computation
Gross, D., & Eisert, J. (2007) · Physical Review Letters · doi:10.1103/physrevlett.98.220503 · Cited by 255 · cited 1×
“At the same time, they are injective projected entangled pair states (PEPS) of constant bond dimension [54,55].”
BackgroundSelf-citationComplexity-Theoretic Foundations of Quantum Supremacy Experiments
Aaronson, S., & Chen, L. (2016) · arXiv · doi:10.48550/arxiv.1612.05903 · Cited by 218
A new universal and fault-tolerant quantum basis
Boykin, P. O., Mor, T., Pulver, M., Roychowdhury, V., & Vatan, F. (2000) · Information Processing Letters · doi:10.1016/s0020-0190(00)00084-3 · Cited by 194 · cited 1×
“Our proof is constructive and shows how to simulate universal circuits of Cliffordþ T gates [76] via postselection.”
MethodAchieving quantum supremacy with sparse and noisy commuting quantum computations
Bremner, M. J., Montanaro, A., & Shepherd, D. J. (2017) · Quantum · doi:10.22331/q-2017-04-25-8 · Cited by 191 · cited 6×
“[16,18,20,22]—is somewhat more natural than stating it in terms of additive ones, as in Ref.”
BackgroundMethodInfluentialCompleteness of the Classical 2D Ising Model and Universal Quantum Computation
Van den Nest, M., Dür, W., & Briegel, H. J. (2008) · Physical Review Letters · doi:10.1103/physrevlett.100.110501 · Cited by 63 · cited 1×
“If an even-column, odd-row qubit i is prepared in j − ii and measured in the X basis (or, equivalently, in jþi and measured in the Y basis), we obtain a reduced graph-state vector jG000i whose graph G000 is obtained from G00 by contracting the edges incident to i [89,90].”
MethodQuantum 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 · cited 1×
“To illustrate the difference, note that there exist quantum algorithms for approximating (normalized) Ising partition functions up to polynomially small additive errors [94, 95], while the latter are”
Method
Cited by
Quantum advantage with shallow circuits
Bravyi, S., Gosset, D., & König, R. (2018) · Science · doi:10.1126/science.aar3106 · Cited by 406
Quantum simulation and computing with Rydberg-interacting qubits
Morgado, M., & Whitlock, S. (2021) · AVS Quantum Science · doi:10.1116/5.0036562 · Cited by 370
Stochastic gradient descent for hybrid quantum-classical optimization
Sweke, R., Wilde, F., Meyer, J., Schuld, M., Faehrmann, P. K., Meynard-Piganeau, B., & Eisert, J. (2020) · Quantum · doi:10.22331/q-2020-08-31-314 · Cited by 219
Self-citationAchieving quantum supremacy with sparse and noisy commuting quantum computations
Bremner, M. J., Montanaro, A., & Shepherd, D. J. (2017) · Quantum · doi:10.22331/q-2017-04-25-8 · Cited by 191
Classical 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
Metadata
- Authors
- Bermejo-Vega, J., Hangleiter, D., Schwarz, M., Raussendorf, R., & Eisert, J.
- Venue
- Physical Review X
- Publisher
- American Physical Society (APS)
- Published
- 2018-04-09
- Volume
- 8
- Issue
- 2
- ISSN
- 2160-3308 (ISSN-L)
- OpenAlex
- W2749114779
- Cited by
- 99
- References
- 31
- FWCI
- 7.36
- Type
- journal article
- Language
- en
- Open access
- gold
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.