PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning many-body Hamiltonians with Heisenberg-limited scaling

Hsin-Yuan Huang, Yu Tong, Di Fang, Yuan Su

arXiv:2210.03030v1quant-phcs.ITcs.LGcs.NAmath.ITmath.NA

TL;DR

Many-body interactions make Heisenberg-limit methods for simple Hamiltonians difficult to apply because entanglement growth couples unknown parameters. This paper proposes a SPAM-robust algorithm using single-qubit Clifford experiments, with O(epsilon^-1) evolution-time scaling that saturates the Heisenberg limit at fixed failure probability.

  • Problem

    Many-body interactions make Heisenberg-limit methods for simple Hamiltonians difficult to apply because entanglement growth couples unknown parameters.

    Source: §1 · p. 3

  • Method

    The algorithm learns an unknown low-interaction Hamiltonian using SPAM-robust single-qubit Clifford experiments.

    Source: §2 · p. 5

  • Results

    O(epsilon^-1) evolution-time scaling saturates the Heisenberg limit when failure probability δ is fixed.

    Source: §1 · p. 4

  • Takeaways & Limitations

    A matching lower bound for SPAM-robust learning establishes the algorithm’s asymptotic optimality.

    Source: §1 · p. 5

    The low-interaction model assumes fixed, known Pauli support; for all-to-all two-body interactions, the reshaping approach costs O(N^2 epsilon^-1 log(delta^-1)) evolution time.

    Source: §2 · p. 5, §4 · p. 11

Abstract

from arXiv · show

Learning a many-body Hamiltonian from its dynamics is a fundamental problem in physics. In this work, we propose the first algorithm to achieve the Heisenberg limit for learning an interacting $N$-qubit local Hamiltonian. After a total evolution time of $\mathcal{O}(\epsilon^{-1})$, the proposed algorithm can efficiently estimate any parameter in the $N$-qubit Hamiltonian to $\epsilon$-error with high probability. The proposed algorithm is robust against state preparation and measurement error, does not require eigenstates or thermal states, and only uses $\mathrm{polylog}(\epsilon^{-1})$ experiments. In contrast, the best previous algorithms, such as recent works using gradient-based optimization or polynomial interpolation, require a total evolution time of $\mathcal{O}(\epsilon^{-2})$ and $\mathcal{O}(\epsilon^{-2})$ experiments. Our algorithm uses ideas from quantum simulation to decouple the unknown $N$-qubit Hamiltonian $H$ into noninteracting patches, and learns $H$ using a quantum-enhanced divide-and-conquer approach. We prove a matching lower bound to establish the asymptotic optimality of our algorithm.

1 Introduction

The introduction frames Hamiltonian learning as important to sensing, device engineering, and many-body physics, while asking whether many-body learning can improve on the usual ϵ^-2 scaling. It presents a Heisenberg-limited algorithm and a matching lower bound, alongside practical advantages and scope limits.

1 Introduction

  • Prior many-body learning methods required at least ϵ^-2 scaling, while entanglement growth makes long-time coherent evolution difficult and short-time approaches attain at best the standard quantum limit.Source: §1 · pp. 3–4
  • O(ϵ^-1) total evolution time and O(polylog(ϵ^-1)) experiments suffice to learn parameters of an interacting N-qubit local Hamiltonian to ϵ error with high probability.The guarantee is stated for any parameter, with probability at least 1−δ.Source: Figure 1 · p. 4, §1 · p. 4
  • The algorithm uses quantum-simulation ideas to decouple the unknown Hamiltonian into non-interacting patches with known local eigenvectors, then learns parameters through long-time coherent evolution.Source: Figure 1 · p. 4
  • A matching lower bound for SPAM-robust learning algorithms establishes the proposed algorithm’s asymptotic optimality.The lower bound accounts for failure probability δ.Source: §1 · p. 5
  • The method uses only single-qubit Clifford gates and needs neither eigenstates nor thermal states, but all-to-all interactions add N-dependence and precision depends on Pauli-gate speed.Source: §1 · p. 5

2 Main results

For low-interaction N-qubit Hamiltonians with known support, the paper gives a SPAM-robust single-qubit-Clifford algorithm that estimates all parameters to ε error in total evolution time O(ε^-1 log(N/δ′)). A matching lower bound establishes the time scaling, while the algorithm also uses few experiments and has near-linear-in-N classical postprocessing.

