PaperlayerView exact revision on arXiv

Source-linked AI summary

Ground state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices

Yulong Dong, Lin Lin, Yu Tong

arXiv:2204.05955v2quant-phmath.NAphysics.comp-ph

TL;DR

The paper addresses the resource overhead of block encoding for ground-state preparation and energy estimation on early fault-tolerant quantum computers. It develops QET-U from controlled Hamiltonian evolution, using few ancillas and limited multi-qubit control, and obtains short-depth and near-optimal query-complexity algorithms. Numerical experiments on the transverse field Ising model support accurate noiseless estimation at modest evolution depths, while the required noise level exceeds current NISQ capability.

  • Problem

    Block-encoding-based ground-state algorithms can require large ancilla, gate, depth, and multi-qubit-control overheads that conflict with early fault-tolerant constraints.

  • Method

    QET-U applies real-polynomial transformations using controlled Hamiltonian evolution, one ancilla qubit, and no multi-qubit control, with a control-free variant for certain Hamiltonians.

  • Results

    The short-depth method achieves e O(ϵ−1γ−2) energy-estimation complexity, while allowing Toffoli gates improves this to e O(ϵ−1γ−1) with increased depth.

  • Takeaways & Limitations

    QET-U provides early-fault-tolerant-compatible algorithms using no more than 3 ancilla qubits, with practical Trotter-based implementation demonstrated for the transverse field Ising model.

  • Takeaways & Limitations

    Reducing preparation query complexity to near-optimal scaling without multi-qubit controlled operations remains an open question, including independence of additional gates from system size n.

Abstract

from arXiv · show

Under suitable assumptions, the algorithms in [Lin, Tong, Quantum 2020] can estimate the ground state energy and prepare the ground state of a quantum Hamiltonian with near-optimal query complexities. However, this is based on a block encoding input model of the Hamiltonian, whose implementation is known to require a large resource overhead. We develop a tool called quantum eigenvalue transformation of unitary matrices with real polynomials (QET-U), which uses a controlled Hamiltonian evolution as the input model, a single ancilla qubit and no multi-qubit control operations, and is thus suitable for early fault-tolerant quantum devices. This leads to a simple quantum algorithm that outperforms all previous algorithms with a comparable circuit structure for estimating the ground state energy. For a class of quantum spin Hamiltonians, we propose a new method that exploits certain anti-commutation relations and further removes the need of implementing the controlled Hamiltonian evolution. Coupled with Trotter based approximation of the Hamiltonian evolution, the resulting algorithm can be very suitable for early fault-tolerant quantum devices. We demonstrate the performance of the algorithm using IBM Qiskit for the transverse field Ising model. If we are further allowed to use multi-qubit Toffoli gates, we can then implement amplitude amplification and a new binary amplitude estimation algorithm, which increases the circuit depth but decreases the total query complexity. The resulting algorithm saturates the near-optimal complexity for ground state preparation and energy estimating using a constant number of ancilla qubits (no more than 3).

I. INTRODUCTION

The paper targets ground-state preparation and energy estimation on early fault-tolerant devices, where qubit count, circuit depth, and multi-qubit controls are constrained. It introduces QET-U and two algorithm families that trade circuit depth against query complexity while using only a few ancillas.

  • Block encoding enables near-optimal algorithms but often requires many ancillas and costly multi-qubit controls, making it unsuitable for early fault-tolerant devices.
  • Hamiltonian evolution offers a lower-overhead input model, especially when H is decomposed into Pauli operators and simulated with Trotter formulas.
  • QET-U prepares states proportional to f(H)|φ0⟩ using controlled forward and backward evolution, one ancilla qubit, and no multi-qubit controlled operation.
  • The short-query-depth algorithms avoid multi-qubit controls, while near-optimal algorithms use low-level controls for improved total query complexity; both use at most 2 or 3 ancillas.
  • The short-depth energy-estimation algorithm improves γ dependence from e O(γ−4) to e O(γ−2) and outperforms prior comparable algorithms, while the near-optimal version matches the best known scaling.
  • For ground-state preparation, the short-depth algorithm improves precision and γ dependence over semi-classical phase estimation, while the near-optimal algorithm reaches e O(γ−1).

II. QUANTUM EIGENVALUE TRANSFORMATION OF UNITARY MATRICES

