Record W2783493337 · doi:10.22331/q-2019-09-30-189

The complexity of simulating local measurements on quantum systems

2019· article· lv· W2783493337 on OpenAlexfundno aff

Bibliographic record

VenueQuantum · 2019

Typearticle

Languagelv

FieldComputer Science

TopicQuantum Computing Algorithms and Architecture

Canadian institutionsnot available

FundersSimons Institute for the Theory of Computing, University of California BerkeleyNatural Sciences and Engineering Research Council of CanadaGovernment of CanadaVirginia Commonwealth UniversityNational Science Foundation

KeywordsObservableHamiltonian (control theory)QuantumGround stateUpper and lower boundsTuring machineTask (project management)Quantum complexity theoryComputation

DOI10.22331/q-2019-09-30-189

Abstract

fetched live from OpenAlex

An important task in quantum physics is the estimation of local quantities for ground states of local Hamiltonians. Recently, [Ambainis, CCC 2014] defined the complexity class<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>P</mml:mi></mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>Q</mml:mi><mml:mi>M</mml:mi><mml:mi>A</mml:mi></mml:mrow><mml:mo stretchy="false">[</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>l</mml:mi><mml:mi>o</mml:mi><mml:mi>g</mml:mi></mml:mrow><mml:mo stretchy="false">]</mml:mo></mml:mrow></mml:msup></mml:math>, and motivated its study by showing that the physical task of estimating the expectation value of a local observable against the ground state of a local Hamiltonian is<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>P</mml:mi></mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>Q</mml:mi><mml:mi>M</mml:mi><mml:mi>A</mml:mi></mml:mrow><mml:mo stretchy="false">[</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>l</mml:mi><mml:mi>o</mml:mi><mml:mi>g</mml:mi></mml:mrow><mml:mo stretchy="false">]</mml:mo></mml:mrow></mml:msup></mml:math>-complete. In this paper, we continue the study of<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>P</mml:mi></mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>Q</mml:mi><mml:mi>M</mml:mi><mml:mi>A</mml:mi></mml:mrow><mml:mo stretchy="false">[</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>l</mml:mi><mml:mi>o</mml:mi><mml:mi>g</mml:mi></mml:mrow><mml:mo stretchy="false">]</mml:mo></mml:mrow></mml:msup></mml:math>, obtaining the following lower and upper bounds.Lower bounds (hardness results): - The<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>P</mml:mi></mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>Q</mml:mi><mml:mi>M</mml:mi><mml:mi>A</mml:mi></mml:mrow><mml:mo stretchy="false">[</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>l</mml:mi><mml:mi>o</mml:mi><mml:mi>g</mml:mi></mml:mrow><mml:mo stretchy="false">]</mml:mo></mml:mrow></mml:msup></mml:math>-completeness result of [Ambainis, CCC 2014] requires<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>O</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>log</mml:mi><mml:mo>⁡</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:math>-local observables and Hamiltonians. We show that simulating even a<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mtext class="MJX-tex-mathit" mathvariant="italic">single qubit</mml:mtext></mml:mrow></mml:math>measurement on ground states of<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mn>5</mml:mn></mml:math>-local Hamiltonians is<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>P</mml:mi></mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>Q</mml:mi><mml:mi>M</mml:mi><mml:mi>A</mml:mi></mml:mrow><mml:mo stretchy="false">[</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>l</mml:mi><mml:mi>o</mml:mi><mml:mi>g</mml:mi></mml:mrow><mml:mo stretchy="false">]</mml:mo></mml:mrow></mml:msup></mml:math>-complete, resolving an open question of Ambainis.- We formalize the complexity theoretic study of estimating two-point correlation functions against ground states, and show that this task is similarly<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>P</mml:mi></mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>Q</mml:mi><mml:mi>M</mml:mi><mml:mi>A</mml:mi></mml:mrow><mml:mo stretchy="false">[</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>l</mml:mi><mml:mi>o</mml:mi><mml:mi>g</mml:mi></mml:mrow><mml:mo stretchy="false">]</mml:mo></mml:mrow></mml:msup></mml:math>-complete. - We identify a flaw in [Ambainis, CCC 2014] regarding a<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>P</mml:mi></mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>U</mml:mi><mml:mi>Q</mml:mi><mml:mi>M</mml:mi><mml:mi>A</mml:mi></mml:mrow><mml:mo stretchy="false">[</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>l</mml:mi><mml:mi>o</mml:mi><mml:mi>g</mml:mi></mml:mrow><mml:mo stretchy="false">]</mml:mo></mml:mrow></mml:msup></mml:math>-hardness proof for estimating spectral gaps of local Hamiltonians. By introducing a ``query validation'' technique, we build on [Ambainis, CCC 2014] to obtain<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>P</mml:mi></mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>U</mml:mi><mml:mi>Q</mml:mi><mml:mi>M</mml:mi><mml:mi>A</mml:mi></mml:mrow><mml:mo stretchy="false">[</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>l</mml:mi><mml:mi>o</mml:mi><mml:mi>g</mml:mi></mml:mrow><mml:mo stretchy="false">]</mml:mo></mml:mrow></mml:msup></mml:math>-hardness for estimating spectral gaps under polynomial-time Turing reductions. Upper bounds (containment in complexity classes): -<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>P</mml:mi></mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>Q</mml:mi><mml:mi>M</mml:mi><mml:mi>A</mml:mi></mml:mrow><mml:mo stretchy="false">[</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>l</mml:mi><mml:mi>o</mml:mi><mml:mi>g</mml:mi></mml:mrow><mml:mo stretchy="false">]</mml:mo></mml:mrow></mml:msup></mml:math>is thought of as ``slightly harder'' than QMA. We justify this formally by exploiting the hierarchical voting technique of [Beigel, Hemachandra, Wechsung, SCT 1989] to show<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>P</mml:mi></mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>Q</mml:mi><mml:mi>M</mml:mi><mml:mi>A</mml:mi></mml:mrow><mml:mo stretchy="false">[</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>l</mml:mi><mml:mi>o</mml:mi><mml:mi>g</mml:mi></mml:mrow><mml:mo stretchy="false">]</mml:mo></mml:mrow></mml:msup><mml:mo>⊆</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>P</mml:mi><mml:mi>P</mml:mi></mml:mrow></mml:math>. This improves the containment<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>Q</mml:mi><mml:mi>M</mml:mi><mml:mi>A</mml:mi></mml:mrow><mml:mo>⊆</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>P</mml:mi><mml:mi>P</mml:mi></mml:mrow></mml:math>[Kitaev, Watrous, STOC 2000]. This work contributes a rigorous treatment of the subtlety involved in studying oracle classes in which the oracle solves a<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>p</mml:mi><mml:mi>r</mml:mi><mml:mi>o</mml:mi><mml:mi>m</mml:mi><mml:mi>i</mml:mi><mml:mi>s</mml:mi><mml:mi>e</mml:mi></mml:math>problem. This is particularly relevant for quantum complexity theory, where most natural classes such as BQP and QMA are defined as promise classes.

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.