2 Main results

  • The algorithm applies to low-interaction Hamiltonians with Θ(N) unknown coefficients, fixed known support, and O(1) few-body terms acting on each qubit.This class includes geometrically-local Hamiltonians and is also called bounded-degree local Hamiltonians.Source: §2 · p. 5
  • Noisy all-zero state preparation, single-qubit Clifford layers, and noisy computational-basis measurement suffice for the algorithm, which is robust to SPAM error.The paper calls this restricted setup single-qubit Clifford experiments.Source: §2 · p. 5
  • Ω(ε^-1 log(δ^-1)) total evolution time is necessary for any SPAM-robust learning algorithm, matching the proposed algorithm's scaling.The lower bound permits arbitrary adaptive quantum experiments involving the unknown dynamics.Source: §2 · p. 6
  • O(ε^-1 log(N/δ′)) total evolution time suffices to estimate all Hamiltonian parameters to ε error with probability at least 1−δ′.The guarantee follows by setting the individual failure probability to δ′/N and applying a union bound.Source: §2 · p. 6
  • The algorithm requires significantly fewer than Θ(ε^-1) experiments and uses O(N ε^-1.5 polylog(ε^-1) log(δ^-1)) single-qubit Clifford gates.Classical time to generate all estimates from experimental data is O(N polylog(ε^-1) log(δ^-1)).Source: §2 · p. 6

3 Proof ideas

The proof ideas reshape unknown Hamiltonians so individual parameters can be isolated, extend this strategy from single qubits to decoupled few-qubit patches, and establish an approximation analysis and matching evolution-time lower bound.

3.1 Reshaping an unknown Hamiltonian

  • Hamiltonian simulation techniques reshape an unknown Hamiltonian using available unitary dynamics without requiring knowledge of the underlying Hamiltonian, but higher-order Trotter formulas are unsuitable because they require backward evolution.The reshaping approximations become exact as r → ∞.Source: §3.1 · pp. 6–7

3.2 Learning a single-qubit Hamiltonian

  • Averaging conjugated Hamiltonians can remove unwanted Pauli terms, letting robust phase estimation recover a single-qubit parameter with O(ϵ^-1 log(δ^-1)) evolution time and O(polylog(ϵ^-1) log(δ^-1)) experiments.The procedure applies to λx, λy, and λz by changing the reshaping.Source: §3.2 · p. 8

3.3 Learning a few-qubit Hamiltonian

  • Reshaping a few-qubit Hamiltonian leaves one non-identity Pauli operator per qubit, giving access to its eigenstates and enabling parameter estimates from eigenvalue differences and a Hadamard transform.For O(1) qubits, all parameters can be learned with O(ϵ^-1 log(δ^-1)) evolution time and O(polylog(ϵ^-1) log(δ^-1)) experiments.Source: §3.3 · pp. 8–9

3.4 Learning a many-qubit Hamiltonian through divide and conquer

  • Reshaping with selected Pauli unitaries decouples an interacting Hamiltonian into independently evolving two-qubit patches, allowing parameters to be estimated in parallel.The divide-and-conquer approach applies to sums of few-body observables when each qubit participates in at most O(1) observables; parameter estimation uses experiments scaling linearly in N, with parallelization able to do better.Source: §3.4 · pp. 9–10

3.5 Characterizing approximation error in reshaping Hamiltonians

  • For reshaped inhomogeneous Heisenberg models, the approximation error improves from O(N^2t^2/r) to O(t^2/r) by analyzing independent two-qubit patches.The tighter bound removes dependence on system size N for the stated example.Source: §3.5 · p. 10

3.6 Establishing a matching lower bound

  • T = Ω(ϵ^-1 log(δ^-1)) is a lower bound on total evolution time, matching the Heisenberg-limit dependence on ϵ and establishing a bound involving failure probability δ.The argument covers algorithms that adapt experiments to previous outcomes.Source: §3.6 · pp. 10–11

4 Outlook

The outlook establishes Heisenberg-limited learning for many-body local Hamiltonians with many unknown parameters, while leaving extensions to broader Hamiltonian classes open.

4 Outlook

  • All-to-all two-body interactions can be learned with Heisenberg-limited precision at total evolution time O(N^2 epsilon^-1 log(delta^-1)), while achieving O(epsilon^-1 log(delta^-1)) remains open.The outlook also identifies fermionic or bosonic Hamiltonians and arbitrary unstructured N-qubit Hamiltonians as open directions.Source: §4 · p. 11