QET-U transforms a Hamiltonian function using symmetric phase factors interleaved with controlled forward and backward evolution. The construction supports polynomial transformations with a compact ancilla structure and can use Trotterized evolution in practice.

  • QET-U prepares f(H)|ψ⟩ normalized by its norm through alternating controlled U, ancilla X rotations, and controlled U† operations.
  • The function information is encoded in symmetric phase factors, whose symmetry enables the transformed function to be real.
  • For any bounded even real polynomial F(x) of degree d, QET-U provides a symmetric phase sequence implementing the corresponding polynomial block.
  • Trotter decomposition can approximate U=e−iH without ancillas by partitioning the evolution into r steps of duration τ=r−1.
  • The method is analyzed primarily with exact U, while polynomial approximation and binary-search errors account for the remaining error sources.

III. GROUND-STATE ENERGY ESTIMATION AND GROUND-STATE PREPARATION

The QET-U framework estimates ground-state energy and prepares ground states using Hamiltonian evolution, with separate short-depth and near-optimal settings. Under an initial-overlap assumption, the energy-estimation algorithms use one or three ancilla qubits, while ground-state preparation additionally assumes a spectral gap.

  • Problem setup: QET-U accesses H through e^-iH and applies real-polynomial transformations to an initial state with overlap at least γ with the ground state.Ground-state preparation additionally assumes a spectral gap Δ.
  • Short query depth: The short-depth energy-estimation algorithm uses e O(ϵ^-1γ^-2 log(ϑ^-1)) queries to (controlled-) U and one ancilla qubit.It requires no extra two-qubit gates beyond those in (controlled-) U.
  • Near-optimal query complexity: The near-optimal energy-estimation algorithm uses e O(ϵ^-1γ^-1 log(ϑ^-1)) queries to (controlled-) U and three ancilla qubits.Its additional gate count is e O(nγ^-1 log(ϵ^-1ϑ^-1) + ϵ^-1γ^-1 log(ϑ^-1)).
  • Trade-off: The near-optimal algorithm is described as the first constant-ancilla method achieving e O(γ^-1ϵ^-1) ground-state energy-estimation query complexity.The framework presents a trade-off between query depth and query complexity.

III.1. Algorithms with short query depths

The short-depth algorithms use polynomial filtering and repeated binary decisions to estimate energy or prepare the ground state. They prioritize low query depth, using one ancilla qubit and Monte Carlo-based binary amplitude estimation.

  • Polynomial filtering: QET-U applies an even polynomial F(cos(H/2)) that preserves the ground-state component while suppressing orthogonal components.The polynomial has degree O(Δ^-1 log ϵ^-1) for ground-state preparation.
  • Ground-state preparation: Ground-state preparation achieves fidelity 1 −ϵ with probability at least 2/3 using e O(γ^-2Δ^-1 log(ϵ^-1)) queries to (controlled-) U and one ancilla qubit.The procedure can be repeated to increase the success probability.
  • Energy estimation: The fuzzy bisection problem distinguishes λ0 ≤ x −h from λ0 ≥ x +h, allowing binary search to estimate the ground-state energy.Either output is permitted in the interval between these thresholds.
  • Binary amplitude estimation: Monte Carlo binary amplitude estimation uses O(γ1^-2 log(ϑ′^-1)) queries to W, no additional ancillas, and maximal query depth O(1).The method distinguishes success amplitudes below γ1 from those above γ2 when their ratio is bounded by a constant.
  • Energy estimation: The short-depth energy-estimation algorithm performs binary amplitude estimation at O(log(ϵ^-1)) binary-search steps, yielding e O(ϵ^-1γ^-2 log(ϑ^-1)) queries to (controlled-) U.The per-step failure probability is adjusted to obtain the target final success probability.

III.2. Quantum phase estimation revisited

QET-U revisits phase estimation by treating an eigenstate as an initial state with unit overlap. The resulting procedure reaches Heisenberg-limited precision using one copy of the eigenstate.

  • Reduction: Phase estimation is recast as energy estimation for U = e^-iH when the input is an eigenstate with γ = 1.Other eigenvalues do not contribute because the initial state has zero overlap with their eigenstates.
  • Algorithm: The algorithm repeatedly solves fuzzy bisection to estimate the eigenphase λ.This procedure is essentially the energy-estimation algorithm based on binary search.
  • Cost: e O(ϵ^-1 log(ϑ^-1)) applications of controlled U and its inverse estimate λ to precision ϵ with probability at least 1 −ϑ.The algorithm uses a single copy of the eigenstate and O(ϵ^-1(log(ϑ^-1) + log log(ϵ^-1))) additional one-qubit gates.
  • Resource use: The single eigenstate copy can be reused because the circuit preserves an eigenstate up to a phase factor.Consequently, the state need not be prepared repeatedly.

