Hamiltonian Learning and Certification Using Quantum Resources

Nathan Wiebe; Christopher Granade; Christopher Ferrie; D. G. Cory

Source-linked AI summary

Hamiltonian Learning and Certification Using Quantum Resources

Nathan Wiebe, Christopher Granade, Christopher Ferrie, D. G. Cory

arXiv:1309.0876v1Sep 4, 2013quant-ph

TL;DR

The paper addresses how to certify an untrusted quantum simulator when classical likelihood evaluation is intractable. It combines Bayesian inference with trusted quantum simulation through QLE and IQLE, and numerically finds that IQLE retains exponential learning under substantial likelihood-estimation noise, with greater robustness than QLE.

Problem
Classical simulation makes likelihood evaluation difficult for complex Hamiltonians, while QLE can become unstable because distant hypotheses may have similar likelihoods.
Method
The method combines Bayesian inference with sequential Monte Carlo and trusted quantum-simulator likelihood estimates, using IQLE to improve robustness.
Results
IQLE retains quadratic-loss scaling as e^-γN under substantial likelihood-estimation errors, and is more robust than QLE in the 9-qubit noisy comparison.
Takeaways & Limitations
The numerical results support quantum-resource-assisted Hamiltonian learning for the studied Ising models, including under noisy likelihood estimation.

Abstract

from arXiv · show

In recent years quantum simulation has made great strides culminating in experiments that operate in a regime that existing supercomputers cannot easily simulate. Although this raises the possibility that special purpose analog quantum simulators may be able to perform computational tasks that existing computers cannot, it also introduces a major challenge: certifying that the quantum simulator is in fact simulating the correct quantum dynamics. We provide an algorithm that, under relatively weak assumptions, can be used to efficiently infer the Hamiltonian of a large but untrusted quantum simulator using a trusted quantum simulator. We illustrate the power of this approach by showing numerically that it can inexpensively learn the Hamiltonians for large frustrated Ising models, demonstrating that quantum resources can make certifying analog quantum simulators tractable.

1. Error Scaling for Linear Interaction Graph

The algorithm learns Hamiltonians on linear interaction graphs, with information increasing exponentially as more IQLE experiments are performed.

1. Error Scaling for Linear Interaction Graph: IQLE experiments on linear interaction graphs are similarly effective, with quadratic loss following exponential scaling in experiment number.The loss is fit to Ae^-γN, where N is the experiment number.

2. Error Scaling for QLE

QLE can learn Hamiltonians on linear Ising models but is less robust than IQLE because distant hypotheses can produce similar likelihoods and confuse resampling.

2. Error Scaling for QLE: QLE learning is expected to be less stable than IQLE because distant Hamiltonian parameters can yield similar likelihoods and misdirect particle resampling.This can make recovery from an incorrect inference more difficult.
2. Error Scaling for QLE: Repeating the learning algorithm and using majority voting can reduce the impact of instances in which QLE becomes confused.The authors expect more serious problems when likelihood evaluations are inexact.
2. Error Scaling for QLE: Figure 7 compares quadratic loss across QLE experiments for 4, 8, and 12 qubits on a line, with dashed 50% confidence intervals.The simulations used 10 000, 10 000, and 20 000 particles for n = 4, n = 8, and n = 12, respectively.

3. Errors in Likelihood Evaluations

The learning method remains effective under sampling errors in IQLE likelihood estimates, retaining exponential error reduction while IQLE is more robust than QLE.