A.2 Low-intersection Hamiltonians

  • A low-intersection Hamiltonian has terms acting on O(1) qubits, each overlapping O(1) other terms, with the Pauli terms assumed known and M = O(N).Geometrically local Hamiltonians are a special case of the stated class.Source: §A.2 · p. 17
  • Coloring the cluster interaction graph groups disjoint interacting clusters into O(1) color classes, enabling parallel estimation within each class.The graph's degree is bounded independently of N, so its chromatic number is O(1).Source: §A.2 · p. 18

B Reshaping Hamiltonians using randomization

  • The reshaping procedure uses qDRIFT-style randomized Pauli conjugations to construct simpler effective Hamiltonians.The approximation is supported in expectation over sampled Paulis and, in later work, for a single realization with high probability.Source: B Reshaping Hamiltonians using… · p. 18

B.1 Decoupling into noninteracting patches

  • For each color class, reshaping decouples the system into noninteracting few-qubit patches whose cluster observables can be measured in parallel.The Pauli randomization cancels terms that connect clusters to qubits outside the class.Source: B Reshaping Hamiltonians using… · p. 18, §B.1 · p. 19

B.2 Isolating the diagonal Hamiltonian

  • A second reshaping step cancels non-diagonal Pauli terms, leaving only terms diagonal in a selected Pauli eigenbasis for each cluster.The resulting diagonal Hamiltonian has an accessible eigenbasis, unlike the original cluster Hamiltonian.Source: §B.2 · pp. 20–21

B.3 Combining the two reshaping procedures

  • Combining the two reshaping procedures applies decoupling and diagonal-term isolation together through a product of the corresponding Pauli operators.The combined construction draws on the two preceding lemmas.Source: §B.3 · pp. 21–22

C Learning the unknown Hamiltonian after reshaping

  • The learning procedure estimates coefficients of the reshaped Hamiltonians, first for one cluster and then in parallel across clusters of the same color.The section introduces experiment execution, diagonal coefficient estimation, and parallel estimation across clusters.Source: C Learning the unknown Hamiltonian… · p. 22

C.1 Executing quantum experiments

Experiments approximate the reshaped local dynamics using randomized Pauli insertions, then estimate cluster parameters through phase differences in accessible eigenstates.

C.1 Executing quantum experiments

  • Random Pauli insertions approximate evolution under the reshaped Hamiltonian, after which disjoint cluster observables are measured simultaneously to estimate parameters in parallel.The experiment begins with a product state prepared using single-qubit Clifford gates.Source: §C.1 · p. 22

C.2 Estimating the diagonal

  • The total evolution time with H is O(ϵ′−1), while experiments scale as O(polylog(ϵ′−1τ′−1)) = O(poly(|C| + log(ϵ′−1))) ≤ O(poly(k + log(ϵ′−1))) because |C| ≤ k.Source: §C.2 · p. 24
  • The procedure estimates neighboring eigenvalue differences and traverses a shortest-path tree of the cluster hypercube to recover each eigenvalue relative to the global-phase reference.The root eigenvalue is set to zero because global phase is undetectable.Source: §C.2 · pp. 24–25
  • The cluster parameters are recovered from the estimated eigenvalues through a Hadamard transform, with each eigenvalue estimated to precision epsilon.The estimation targets eigenvalue differences because the global phase cannot be observed.Source: §C.2 · pp. 23, 25

C.3 Estimating for all bases and clusters

The algorithm estimates parameters across clusters and bases in parallel, achieving Heisenberg-limited evolution-time scaling for low-interaction Hamiltonians under constant locality and overlap assumptions.

C.3 Estimating for all bases and clusters

  • Clusters sharing a color can be estimated in parallel, giving an overhead of chi = O(d^2) rather than an overhead proportional to the number of clusters.The procedure repeats across clusters and their possible Pauli eigenbases.Source: §C.3 · p. 25
  • O(epsilon^-1 log(delta^-1)) total evolution time and O(polylog(epsilon^-1) log(delta^-1)) experiments suffice when k = O(1) and d = O(1).These costs apply to estimating all parameters to error epsilon with the stated confidence guarantee.Source: §C.3 · pp. 25–26
  • The algorithm is robust against state preparation and measurement error.The paper attributes tolerance to robust phase estimation's ability to handle deviations in the measured probabilities.Source: §C.3 · p. 27
  • The stated cost assumes k = O(1) and d = O(1), and does not account for dependence on either parameter.Here k bounds term support size and d bounds the number of overlapping terms.Source: §C.3 · p. 27