III.3. Algorithms with near-optimal query complexities

The near-optimal algorithms combine QET-U with improved binary amplitude estimation and amplitude amplification. They recover near-optimal query scaling while using only a constant number of ancilla qubits, at the cost of deeper circuits and multi-qubit Toffoli operations.

  • Circuit resources: Amplitude amplification requires an (n + 1)-bit Toffoli-based reflection, which can be costly on early fault-tolerant devices.The Toffoli implementation uses O(n) elementary one- or two-qubit gates.
  • Ground-state preparation: Near-optimal ground-state preparation achieves fidelity 1 −ϵ with probability 2/3 using e O(γ^-1Δ^-1 log(ϵ^-1)) queries and two ancilla qubits.Amplitude amplification provides the improved γ dependence.
  • Binary amplitude estimation: QET-U binary amplitude estimation reduces the additional ancilla requirement to one qubit and uses O((γ2 −γ1)^-1 log(ϑ′^-1)) queries to W.The method treats the amplitude-estimation walk operator as a Hamiltonian evolution operator.
  • Parameter knowledge: Without prior knowledge of μ, ground-state preparation can first estimate the energy to additive error O(Δ) and then run the preparation algorithm.The energy-estimation step supplies the parameter needed by the preparation procedure.
  • Ground-state preparation: The general preparation theorem uses e O(Δ^-1γ^-1 poly log(ϵ^-1ϑ^-1)) queries and three ancilla qubits.It achieves fidelity at least 1 −ϵ with probability at least 1 −ϑ.

IV. CONVEX-OPTIMIZATION-BASED METHOD FOR CONSTRUCTING APPROXIMATING POLYNOMIALS

The paper constructs approximating polynomials by discretizing the domain, solving a convex min-max problem for Chebyshev coefficients, and converting the result into symmetric phase factors. Numerical optimization produces near-optimal approximations for shifted sign functions and supports substantial polynomial degrees.

  • Polynomial construction: The target even polynomial is expanded in Chebyshev polynomials, reducing approximation to finding coefficients c_k on a discretized domain.The coefficient matrix is A_jk = T_2k(x_j), with Chebyshev-grid points used to formulate the discrete problem.
  • Polynomial construction: The coefficients are obtained from a convex optimization problem imposing |F(x_j)| ≤ c at sampled points.The sampled constraint relaxes the global bound |F(x)| ≤ 1, with c chosen close to 1.
  • Approximation quality: The sampled min-max formulation yields a near-optimal solution in the L∞ norm in both asymptotic and pre-asymptotic regimes.The relaxation's overshoot between grid points is described as negligible in practice when c is sufficiently close to 1.
  • Phase-factor implementation: The resulting Chebyshev coefficients determine symmetric phase factors for implementing the polynomial through QET-U.Parity reduces the number of polynomial degrees of freedom to approximately half the polynomial degree.
  • Numerical construction: Numerical optimization finds near-optimal polynomials for degrees around 5,000 and phase factors for degrees around 10,000 on a laptop.A shifted-sign example with d = 20 and d = 80 exhibits the pointwise approximation behavior and equioscillation property.

V. NUMERICAL COMPARISON WITH QPE FOR GROUND-STATE ENERGY ESTIMATION