How this classification was reachedexpand

Full frame distilled prediction

Teacher imitation

Not calibrated prevalence, not ground truth. Human validation pending. Learned from the 10,348 direct Codex labels and 10,348 direct Gemma labels. Candidate is the union of thresholded teacher heads; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels or direct frontier model labels.

metaresearch head score (Codex)0.002

metaresearch head score (Gemma)0.000

Version: codex-gemma-dda1882f352aValidation status: machine_predicted_unvalidated

Candidate categoriesMeta-epidemiology (narrow)

Consensus categoriesnone

DomainCandidate signal: none · Consensus signal: none

Study designCandidate signal: Simulation or modeling · Consensus signal: none

GenreCandidate signal: Empirical · Consensus signal: Empirical

Teacher disagreement score0.529

Threshold uncertainty score1.000

Codex and Gemma teacher scores by category

Category	Codex	Gemma
Metaresearch	0.002	0.000
Meta-epidemiology (narrow)	0.001	0.000
Meta-epidemiology (broad)	0.001	0.000
Bibliometrics	0.000	0.001
Science and technology studies	0.001	0.001
Scholarly communication	0.000	0.000
Open science	0.002	0.001
Research integrity	0.000	0.001
Insufficient payload (model declined to judge)	0.000	0.000

Machine scores (provisional)

The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.

Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.

Opus teacher head0.066

GPT teacher head0.277

Teacher spread0.211 · how far apart the two teachers sit on this one work

Validation statusscore_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from it

Classification

machine, unvalidated

Machine predicted; a candidate call from one teacher head, not a consensus.

Meta-epidemiology (narrow)

Study designSimulation or modeling

Domainnot available

GenreEmpirical

How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".

Quick stats

Citations11

Published2019

Admission routes1

Has abstractyes

Download record (JSON)Report an issue with this record

Explore more

Same venueQuantum→Same topicQuantum Computing Algorithms and Architecture→French-language works237,207→