D Deviation from the limiting dynamics in the randomization approach

Random Pauli insertions make the dynamics of a local observable approximate those of a local effective Hamiltonian, with an error bound independent of system size.

D Deviation from the limiting dynamics in the randomization approach

  • The proof bounds the observable's deviation by separating its dynamics into a local component and an environment component, then combining the bounds.The cited argument uses a triangle-inequality combination of the two bounds.Source: D Deviation from the limiting dynamics… · pp. 27, 29
  • The local-observable deviation is O(t^2/r), with the bound independent of system size N and the number of terms M.Here r is the number of random Pauli insertions used during evolution time t.Source: D Deviation from the limiting dynamics… · p. 27
  • With sufficiently frequent random Pauli insertions, a local observable's evolution is determined up to small error by the effective Hamiltonian on its cluster.This is the limiting dynamics targeted by the randomization procedure.Source: D Deviation from the limiting dynamics… · pp. 28–29

D.1 The decoupling error

The decoupling-error proof restricts contributing nested commutators by support overlap, counts the resulting terms, and bounds their higher-order contributions.

D.1 The decoupling error

  • Only nested-commutator terms whose supports successively intersect the preceding supports and C contribute to the bound.The proof defines A_j as the set of index sequences satisfying this overlap condition.Source: §D.1 · p. 30
  • |A_j| is at most j!(d + 1)^j for the contributing index sequences.The proof counts at most d + 1 choices at each step, with a factor accounting for the step index.Source: §D.1 · pp. 30–31
  • The proof treats the j = 0 and j = 1 terms separately before bounding the higher-order remainder.It substitutes the overlap count into the remainder bounds and concludes the lemma.Source: §D.1 · p. 31

D.2 The error in the local dynamics

The proof uses support preservation to analyze local dynamics, then reshapes the Hamiltonian with second-order Trotterization and graph-based decoupling.

D.2 The error in the local dynamics

  • Conjugating each Pauli term by the projection Pauli preserves its support, a fact used in the local-dynamics error proof.The subsection concludes by establishing its error lemma under the assumptions of Theorem 16.Source: §D.2 · p. 32

E Reshaping Hamiltonians using Trotterization

  • Second-order Trotterization reshapes an exponentially large sum of conjugated Hamiltonian terms into a sum with a number of terms independent of N.The section contrasts this construction with the earlier randomization approach.Source: E Reshaping Hamiltonians using… · p. 32

E.1 Decoupling the dynamics using Trotterization

  • The qubit interaction graph can be colored with χq ≤ (d + 1)(k − 2) + 1 colors.The degree bound counts qubits connected through Hamiltonian terms that overlap the selected cluster.Source: §E.1 · p. 33
  • For each color, Pauli conjugations average away terms overlapping the selected qubits while terms disjoint from them form a residual Hamiltonian.The construction implements the resulting sum using the second-order Trotter formula.Source: §E.1 · pp. 33–34

E.2 Isolating the diagonal Hamiltonian using Trotterization

The Trotter-based construction isolates diagonal Hamiltonians and controls the resulting dynamics error. The section also introduces a lower bound on evolution time for Hamiltonian learning.

E.2 Isolating the diagonal Hamiltonian using Trotterization

  • The diagonal Hamiltonian for each cluster is defined in a Pauli eigenbasis, and the construction uses Pauli operators to extract it.The sequence uses R_c = {PQ : P ∈ P_c, Q ∈ Q_c}, with terms of order τ^3 or higher neglected in the approximation.Source: §E.2 · p. 34
  • The number of Pauli operators per short-time step is proportional to |R_c|, which is independent of system size N.Source: §E.2 · p. 34
  • r0 = O(t^3/2/ε^1/2) Trotter repetitions suffice for local observables to approximate the limiting dynamics.The theorem states this bound for observables supported on a cluster and having norm at most 1.Source: §E.2 · p. 35
  • The learning algorithm uses r = O(ε^-3/2) Trotter repetitions, compared with O(ε^-2) for the randomization approach.The text says only a small constant deviation from the limiting dynamics is needed for learning.Source: §E.2 · p. 35

