Spectral Gap Amplification
Open accessThe DOI matches its Crossref record; 11 of the 11 references it cites were found in a registry or an index.
Abstract
Many problems can be solved by preparing a specific eigenstate of some Hamiltonian $H$. The generic cost of quantum algorithms for these problems is determined by the inverse spectral gap of $H$ for that eigenstate and the cost of evolving with $H$ for some fixed time. The goal of spectral gap amplification is to construct a Hamiltonian $H'$ with the same eigenstate as $H$ but a bigger spectral gap, requiring that constant-time evolutions with $H'$ and $H$ are implemented with nearly the same cost. We show that a quadratic spectral gap amplification is possible when $H$ satisfies a frustration-free property and give $H'$ for these cases. This results in quantum speedups for optimization problems. It also yields improved constructions for adiabatic simulations of quantum circuits and for the preparation of projected entangled pair states, which play an important role in quantum many-body physics. Defining a suitable black-box model, we establish that the quadratic amplification is optimal for frustration-free Hamiltonians and that no spectral gap amplification is possible, in general, if the frustration-free property is removed. A corollary is that finding a similarity transformation between a stoquastic Hamiltonian and the corresponding stochastic matrix is hard in the black-box model, setting limits to the power of some classical methods that simulate quantum adiabatic evolutions.
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
Quantum annealing in the transverse Ising model
Kadowaki, T., & Nishimori, H. (1998) · Physical Review E · doi:10.1103/physreve.58.5355 · Cited by 2,339 · cited 2×
“Methods to compute such states exist, with adiabatic state transformation (AST) being one of the most acknowledged and powerful heuristics for that goal [4, 19–21, 23, 25].”
MethodA Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
Farhi, E., Goldstone, J., Gutmann, S., Lapan, J., Lundgren, A., & Preda, D. (2001) · Science · doi:10.1126/science.1057726 · Cited by 2,056
Strengths and Weaknesses of Quantum Computing
Bennett, C. H., Bernstein, E., Brassard, G., & Vazirani, U. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539796300933 · Cited by 1,470 · cited 2×
“Quantum algorithms that solve SEARCH with Θ( √ M) uses of Qx, and other x-independent operations, exist [7, 21].”
MethodClassical and Quantum Computation
Kitaev, A., Shen, A., & Vyalyi, M. (2002) · Graduate Studies in Mathematics · doi:10.1090/gsm/047 · Cited by 1,387
Spatial search by quantum walk
Childs, A. M., & Goldstone, J. (2004) · Physical Review A · doi:10.1103/physreva.70.022314 · Cited by 725 · cited 1×
“[14], and Andrew Landahl for discussions on constructions of local Hamiltonians.”
BackgroundEfficient Quantum Algorithms for Simulating Sparse Hamiltonians
Berry, D. W., Ahokas, G., Cleve, R., & Sanders, B. C. (2007) · Communications in Mathematical Physics · doi:10.1007/s00220-006-0150-x · Cited by 692
(2004) · doi:10.1109/focs.2004.53 · Cited by 599
Criticality, the Area Law, and the Computational Power of Projected Entangled Pair States
Verstraete, F., Wolf, M. M., Perez-Garcia, D., & Cirac, J. I. (2006) · Physical Review Letters · doi:10.1103/physrevlett.96.220601 · Cited by 580
Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation
Aharonov, D., van Dam, W., Kempe, J., Landau, Z., Lloyd, S., & Regev, O. (2007) · SIAM Journal on Computing · doi:10.1137/s0097539705447323 · Cited by 457
Higher order decompositions of ordered operator exponentials
Wiebe, N., Berry, D., Høyer, P., & Sanders, B. C. (2010) · Journal of Physics A: Mathematical and Theoretical · doi:10.1088/1751-8113/43/6/065203 · Cited by 208 · cited 2×
“When direct access to Hamiltonian evolutions is not possible, such evolutions can be simulated in the standard quantum circuit model by means of Trotter-Suzuki-like formulas [8, 29, 42].”
MethodQuantum Approach to Classical Statistical Mechanics
Somma, R. D., Batista, C. D., & Ortiz, G. (2007) · Physical Review Letters · doi:10.1103/physrevlett.99.030603 · Cited by 87
Self-citation
Cited by
Albash, T., & Lidar, D. A. (2018) · Reviews of Modern Physics · doi:10.1103/revmodphys.90.015002 · Cited by 1,546
Hamiltonian Simulation by Qubitization
Low, G. H., & Chuang, I. L. (2019) · Quantum · doi:10.22331/q-2019-07-12-163 · Cited by 854
Quantum Algorithms for Systems of Linear Equations Inspired by Adiabatic Quantum Computing
Subaşı, Y., Somma, R. D., & Orsucci, D. (2019) · Physical Review Letters · doi:10.1103/physrevlett.122.060504 · Cited by 183
Self-citationFast quantum computation at arbitrarily low energy
Jordan, S. P. (2017) · Physical Review A · doi:10.1103/physreva.95.032305 · Cited by 40
“Similar ideas have been used previously in [27,35].”
Metadata
- Authors
- Somma, R. D., & Boixo, S.
- Venue
- SIAM Journal on Computing
- Published
- 2013-01
- Volume
- 42
- Issue
- 2
- Pages
- 593-610
- ISSN
- 0097-5397 (ISSN-L)
- 1095-7111
- OpenAlex
- W2098246547
- Cited by
- 43
- References
- 11
- FWCI
- 4.79
- Type
- journal article
- Language
- en
- Open access
- green
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.