PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Query Complexity for Ground-State Preparation

Boyang Chen, Minbo Gao, Xinzhao Wang, Shuo Zhou

arXiv:2609.35668v2quant-phcs.CCcs.DS

TL;DR

Ground-state preparation is computationally hard in general, and efficient guarantees rely on initial-state and low-energy spectral information. This paper uses spectral filtering with transducer composition to prepare the ground state. Its expected U_H query count has a matching lower bound, and its worst-case U_H bound matches Somma and de Wolf [SdW26].

  • Problem

    Ground-state preparation is computationally hard in general, so efficient algorithms typically assume additional information about the initial state and low-energy spectrum.

    Source: §1 · p. 3

  • Method

    The algorithms use a constant-accuracy spectral filter and transducer composition to prepare constant ground-state overlap, then apply high-accuracy filtering.

    Source: §1 · p. 4

  • Results

    The expected U_H query count has a matching lower bound, and the worst-case U_H bound matches Somma and de Wolf [SdW26].

    Source: §1 · p. 3

  • Takeaways & Limitations

    Transducer composition removes the remaining log(1/γ) overhead in composing O(1/γ) ground-state reflections.

    Source: §1 · p. 4

    The U_I lower bounds require restricting calls to U_H.

    Source: §1 · p. 3

Abstract

from arXiv · show

We determine the optimal query complexity of ground-state preparation to trace-distance error $\varepsilon$ when an energy threshold in the spectral gap is known. Let $U_H$ be an $\alpha$-block-encoding of a Hamiltonian with unique ground state $|\psi_0\rangle$, and suppose $|\langle\psi_0|U_I|0\rangle|\ge\gamma$ for a state-preparation oracle $U_I$. The threshold lies at least $\Delta/2$ above the ground-state energy and at least $\Delta/2$ below every excited-state energy. We give two algorithms that prepare a state within trace distance $\varepsilon$ of the ground state. One uses $O((\alpha/\Delta)(\gamma^{-1}+\log(1/\varepsilon)))$ calls to $U_H$ in expectation; the other uses $O((\alpha/(\gamma\Delta))\log(1/\varepsilon))$ calls to $U_H$ in the worst case. We prove a lower bound matching the expected query count; the corresponding worst-case lower bound follows from Somma and de Wolf [SdW26]. The respective bounds on calls to $U_I$ are $O(1/\gamma)$ in expectation and $O(\gamma^{-1}\log(1/\varepsilon))$ in the worst case. On $(N+1)$-dimensional systems, these $U_I$ bounds are also optimal when the expected or worst-case count of $U_H$ calls, respectively, is $o((\alpha/\Delta)\sqrt N)$. Both algorithms use a constant-accuracy spectral filter to construct a purifier, which we then sequentially compose during amplitude amplification to prepare a state with constant overlap with the ground state. The expected-query algorithm repeats the preparation followed by one high-accuracy spectral filter until success. The worst-case algorithm uses filters of increasing accuracy and limits the total number of queries.

1 Introduction

Ground-state preparation is computationally hard in general, so efficient guarantees rely on information about the initial state and low-energy spectrum. This paper gives expected- and worst-case query guarantees under a known spectral threshold, with a matching expected-query lower bound and a worst-case bound matching Somma and de Wolf [SdW26].

1 Introduction

  • Ground-state preparation supports studies of ground-state properties, but efficient general methods would solve the QMA-complete Local Hamiltonian problem after energy estimation.The paper therefore situates efficient guarantees in settings with additional initial-state and low-energy spectral information.Source: §1 · p. 3
  • The model assumes a unique ground state, an α-block-encoding, initial overlap at least γ, and a known threshold at least Δ/2 from ground and excited energies.The preparation target is trace-distance error at most ε.Source: §1 · p. 3
  • The expected-query algorithm has a matching lower bound on E[qH] and uses E[qI] = O(1/γ).The paper also gives a worst-case algorithm whose query counts are bounded on every run.Source: §1 · p. 3
  • The worst-case qH bound matches Somma and de Wolf [SdW26]; the qI lower bounds require restricting qH to o((α/Δ)√N) on (N+1)-dimensional systems.At constant error, O((α/Δ)√N) qH calls suffice without qI.Source: §1 · p. 3
  • Transducer composition removes the remaining log(1/γ) overhead when composing O(1/γ) ground-state reflections, enabling the two-stage expected-query algorithm to repeat until success.A constant-accuracy filter and purifier prepare constant ground-state overlap, followed by one high-accuracy spectral filter.Source: §1 · pp. 3–4
  • The worst-case algorithm applies filters of increasing accuracy, restarts when a filter rejects, and imposes a query cutoff to avoid multiplying filtering cost by log(1/ε).Rejected attempts rarely reach the more expensive filters.Source: §1 · p. 4