F Deviation from the limiting dynamics in Trotterization

  • The local-operator deviation bound has an O(t^3/r^2) term whose constant is independent of N and the number of Hamiltonian terms M.The stated setting has an effective Hamiltonian supported on a subsystem C of size O(1).Source: F Deviation from the limiting dynamics… · p. 35

G Lower bound for learning Hamiltonian from dynamics

G.1 Model of quantum experiments

A quantum experiment applies an unknown Hamiltonian evolution within a controlled protocol and measures an outcome. The model also describes noisy preparation and measurement and allows adaptive choices across experiments.

G.1 Model of quantum experiments

  • An ideal experiment begins with an arbitrary N′-qubit state, applies a controlled sequence involving the unknown evolution, and returns a POVM outcome.The sequence can use arbitrary evolution times and intervening unitaries.Source: §G.1 · pp. 37–38
  • The experiment's evolution time is defined as the sum of the evolution times used in its sequence.Source: §G.1 · p. 38
  • The model allows adaptive experiment choices and small SPAM errors; the lower bound is proved for measurement noise η = Θ(1).Preparation and measurement deviations are described as bounded by a small constant η.Source: §G.1 · p. 38

G.2 Learning task and lower bound

Theorem 28 lower-bounds the evolution time needed to estimate any unknown Pauli coefficient of an N-qubit Hamiltonian under constant measurement noise. Its scaling matches the proposed learning algorithm.

G.2 Learning task and lower bound

  • The lower-bound scaling matches that of the proposed learning algorithm.Source: §G.2 · p. 39
  • Theorem 28 considers H = Σ_a λ_a E_a with M nonidentity N-qubit Pauli operators and unknown coefficients satisfying |λ_a| ≤ 1.The learning algorithm must estimate any λ_a to ϵ-error with probability at least 1 − δ.Source: §G.2 · p. 39
  • T ≥ log(1/2δ)/(40ϵ) even when measurement noise η = 10^-10.The bound applies to algorithms that estimate a requested parameter to ϵ-error with probability at least 1 − δ.Source: §G.2 · p. 39

G.3 Proof of Theorem 28

The proof reduces Hamiltonian learning to distinguishing two candidate Hamiltonians, bounds how much measurement outcomes can distinguish them, and combines these bounds to establish the evolution-time lower bound. For a single noisy experiment, the outcome distributions’ total variation distance is bounded in terms of its evolution time.

G.3 Proof of Theorem 28

  • The proof has four stages: reduce learning to binary distinguishing, bound single-experiment and adaptive multi-experiment total variation, then apply LeCam’s two-point method.The learning-tree representation is described in.Source: §G.3 · p. 39

G.3.1 Reduction

  • A learner that estimates the Hamiltonian can distinguish with probability at least 1 − δ between H = ϵE1 and H = −ϵE1, so a lower bound for this task applies to learning.E1 is a nonidentity N-qubit Pauli operator.Source: §G.3.1 · p. 39

G.3.2 TV upper bound for a single experiment

  • TV(p+, p−) ≤ (1 − η) min(2ϵt E(η), 1) for the outcome distributions of one experiment using the noisy POVM.The noisy POVM mixes the ideal measurement operators with η-weighted identity terms.Source: §G.3.2 · p. 40

G.3.3 TV upper bound for many experiments

The proof represents adaptive experiments as a rooted tree whose nodes encode observed outcomes and whose leaves encode the algorithm’s available information. It bounds the total variation between the two hypotheses’ outcome distributions and uses that bound with LeCam’s method to establish Theorem 28.

G.3.3 TV upper bound for many experiments

  • A rooted tree represents adaptive experiment choices: each node records prior measurement outcomes, and the experiment at that node may depend on them.The tree covers algorithms that adapt experiments based on previous outcomes.Source: §G.3.3 · p. 41

G.3.4 Lower bound from TV upper bound

  • The multi-experiment lemma bounds total variation between outcome distributions on the tree, while the learner’s final information is its reached leaf.The proof then applies LeCam’s two-point method to derive the evolution-time lower bound and establish Theorem 28.Source: §G.3.3 · p. 41, §G.3.4 · p. 43
Loading 2210.03030v1…