PaperlayerView exact revision on arXiv

Source-linked AI summary

Hamiltonian Simulation with Optimal Sample Complexity

Shelby Kimmel, Cedric Yen-Yu Lin, Guang Hao Low, Maris Ozols, Theodore J. Yoder

arXiv:1608.00281v1quant-ph

TL;DR

The paper asks how many copies of a quantum state are needed to simulate evolution under the Hamiltonian it encodes. It analyzes the LMR method and establishes its asymptotic optimality, while extending the approach to multiple states and applications.

  • Problem

    The paper asks for the minimum number of copies of an unknown state ρ needed to simulate its encoded Hamiltonian evolution.

    Source: §1 · pp. 1–2

  • Method

    The paper analyzes the LMR sample-based simulation procedure and extends it to Hamiltonians built from multiple input states.

    Source: §1 · pp. 2–3

  • Results

    The LMR protocol is asymptotically optimal in t and δ, with sample complexity Θ(t^2/δ) under the theorem’s stated conditions.

    Source: §1 · p. 3, §3 · p. 7

  • Takeaways & Limitations

    Sample-based Hamiltonian simulation also supports a universal quantum-computation model using partial swaps and simple single-qubit states.

    Source: §1 · p. 3

    The universal model has a polynomial blow-up in the number of operations and cannot provide a speed-up for problems such as Grover’s search.

    Source: §7 · p. 21

Abstract

from arXiv · show

We investigate the sample complexity of Hamiltonian simulation: how many copies of an unknown quantum state are required to simulate a Hamiltonian encoded by the density matrix of that state? We show that the procedure proposed by Lloyd, Mohseni, and Rebentrost [Nat. Phys., 10(9):631--633, 2014] is optimal for this task. We further extend their method to the case of multiple input states, showing how to simulate any Hermitian polynomial of the states provided. As applications, we derive optimal algorithms for commutator simulation and orthogonality testing, and we give a protocol for creating a coherent superposition of pure states, when given sample access to those states. We also show that this sample-based Hamiltonian simulation can be used as the basis of a universal model of quantum computation that requires only partial swap operations and simple single-qubit states.

1 Introduction

The paper studies how many copies of a quantum state encoding a Hamiltonian are needed to simulate its evolution, extending Hamiltonian simulation beyond classical or black-box descriptions. It establishes optimality for the LMR approach and outlines extensions to multiple states and applications.

1 Introduction

  • The authors place sample-based Hamiltonian simulation alongside classical-description and black-box approaches to Hamiltonian simulation.Prior work includes Lloyd’s simulation results and optimal sparse-Hamiltonian algorithms [LC16].Source: §1 · p. 1
  • The problem encodes a Hamiltonian in a density matrix ρ and supplies copies of ρ rather than a classical or black-box description of the Hamiltonian.The encoding assumes a shift H + c1 that is positive semidefinite, making ρ a valid density matrix.Source: §1 · pp. 1–2
  • The LMR protocol uses partial swaps to approximate e^-iρt, independently of the input state σ and the encoded state ρ.Its sample requirement is independent of the states’ dimension, and the protocol was introduced in [LMR14].Source: §1 · p. 2
  • The central question is how many copies of an unknown state ρ are needed to implement e^-iρt on an unknown state σ within trace-distance error δ.The paper calls this quantity the sample complexity of Hamiltonian simulation.Source: §1 · p. 2
  • The paper shows that LMR is asymptotically optimal in t and δ and outperforms tomographic strategies for sample-based simulation.It also extends simulation to Hermitian polynomials of multiple states and applies commutator simulation to orthogonality testing and quantum state addition.Source: §1 · p. 3

2 LMR Protocol versus State Tomography

The section compares LMR simulation with state tomography and explains why estimating ρ first is less sample-efficient. LMR implements the evolution directly with O(t^2/δ) copies, without dependence on state dimension or rank.