2 Problem setting and results

The section formalizes ground-state preparation with a block-encoded Hamiltonian, a state-preparation oracle, and a known threshold separating ground and excited energies. It states expected- and worst-case query guarantees and lower bounds for the resulting task.

2.1 Oracle and output model

  • The model assumes a unique ground state, an α-block-encoding of H, an input state with ground-state overlap at least γ, and a known threshold at least ∆/2 from ground and excited energies.Error is measured in trace distance; runs may use random query counts and may report success or failure.Source: §2.1 · p. 6

2.2 Main results

  • The expected-query algorithm has a matching lower bound on its expected number of Hamiltonian queries.The section introduces this algorithm and lower bound as its first main result.Source: §2.2 · p. 6
  • The worst-case algorithm matches the Hamiltonian-query lower bound of Somma and de Wolf [SdW26].Its output is within trace distance ε of the ground state on every valid instance.Source: §2.2 · p. 7
  • A separate guarantee permits failure with probability at most ζ, with the output within trace distance ε of the ground state conditioned on success.The theorem states this guarantee for every valid instance.Source: §2.2 · p. 7

3 Algorithm overview

The algorithms use amplitude amplification to create constant ground-state overlap, then spectral filtering to reach error ε. Transducer composition reduces reflection overhead, while final filtering strategies address expected and worst-case query bounds.

3 Algorithm overview

  • After normalization, the ground eigenvalue lies in [−1, −δ] and excited eigenvalues lie in [δ, 1], enabling spectral filtering and amplitude amplification.The overview uses these normalized spectral bounds to describe the two algorithm stages.Source: §3 · p. 8

3.1 Spectral filtering and approximate reflection

  • An approximate ground-state reflection built from a spectral filter costs O((α/∆) log(1/η)) Hamiltonian queries.The filter approximately preserves the ground-state component and suppresses excited-state components.Source: §3.1 · p. 8

3.2 Amplitude amplification and error accumulation

  • A two-stage approach first amplifies to constant ground-state overlap, then applies one high-accuracy filter to reach trace-distance error O(ε).The first stage can use η = Θ(γ) for O(1/γ) amplification iterations; the final filter succeeds with constant probability.Source: §3.2 · p. 9, §3.4 · p. 10

3.3 Ground-state reflection by a transducer

  • Transducers compose ground-state and input-state reflections without introducing approximation error at each step.Sequential composition applies the circuit implementation theorem once to the complete transducer.Source: §3.3 · pp. 9–10

3.4 Final filtering

  • Increasing-accuracy filters suppress excited-state components before costly filters, while limiting attempts and total queries bounds worst-case use.The successful attempt ends with a filter of error O(ε), using O((α/∆) log(1/ε)) Hamiltonian queries.Source: §3.4 · p. 11

4 Preliminaries

This section develops the representations and tools used throughout the paper, including spectral filtering, transducer composition, and purifier construction, along with their implementation costs and conditions. It also provides purifier-unitary implementation details and mathematical tools for query lower bounds, including a trigonometric growth inequality and a hybrid argument for comparing oracle circuits.

4.1 Shifting and rescaling the Hamiltonian

  • Shifting the threshold to zero and rescaling preserves H’s eigenvectors, yields a 1-block-encoding using one controlled U_H call, and separates ground and excited energies by ±δ.The rescaling uses αbar = α + |μ|, with αbar < 2α.Source: §4.1 · pp. 11–12