3. Errors in Likelihood Evaluations: Even with a large constant likelihood-estimation uncertainty P, IQLE continues reducing quadratic loss as e^-γN, although γ is reduced.The simulations model estimation noise by adding zero-mean Gaussian noise and clipping likelihoods to [0, 1].
3. Errors in Likelihood Evaluations: For a 9-qubit Ising model with P = 0.1, IQLE remains more robust to sampling errors than QLE at later times while retaining exponential error scaling.At short times, QLE and IQLE agree because the probability distribution has not yet reached maximum support.
3. Errors in Likelihood Evaluations: IQLE’s inversion concentrates probability over fewer outcomes, producing smaller relative likelihood errors under noisy estimation.This provides part of the explanation for IQLE’s greater robustness than QLE.
3. Errors in Likelihood Evaluations: For P = 0, γ ∝d^-1, whereas for P = 0.4/n, γ ∝d^-3/2, showing that sampling noise changes scaling quantitatively but not qualitatively.The latter setting corresponds to ϵ ≈ 0.4.
3. Errors in Likelihood Evaluations: With approximately 10 000 particles in a region, independent likelihood errors can reduce total density-update error to roughly 1/100 of the fully correlated-error case.The reduction relies on errors being approximately unbiased and distributed across many particles.

Appendix B: Bayesian Inference of Hamiltonians

The paper implements Bayesian Hamiltonian inference with sequential Monte Carlo, representing hypotheses as weighted particles and using resampling to explore parameter space and quantify uncertainty.

Appendix B: Bayesian Inference of Hamiltonians: Sequential Monte Carlo approximates the intractable Bayesian Hamiltonian posterior with a weighted sum of Dirac-delta particles.The particle count controls approximation accuracy.
Appendix B: Bayesian Inference of Hamiltonians: Bayes’ rule updates the probability of each Hamiltonian after measurement outcomes using the likelihood Pr(D|H), prior Pr(H), and posterior Pr(H|D).The normalization term can be obtained implicitly by integrating the unnormalized distribution.
Appendix B: Bayesian Inference of Hamiltonians: Resampling moves particles away from low-weight hypotheses, adds perturbations, and helps explore Hamiltonian parameter space rather than remaining at initial hypotheses.The method uses an effective-sample-size threshold and covariance-dependent perturbations.
Appendix B: Bayesian Inference of Hamiltonians: The posterior mean is an efficient single Hamiltonian estimate, while credible regions summarize uncertainty around the unknown Hamiltonian.After sufficient experiments, the posterior is assumed approximately Gaussian in the chosen parameterization.
Appendix B: Bayesian Inference of Hamiltonians: Region estimation lets the method characterize uncertainty in Hamiltonian estimates, an advantage over approaches where uncertainty characterization is less natural.The authors identify this capability as a practical advantage over tomographic methods.

Appendix C: Solution in tractable cases

The paper combines decision theory, statistical learning, and computational statistics to approximate Hamiltonian learning, while solving the single-parameter case analytically.

Hamiltonian identification is formulated using decision theory and statistical learning tools.Computational-statistics methods approximate the optimal solution for general Hamiltonian learning.
The single-unknown-parameter problem can be solved analytically.These analytic solutions guide the design of the numerical algorithm for the general problem.

1. Statistical decision theory of learning

The learning task is framed as Bayesian decision theory: choose an estimator minimizing expected quadratic loss, with the posterior mean providing the optimal strategy under regularity conditions.

Quadratic loss L(x_hat, x) = ||x_hat − x||^2 quantifies estimation error and generalizes mean squared error to multiple parameters.
Hamiltonian estimation chooses an estimator mapping possible data sets to valid parameters and minimizes expected loss, or Bayes risk.The objective averages loss over the parameter and data distributions for a given experiment.
Under regularity conditions, the unique best strategy is the Bayesian estimator given by the posterior mean.
For quadratic loss, Bayes risk equals the expected trace of the posterior covariance matrix, or the posterior variance for one parameter.

2. Single parameter problem

The single-parameter analysis specifies a simple Hamiltonian-learning experiment, Bayesian update, and optimal estimator, while assuming an approximately Gaussian parameter distribution for asymptotic analysis.