2 LMR Protocol versus State Tomography

  • O(t^2/δ) copies of ρ suffice for implementing e^-iρt to error δ in diamond norm.The LMR protocol’s requirement does not depend on the dimension of the states.Source: §2 · p. 4
  • The LMR construction approximates short-time evolution with partial swaps and repeats the step O(t^2/δ) times.The resulting trace-norm error is O(δ), and extending the argument yields the diamond-norm result.Source: §2 · p. 4
  • The protocol can be implemented using O(log D · t^2/δ) single-qubit and Fredkin gates.The partial swap is implemented through a linear combination of the identity and swap operations.Source: §2 · p. 4
  • Tomography must estimate ρ to trace-norm error O(δ/t) to simulate the evolution with error δ.The simulation error from using an estimate bρ instead of ρ is bounded by ϵt when ∥bρ − ρ∥1 = ϵ.Source: §2 · p. 5
  • For fixed dimension and rank, LMR gives a square-root improvement in sample complexity over tomography as a function of δ.LMR also avoids tomography’s dependence on dimension and rank.Source: §2 · p. 6

3 LMR Protocol is Optimal

The section proves that LMR’s sample complexity cannot be improved asymptotically by reducing simulation to state discrimination. Under stated bounds on δ and δ/t, the required number of copies is Θ(t^2/δ).

3 LMR Protocol is Optimal

  • The lower-bound strategy converts a hypothetical more sample-efficient simulator into a procedure for distinguishing two states, contradicting a state-discrimination lower bound.The construction uses states ρ(x) and ρ(x + ϵ), whose sample discrimination requires order 1/ϵ^2 copies under the stated conditions.Source: §3 · p. 6
  • For commuting rank-2 states ρ(x) and ρ(x + ϵ), fewer than Cη/ϵ^2 copies keep the total variation distance between their measurement distributions below 1/3.The states’ eigenvalue distributions correspond to binomial distributions with n trials and probabilities x and x + ϵ.Source: §3 · p. 7
  • f(t, δ) = Θ(t^2/δ) copies are necessary and sufficient when δ ≤ 1/6 and δ/t ≤ 1/(6π).The upper bound follows from the LMR protocol; the section proves the matching lower bound.Source: §3 · p. 7

4 Pure State Discrimination and the Optimality of LMR for Pure States

The section establishes that LMR remains optimal for pure-state Hamiltonian simulation in the error parameter, using a reduction through sample-based Grover search. It also explains why pure-state periodicity prevents a meaningful asymptotic lower bound in time.

4 Pure State Discrimination and the Optimality of LMR for Pure States

  • The pure-state question has practical relevance because LMR and certain pure states as resources create a universal model of quantum computation.The paper points to Section 7 for this application.Source: §4 · p. 8
  • For pure states, periodicity 2π lets simulation use an equivalent time in [0, 2π), so a meaningful asymptotic lower bound on time dependence is unavailable.The authors therefore establish optimality in the error parameter, not the time parameter.Source: §4 · p. 8

4.2 The LMR Protocol is Optimal for Pure States

  • The optimality proof reduces pure-state discrimination to sample-based Grover search and uses state-discrimination bounds to obtain a lower bound.LMR implements sample-based Grover search, connecting that lower bound to its copy complexity.Source: §4 · p. 8, §4.2 · p. 9

4.1 Metrological View of Grover’s Search

  • Sample-based Grover search replaces a circuit description of V with copies of |s⟩, while orthogonality testing replaces both V and U_T with copies of |s⟩ and |t⟩.Both sample-based tasks require Θ(log(1/ϵ)/w) copies.Source: §4.1 · p. 9

4.2 The LMR Protocol is Optimal for Pure States

  • Θ(log(1/ϵ)/w) copies of |s⟩ are necessary and sufficient for sample-based Grover search.The task distinguishes zero target overlap from overlap at least w.Source: §4.2 · p. 9, §4.1 · p. 9
  • For pure ρ, any algorithm needs Ω(1/δ) copies to simulate e^-iρt to trace norm δ, matching LMR’s precision scaling.The lower bound follows by using LMR to implement sample-based Grover search.Source: §4 · p. 8, §4.2 · p. 10

5 Generalized LMR for Simulation of Hermitian Polynomials

This section extends sample-based simulation to Hermitian polynomials in multiple unknown input states. It gives an O(Lc²t²/δ) sample bound for these polynomials and treats linear combinations, commutators, and anticommutators as special cases.

5 Generalized LMR for Simulation of Hermitian Polynomials

  • A flagged state ρ′=|0⟩⟨0|⊗ρ+ + |1⟩⟨1|⊗ρ− lets Lemma 8 simulate the difference ρ+−ρ− using O(t²/δ) samples.Source: §5 · p. 11