4.2 Spectral filtering by QSVT

  • The QSVT filter approximates 1 on [−1, −δ] and 0 on [δ, 1], using O(δ^-1 log(1/η)) queries and O((a_H + 1)δ^-1 log(1/η)) gates.The approximation error is at most η on both intervals.Source: §4.2 · p. 12

4.3 Transducers

  • For inputs with transduction complexity W at most W0, a circuit approximates the transduction action within εc using controlled executions and O(K) additional gates.The catalyst is not an input to this circuit.Source: §4.3 · p. 13

The same implementation has gate count

  • Sequential composition applies transduction actions in order, with component complexities and squared norms of intermediate public states adding; functional composition substitutes one transduction action for another’s input oracle.Source: §4.3 · p. 14, The same implementation has gate count · p. 15

4.4 Purifier

  • The canonical purifier uses two oracle calls and transduces a state to itself or its negative according to whether a measured qubit yields outcome 1 with probability below or above 1/2.With a finite counter of size D, its work-unitary gate count is O(log D), and each application shifts the counter by at most one.Source: §4.4 · pp. 16, 17, 19
  • The work unitary uses controlled counter shifts costing O(b) gates and a zero test costing O(b) one- and two-qubit gates, where b = log2 D.B0 and B2 each use one controlled shift, B1 uses two, and clock conditioning and updating add constant gate overhead.Source: §4.4 · p. 19

4.5 Trigonometric polynomial inequalities

  • The query lower bounds use a trigonometric growth inequality whose range beyond s ≤ π/2 follows from [TY18, Theorem 1.1].The usual form for s ≤ π/2 appears in [BE95, Theorem 5.1.2].Source: §4.5 · p. 19

4.6 Hybrid argument

  • The hybrid argument bounds circuit differences using query-wise oracle changes on reference-circuit states, with query types contributing at most c_j Q_j.Here Q_j is the number of queries of type j.Source: §4.6 · p. 19

5 Ground-state reflection

A constant-accuracy spectral test separates the ground state from excited states. A purifier applied with a shared reflection oracle can then be composed into a constant-complexity transducer for the ground-state reflection.

5 Ground-state reflection

  • The ground-state reflection is realized by testing each eigenstate, applying the purifier, then undoing the test unitary.The purifier preserves the ground-state test state and negates the excited-state test states.Source: §5 · p. 20

5.1 Constant-accuracy spectral test

  • The constant-accuracy test makes the answer-qubit probability at most 19/100 on the ground state and at least 99/100 on excited states.The test is built by applying the filter and recording whether its filter ancilla is nonzero.Source: §5.1 · pp. 20–21

5.2 Reflection about the test states

  • One reflection oracle serves all test states because their associated subspaces are mutually orthogonal and invariant under the test projectors and oracle.The shared oracle is Oref = 2Π − I on each K(φk).Source: §5.2 · pp. 21–22

5.3 Purifier on superpositions

  • Orthogonal catalysts let the same purifier transduce superpositions of test states while retaining bounded transduction complexity.The construction chooses catalysts in orthogonal spaces for the different φk.Source: §5.3 · pp. 22–23

5.4 Ground-state reflection transducer

  • The ground-state reflection has a canonical transducer with O(1) transduction complexity on every normalized system input.The construction functionally and sequentially composes the purifier with transducers for the test and its inverse.Source: §5.4 · pp. 23–25

6 Ground-state overlap amplification

Randomized Grover iterations amplify an initially unknown ground-state overlap using a random iteration count. Finite transducer circuits implement those iterations with bounded oracle-query costs and retain constant ground-state overlap.

6.1 Randomized Grover iterations

  • Choosing the Grover iteration count uniformly from a range of size O(1/γ) handles the unknown overlap β when only β ≥ γ is known.The ideal procedure outputs |ϕ⟩ with probability 1/2 and otherwise samples j uniformly from {0, …, M −1}, with M := ⌈2/γ⌉.Source: §6.1 · p. 25
  • The ideal randomized procedure has ground-state overlap greater than 3/16 for every allowed initial overlap.The proof gives a stronger bound in the larger-angle case.Source: §6.1 · p. 26