The numerical study compares the paper's ground-state energy algorithm with single-ancilla quantum phase estimation using a semiclassical Fourier transform. At comparable target accuracy, the proposed method requires fewer queries and improves the overlap dependence from γ^-4 to γ^-2.

  • Experimental setup: The experiment compares query counts and errors for a 200 × 200 Hamiltonian with randomly generated spectrum and target accuracy ϵ ≤ 10^-3.The proposed method and semiclassical-Fourier-transform QPE are both simulated classically against the exact ground-state energy.
  • Polynomial diagnostics: Figure 2 evaluates shifted-sign polynomial approximations and pointwise errors for degrees d = 20 and d = 80.The approximation and error are shown over [σmin, σ−] ∪ [σ+, σmax].
  • Query complexity: The proposed algorithm uses significantly fewer queries than QPE at comparable accuracy, improving asymptotic overlap scaling from γ^-4 to γ^-2.The comparison also reports fewer actual queries for moderately small values of γ.
  • Accuracy: For target accuracy ϵ = 5 × 10^-4, the proposed method consistently reaches the target precision while QPE does not achieve higher precision.The mean absolute errors are used to check that the query advantage does not arise from a loose QPE error estimate.
  • Polynomial diagnostics: Figure 3 tracks exponential convergence of the maximum pointwise error as the convex-optimization polynomial degree increases.

VI. CONTROL-FREE IMPLEMENTATION OF QUANTUM SPIN MODELS

The paper removes direct controlled Hamiltonian evolution for suitable spin Hamiltonians by exploiting Pauli anti-commutation relations. For TFIM, the simplified QET-U circuit uses controlled Pauli strings and avoids their insertion between Trotter layers, reducing implementation cost when Trotterization is deep.

  • General construction: If each Hamiltonian component has an anti-commuting Pauli operator K_j, conjugation reverses its evolution time and enables control-free implementation.The number of required Pauli-string groups is ℓ, which is polynomial in n in the worst case but may be constant in practice.
  • TFIM: For TFIM, one Pauli string anti-commutes with both Hamiltonian components, so controlled evolution is implemented by controlled Pauli strings.This corresponds to ℓ = 1 and makes the QET-U circuit equivalent to the simplified circuit in Figure 5.
  • TFIM: The TFIM implementation requires only controlled single-qubit gates rather than controlled two-qubit gates for the Hamiltonian's Z_jZ_j+1 terms.
  • Trotterized implementation: The simplified TFIM circuit inserts 2d controlled Pauli strings, rather than O(dℓr) strings when controls are inserted between Trotter layers.Because the simplified circuit omits insertion between Trotter layers, its advantage grows when the Trotter-step count r is large.
  • Other models: Heisenberg and Fermi-Hubbard models require multiple anti-commuting Pauli strings, and the Heisenberg construction cannot cancel controls between Trotter layers.The paper identifies control-free implementation of more complex two-dimensional Fermi-Hubbard instances as future work.
  • Energy estimation: Energy estimation for the control-free implementation can use measurement frequencies of bit strings with standard VQE-type processing.

VII. NUMERICAL RESULTS FOR TFIM

The TFIM experiments demonstrate QET-U ground-state energy estimation under noiseless and depolarizing-noise simulations, with accuracy depending on polynomial degree and noise level.

  • IBM Qiskit simulations demonstrate QET-U energy estimation for the transverse field Ising model using only one- and two-qubit gate operations.The implementation uses Trotter-based Hamiltonian simulation and varies the number of qubits.
  • Noiseless estimates converge to the exact ground-state energy with modest polynomial degrees d between 10 and 30.The standard deviation from 30 repetitions is on the order of 10^-2 and is not visible in the top panels.
  • 10^-2 standard deviation is obtained from 30 repetitions in the simulated energy estimates.
  • Accurate noisy energy estimation requires depolarizing error rates rdplz of 10^-4 or less.This requirement is below the noise performance achieved by current NISQ devices, according to the passage.
  • For TFIM, increasing the qubit number decreases the spectral gap, requiring a higher polynomial degree for fixed-precision ground-state preparation.

VIII. CONCLUSION

The paper develops QET-U algorithms for early fault-tolerant quantum computers, replacing resource-intensive block encoding with Hamiltonian evolution and extending the approach to control-free and amplitude-estimation settings.

  • Existing block-encoding strategies can impose large resource overheads that conflict with early fault-tolerant limits on qubits, depth, and multi-qubit controls.
  • QET-U applies real-polynomial matrix functions using controlled Hamiltonian evolution, one ancilla qubit, and no multi-qubit control operations.
  • The QET-U energy-estimation algorithm has query complexity e O(ϵ^-1γ^-2) and outperforms previous algorithms with comparable circuit structure.
  • Allowing (n + 1)-bit Toffoli gates improves total energy-estimation complexity to e O(ϵ^-1γ^-1) while increasing circuit depth to e O(ϵ^-1γ^-1).
  • Ground-state preparation retains similar improvements in circuit depth and query complexity, but near-optimal scaling without multi-qubit controlled operations remains open.
  • For certain quantum spin Hamiltonians, anti-commutation relations enable a control-free QET-U implementation, while IBM Qiskit simulations achieve relatively accurate estimates at polynomial degree 10–30.