5.1 Simulating Linear Combinations

  • For linear combinations, O(c²t²/δ) samples suffice, and some inputs require Ω(c²t²/δ), making the scaling tight.Source: §5.1 · p. 12

5.2 Simulating the Commutator and Anticommutator

  • Commutator and anticommutator simulation use O(t²/δ) samples and have optimal scaling; the commutator lower bound requires Ω(t²/δ) copies of each state.Sequentially applying Theorem 1 to the product expansion instead gives O(t) error and fails even at lowest order.Source: §5.2 · pp. 13–14

5.3 Simulating Hermitian Polynomials in the Input States

  • Any Hermitian polynomial in multiple input states can be simulated using O(Lc²t²/δ) samples, where L is its maximum degree and c is the sum of absolute coefficients.Source: §5.3 · p. 15

6 Applications of Commutator Simulation

The section applies commutator simulation to coherent state addition and orthogonality testing. The addition protocol has overlap-dependent sample cost and boundary cases, while orthogonality testing achieves a tight copy complexity.

6.1 Coherent state addition

  • Given the angle ∆ between two unknown pure states, the protocol prepares a phase-adjusted linear combination, with sample complexity O(χ^2/(δ sin^2 2∆)) for each state.Choosing χ = ∆/2 allows a state proportional to |ψ1⟩ + |ψ2⟩, ignoring the relative phase; the angle must be determined, which can be done by phase estimation on the commutator.Source: §6.1 · pp. 17–18
  • The addition protocol uses commutator simulation to rotate within the two-state subspace, producing real coefficients; complex coefficients require a more sophisticated Hamiltonian.The target is sensitive to relative input phases, so the theorem specifies a phase-adjusted state that is unique up to global phase.Source: §6.1 · p. 17
  • Very small or very large state overlap makes the addition protocol sample-intensive; for orthogonal states the commutator vanishes, while identical states make the task trivial.The theorem excludes ∆ = 0 and π/2.Source: §6.1 · p. 17

6.2 Orthogonality Testing

  • Θ(log(1/ϵ)/w) copies of each state suffice and are necessary to distinguish orthogonal states from states with overlap at least w, with success probability 1 − ϵ.The protocol uses commutator simulation and phase estimation; the lower bound follows by reduction from sample-based Grover search.Source: §6.2 · pp. 18–19

7 Universality of LMR

The paper constructs a universal computation model using Heisenberg interactions and single-qubit |0⟩ and |+⟩ resource states, without encoded qubits. The construction has polynomial, specifically squared, operation overhead and uses O(N(M + M′)^2) operations under the stated connectivity model.

7 Universality of LMR

  • The Heisenberg exchange is the natural coupling in several solid-state implementations and, up to scaling, is the swap interaction used by LMR.Heisenberg interaction alone is not universal for spin-1/2 systems.Source: §7 · p. 19
  • The model is universal without encoded qubits, using n + 1 physical qubits for computations on n qubits and requiring Heisenberg interactions plus single-qubit |0⟩ and |+⟩ preparation.The exchange interaction supplies an entangling gate; arbitrary single-qubit gates complete the universal gate set.Source: §7 · pp. 19–20
  • O(N(M + M′)^2) operations suffice for M single-qubit gates and M′ CNOT gates on the stated connectivity graph.The construction uses O((M + M′)^2) resource states |0⟩ and |+⟩; moving qubits into proximity costs O(N) swaps per gate.Source: §7 · pp. 19–20, Figure 3 · p. 20
  • The model incurs a polynomial, specifically squared, blow-up in operation count, yet remains universal; it cannot provide speedups for problems such as Grover’s search.The paper presents the model as potentially useful where Heisenberg exchange is a natural operation.Source: §7 · p. 21

8 Outlook

The paper concludes that LMR and its generalizations are optimal for several tasks, including unknown-Hamiltonian simulation, pure-state discrimination, and commutator evolution. It leaves open optimality for multinomial evolution, ancilla requirements in the general protocol, and connections to distributed protocols.