6.2 Transducer implementation

  • For each fixed j, circuit Cj approximates the transducer action with O(j/δ) Hamiltonian queries and O(j) state-preparation queries.The circuit output is within Euclidean distance 1/32 of the ideal state, which bounds the reduced system's trace-distance error.Source: §6.2 · pp. 27–28
  • The implemented randomized procedure produces a state with constant ground-state overlap, using worst-case query counts QI = O(1/γ) and QH = O(1/(γδ)) = O(α/(γ∆)).Its query bounds follow by limiting j to values below M ≤ 3/γ.Source: §6.2 · p. 30

7 Final filtering

The section first uses a high-accuracy spectral filter to turn the constant-overlap state into an accurate ground-state preparation with constant success probability. It then stages filters and limits their total query budget to reduce failure probability with bounded queries.

7.1 Constant-success preparation

  • One final filter yields trace-distance error at most ε on success, and the one-run algorithm succeeds with probability at least 1/16.The filter has accuracy ε/8 and uses no state-preparation query.Source: §7.1 · pp. 31–32

7 Final filtering

  • Repeating independent runs until success gives expected query bounds because each run succeeds with probability at least 1/16 and the mean number of runs is at most 16.The output conditioned on success retains the per-run trace-distance guarantee.Source: §7.1 · p. 32

7.2 Reducing the failure probability

  • The staged-filter algorithm succeeds with probability at least 1 − ζ and, conditioned on success, has trace-distance error at most ε.Filters of increasing accuracy restart an attempt at the first rejection; the budget check cannot halt an attempt before its first acceptance finishes.Source: §7.2 · pp. 33, 36

8 Optimality of the query bounds

The section establishes lower bounds on Hamiltonian and state-preparation queries using overlap, precision, and oracle-comparison arguments. Together, these results support optimality claims under the stated query models and dimensional conditions.

8.1.1 Dependence on the initial overlap

  • The overlap lower bound is adapted to the paper's block-encoding access and success-conditioned output model from Arihara and Murao [AM26].The cited lemma covers algorithms with unrestricted access to the state-preparation oracle and its inverse.Source: §8.1.1 · p. 37

8.1.2 Dependence on the target precision

  • The precision lower bound adapts a trigonometric-polynomial argument to block-encoding queries and success-conditioned ground-state preparation.The construction compares Hamiltonians whose ground states differ near θ = 0 but agree when |sin θ| is large.Source: §8.1.2 · p. 38
  • Combining overlap and precision bounds gives an expected Hamiltonian-query lower bound of Ω(1/(γδ)) and Ω(δ^-1 log(1/ε)) terms.The argument truncates a random-query algorithm before applying the fixed-query bounds.Source: §8.1.2 · pp. 39–40
  • The worst-case Hamiltonian-query lower bound uses the Somma and de Wolf hard family for small γ and the precision bound for constant γ [SdW26].For constant γ, the passage gives Ω((α/∆) log(1/ε)).Source: §8.1.2 · p. 40

8.2 State-preparation queries

  • A query tradeoff yields a state-preparation-query lower bound when the Hamiltonian-query contribution vanishes; truncation extends the tradeoff to expected counts.The section also derives the worst-case state-preparation lower bound by rescaling the construction in Lemma 8.3.Source: §8.2 · pp. 42–43

Statement on AI use

The authors report using large language models to develop detailed constructions and proofs, then reviewing and verifying the arguments, substantially rewriting the manuscript, and taking responsibility for its claims, proofs, and citations.

Statement on AI use

  • The authors used large language models to develop detailed constructions and proofs, then reviewed, verified, and substantially rewrote the manuscript.They take full responsibility for its claims, proofs, and citations.Source: Statement on AI use · p. 43

A Proof of the overlap lower bound with controlled queries

The proof constructs instances with a shared preparation oracle and distinct ground states, then establishes a query lower bound that also holds for controlled calls.

A Proof of the overlap lower bound with controlled queries

Loading 2609.35668v2…