The analysis studies a single-parameter Hamiltonian with initial state |+> and final measurement in the {|+>, |->} basis.An IQLE experiment evolves for time t using inversion Hamiltonian H_minus = H(x_minus), producing the likelihood function.
The asymptotic analysis assumes the parameter distribution is approximately Gaussian and remains so after a subsequent measurement.The risk between measurements approximates the algorithm's Bayes risk.
The posterior update factors into the likelihood Pr(d|x, mu, sigma; x_minus, t) and prior Pr(x|mu, sigma).
The estimator x_hat_opt is an analytic function of the measurement outcome, prior parameters, evolution time, and inversion parameter.Its associated risk is then analyzed as the optimal estimator's performance.

3. Asymptotic risk and the particle guess heuristic

The asymptotic analysis connects posterior-risk reduction to experiment design: risk decreases exponentially, while the particle guess heuristic adapts evolution times and randomizes inversion choices as uncertainty changes.

Asymptotic risk: Posterior variance cannot increase on average, so every experiment is not strictly bad; the risk envelope also supplies a theoretical lower bound.
Asymptotic risk: Risk oscillates rapidly within its envelope, making the optimum a challenging global-optimization problem.Inversion washes out these oscillations, reducing sensitivity to errors in the estimated optimal evolution time.
Particle guess heuristic: The one-dimensional asymptotic conclusions do not directly apply to multidimensional parameter estimation.The multidimensional heuristic avoids explicitly computing and inverting the current covariance matrix.
Particle guess heuristic: The particle guess heuristic selects the inversion Hamiltonian from a sampled parameter particle and uses random particle differences as a proxy for inverse uncertainty.Randomizing the inversion parameter also provides an adaptive warm-up before the distribution becomes approximately Gaussian.

4. Robustness of inversion to sampling error

The analysis models symmetric errors as bit-flips and shows that inversion preserves estimation performance near the optimal evolution time despite such noise. Without inversion, noise can increase Bayes risk, whereas the particle guess heuristic requires no noise-dependent strategy change.

Symmetric errors in a two-outcome model are represented as bit-flips with probability α, modifying the likelihood to α + (1 − 2α) Pr(d|x; x−, t).
Ignoring added noise leaves the posterior, posterior-mean estimator, and variance unchanged under the assumed model, but Bayes risk is evaluated using data from the true model.
With added bit-flip noise, the no-inversion strategy can exhibit increasing risk.
The inversion model is insensitive to noise strength near the optimal evolution time, and the particle guess heuristic performs identically regardless of noise.Thus, the experimenter need not alter the strategy based on whether noise is present.

5. Consistency in multiple dimensions

Simulations of a three-qubit problem extend the two-qubit analysis and retain its qualitative conclusions: inversion smooths Bayes risk while preserving improvement near the optimal evolution time.

Because the multidimensional Bayes-risk integrals appear analytically intractable, the analysis uses simulations of a three-qubit problem.
The three-qubit simulations find that inversion improves estimation by smoothing the Bayes risk and leaving the improvement unchanged near the optimal evolution time.

Appendix D: Conditions for Asymptotic Stability of Bayesian Inference

Appendix D analyzes stability in sequential Monte Carlo Bayesian inference by separating prior and likelihood errors and examining sampling-based likelihood estimates. It derives conditions under which update errors and total simulation costs remain controlled, while noting that the efficiency conditions may be conservative and model-dependent.

The update procedure has two error sources: inaccuracies in the prior and errors in evaluating likelihoods.
Sampling-based likelihood estimates can destabilize Bayesian updates when particle weights become too small or typical outcomes have small prior-averaged likelihood.
Resampling is justified when the effective sample size is too small, with the stated criterion N_ess ≤ |{x_i}|/2.
The estimator is the posterior mean, and stability is expected when relative errors in posterior variance remain small.
With high probability, the total simulation cost to reach loss δ follows the appendix’s derived scaling under its stability conditions.
Efficiency is suggested when γ ∈ Ω(poly(1/n)), max_j ||H_j|| ∈ O(poly(n)), and experiments with high-probability likelihood O(1/poly(n)) are avoided.The authors caution that more complex examples may require local optimization, and that the predicted δ-scaling may be pessimistic.