8 Outlook

  • The LMR protocol is optimal for simulating Hamiltonians encoded as quantum states, and its generalizations are optimal for pure-state discrimination and commutator evolution.The paper also raises possible connections to distributed protocols, but leaves them for future investigation.Source: §8 · p. 21
  • The authors have not established whether their protocol is optimal for simulating evolutions by the multinomials in Eq. (42).They leave open whether it is optimal or whether better algorithms exist.Source: §8 · p. 21
  • Ancillas seem essential to the general simulation protocol, unlike the original LMR protocol, which uses partial swaps without ancillas.The authors ask whether continuous permutations could implement the general protocol without ancillas.Source: §8 · p. 21
  • The LMR protocol encodes e−iρt into copies of ρ, potentially letting a user perform the operation without learning what ρ is through tomography.The paper frames this as a possible form of quantum copy-protection and notes prior progress and negative results for circuit encodings.Source: §8 · p. 21

A Proof of Hadamard Lemma

The proof relates conjugation of an operator by exponentials to nested commutators. It obtains the relation by comparing the Taylor expansion with the conjugated operator.

A Proof of Hadamard Lemma

  • The lemma defines ad_A(B) as the commutator [A, B].It uses this adjoint representation to express derivatives through nested commutators.Source: A Proof of Hadamard Lemma · p. 26
  • Repeated differentiation gives the n-th derivative of f(t) as a nested-commutator expression, with [A, B]_0 = B.The iterated commutator is defined recursively by [A, B]_n = [A, [A, B]_{n−1}].Source: A Proof of Hadamard Lemma · p. 26
  • Expanding f(t) in a Taylor series at zero and equating its value at 1 with f(t) = e^{tA}Be^{−tA} yields the lemma.The proof equates the two expressions for f(1).Source: A Proof of Hadamard Lemma · p. 26

B Proof of the LMR Upper Bound

The appendix proves that LMR uses O(t^2/δ) copies of ρ to implement e−iρt within error δ in diamond norm. Its construction applies a partial swap with each copy and bounds the accumulated approximation error.

B Proof of the LMR Upper Bound

  • O(t^2/δ) copies of ρ suffice to implement e−iρt with error δ in diamond norm.This is the stated upper bound for Hamiltonian ρ evolved for time t.Source: B Proof of the LMR Upper Bound · pp. 26–27
  • LMR applies the swap Hamiltonian between the input system and each copy of ρ for a small time, then discards that copy.The swap Hamiltonian generates the partial-swap unitary used in each iteration.Source: B Proof of the LMR Upper Bound · p. 26
  • The first iteration approximates the desired evolved state, and the proof bounds the trace-distance gap from the ideal state.The recursive analysis chooses ε = t/n and compares the resulting state with the target evolution at time t.Source: B Proof of the LMR Upper Bound · p. 27

C Controlled Density Matrix Exponentiation

The appendix shows how to implement controlled density-matrix exponentiation with the LMR protocol, despite the concern that discarding registers could destroy control coherence. The construction uses O(t^2/δ) copies, and the embedding trick extends to controlled evolution by Hermitian polynomials.

C Controlled Density Matrix Exponentiation

  • O(t^2/δ) copies of ρ implement controlled-e−iρt with error δ in diamond norm.The result addresses whether discarding registers in LMR would lose coherence between control components.Source: C Controlled Density Matrix… · p. 27
  • Appending a |1⟩⟨1| control state to ρ lets the LMR protocol implement the controlled evolution.The proof uses |1⟩⟨1| ⊗ ρ as the input state to LMR.Source: C Controlled Density Matrix… · p. 28
  • A controlled partial swap preserves the control structure up to O(Δ^2) error per step, yielding total error O(δ) after O(t^2/δ) repetitions.The procedure sets Δ = δ/t and traces out the register holding ρ after each step.Source: C Controlled Density Matrix… · p. 28
  • The appended-control-state trick also applies to controlled evolution generated by any Hermitian polynomial of the input states.Embedding each ρ_k as |1⟩⟨1| ⊗ ρ_k carries the polynomial through the control-state factor.Source: C Controlled Density Matrix… · p. 28

D Better Phase Estimation

Kitaev’s phase estimation on e−iρ requires O(1/ϵ2) samples, a polynomial improvement over the O(1/ϵ3) claimed in [LMR14]. The paper also notes that principal component analysis can be performed with fewer samples than [LMR14] claims.

D Better Phase Estimation

E Equivalence of Hermitian polynomials and the Jordan-Lie algebra

Hermitian multinomials in density matrices are equivalent to elements of the Jordan-Lie algebra generated by those states. The section sketches how nested commutators and anticommutators represent monomials and their Hermitian combinations.

E Equivalence of Hermitian polynomials and the Jordan-Lie algebra

Related papers

Loading 1608.00281v1…