Appendix A: Brief summary of polynomial matrix transformations

The appendix situates QET-U among polynomial matrix-transformation methods and explains how it directly uses Hamiltonian evolution rather than first constructing a block encoding.

  • Polynomial matrix-transformation methods represent polynomials through products of parameterized SU(2) matrices and lift them to arbitrary-dimensional matrix transformations.
  • Block encoding embeds a rescaled matrix as a submatrix of a larger unitary, enabling polynomial transformations through QET and QSVT.
  • For sparse Hamiltonians, QET/QSVT can provide a more concise algorithm than the original quantum-walk-based QSP presentation.
  • QET-U uses the Hamiltonian evolution input model with a simpler, constructive derivation and an explicit procedure for evaluating phase factors.
  • QET-U directly queries U, avoiding the intermediate block encoding of cos(H) and approximate matrix logarithm required by a QSVT-based route.
  • This direct construction saves one ancilla qubit and may slightly reduce circuit depth relative to the intermediate QSVT procedure.

Appendix B: Quantum eigenvalue transformation for unitary matrices

The appendix derives QET-U from symmetric quantum signal processing and extends it to forward-and-backward evolution, while relating approximation requirements to Trotterized implementation costs.

  • Symmetric quantum signal processing represents bounded real polynomials with parity matching the polynomial degree through symmetric phase factors.
  • QET-U is derived by choosing shifted symmetric phase factors so the polynomial transformation is implemented on invariant eigenstate subspaces.
  • The Wz-convention encodes the polynomial variable in the Wz matrix and provides a representation for even real polynomials on [-1,1].
  • With an oracle for controlled forward and backward evolution, the circuit implements F(cos H) for any bounded even real polynomial F of degree d.
  • The controlled backward evolution V† can be implemented by conjugating V with Pauli X gates on the first qubit.
  • Trotterized implementations assume H is a sum of efficiently exponentiable terms and analyze gate complexity through the number and depth of Trotter steps.
  • Without amplitude amplification, the resulting query depth scales as e O(ϵ^-1 log(γ^-1)), while total queries scale as e O(ϵ^-1γ^-2 log(ϑ^-1)).

Appendix D: Binary amplitude estimation with a single ancilla qubit and QET-U

The appendix develops a single-ancilla QET-U procedure for binary amplitude estimation, using polynomial transformations and sampling to distinguish amplitude intervals. It also describes measurement-based ground-state energy estimation for TFIM and grouped Hamiltonians.

  • Binary amplitude estimation: Binary amplitude estimation distinguishes whether the success amplitude A is below γ1 or above γ2.The procedure assumes 0 ≤ γ1 < γ2 and excludes amplitudes between the thresholds.
  • Binary amplitude estimation: QET-U treats the product of two reflection operators as time evolution and applies polynomial transformations to estimate the relevant quantity by Monte Carlo sampling.The method contrasts this approach with phase estimation applied directly to the reflection-product operator.
  • Binary amplitude estimation: A polynomial of degree O((γ2 − γ1)^−1 log(δ^−1)) enables interval discrimination when it is bounded by one on [−1, 1].The polynomial can be constructed from an approximate sign function or by the optimization procedure described in Section IV.
  • Binary amplitude estimation: O((γ2 − γ1)^−1 log(ϑ^−1)) applications of W suffice for success probability at least 1 − ϑ using majority voting.Each run uses O(log(ϑ^−1)) repetitions of W and U, while one U implementation requires O((γ2 − γ1)^−1) applications of W.
  • Binary amplitude estimation: The implementation uses one additional QET-U ancilla and another ancilla for the Toffoli-based reflection operator.The stated construction therefore requires additional workspace beyond the system and initial ancilla registers.
  • Ground-state energy estimation: For TFIM and related Hamiltonians, energy estimation uses measurements after basis changes and signed combinations of marginal probabilities.More generally, grouping Hamiltonian components into L classes requires measuring L circuits Vk|ψ0⟩, where each Vk simultaneously diagonalizes one class.
Loading 2204.05955v2…