PaperlayerView exact revision on arXiv

Source-linked AI summary

Preparing ground states of quantum many-body systems on a quantum computer

David Poulin, Pawel Wocjan

arXiv:0809.2705v1quant-ph

TL;DR

Preparing physically relevant states is a central challenge in quantum simulation, and no general initialization method had been available. The paper modifies a quantum search approach to prepare ground states of interacting quantum systems. It reports a runtime equal to the square root of the system’s Hilbert-space dimension, matching the classical-system ground-state preparation time.

  • Problem

    Although a quantum computer can implement quantum-system dynamics, there was no general method to initialize it in a physically relevant state of the simulated system.

    Source: p. 1

  • Method

    The algorithm runs the search backward from a random system state and uses Grover amplification with a filter that reweights eigenstates near a target energy while returning auxiliary qubits to zero.

    Source: p. 2

  • Results

    The algorithm’s time is the square root of the system’s Hilbert-space dimension, the same time required to prepare a classical many-body system’s ground state.

    Source: p. 4

  • Takeaways & Limitations

    The paper presents a method for preparing ground and thermal states of quantum many-body systems on a quantum computer.

    Source: p. 4

    The general QMA algorithm searches the larger witness-and-scratchpad space, though known natural QMA problems with logarithmic-size scratchpads have the same runtime as local Hamiltonians.

    Source: p. 4

Abstract

from arXiv · show

Preparing the ground state of a system of interacting classical particles is an NP-hard problem. Thus, there is in general no better algorithm to solve this problem than exhaustively going through all N configurations of the system to determine the one with lowest energy, requiring a running time proportional to N. A quantum computer, if it could be built, could solve this problem in time sqrt(N). Here, we present a powerful extension of this result to the case of interacting quantum particles, demonstrating that a quantum computer can prepare the ground state of a quantum system as efficiently as it does for classical systems.

APPENDIX A: JORDAN’S RESULT

Jordan’s result gives two projectors a simultaneous block-diagonal form with blocks of size at most two, organizing their eigenvectors into pairs. This structure underlies the appendix’s analysis of projector operations.

APPENDIX A: JORDAN’S RESULT

  • Any two projectors on an N-dimensional Hilbert space can be put in simultaneous block-diagonal form with blocks of size at most 2.For intermediate eigenvalues, the remaining eigenvectors can be grouped into pairs; after enlarging the space by at most a factor of two, the paired eigenvectors form complete orthonormal bases.Source: Appendix A · p. 5
  • The operators QRQ and RQR share the same spectrum, with eigenvalues between 0 and 1, although their eigenvectors generally differ.When an eigenvalue is 1, the bases can be chosen with matching eigenvectors; when it is 0, either Q annihilates its eigenvector or R does.Source: Appendix A · p. 5
  • For eigenvalues strictly between 0 and 1, Jordan’s result pairs the remaining eigenvectors of the two operators.The paired bases can be completed by enlarging the Hilbert space by at most a factor of two.Source: Appendix A · p. 5

APPENDIX B: FAILURE OF THE NAIVE ALGORITHM

The appendix analyzes why phase-estimation marking followed by Grover amplification can fail: imperfect energy classification lets amplification move the state outside the auxiliary-zero subspace. The resulting overlap with that subspace can be arbitrarily small.

APPENDIX B: FAILURE OF THE NAIVE ALGORITHM

  • The appendix assumes that phase estimation implements U exactly, setting aside imperfect simulation of the unitary evolution.The text says this simulation error can be ignored because it does not build up during Grover’s algorithm.Source: Appendix B · p. 5
  • Even eigenstates above the threshold E can be mistakenly classified below E because phase estimation has a small error probability.The error is more pronounced near E and is zero only when the energy has an exact k-bit binary representation.Source: Appendix B · p. 5
  • Amplifying the phase-estimation projector R can move the resulting state outside the image of Q, the projector onto all-zero auxiliary qubits.The naive procedure starts with a random superposition whose auxiliary qubits are zero and amplifies the phase-estimation outcome marking energies below E.Source: Appendix B · p. 5
  • The overlap with Q can be arbitrarily small when most eigenstates have p_a near 1/N and only a negligible fraction have p_a of order unity.Under that distribution, the overlap is of order 1/N.Source: Appendix B · p. 5

APPENDIX C: DETAILED ANALYSIS FOR THE GROUND STATE PROBLEM

The ground-state analysis bounds the filter overlap as a function of energy distance, then shows that amplification can produce a state near the target energy with high probability. Sweeping candidate energies to polynomial accuracy takes polynomial time.

APPENDIX C: DETAILED ANALYSIS FOR THE GROUND STATE PROBLEM

  • The bounds on |⟨ϕ|μ⟩| make the filter retain nearby energies while controlling contributions from energies separated from μ.The proof uses a lower bound for energies within the filter width and upper bounds for energies at least ε/2 away.Source: Appendix C · pp. 5–6
  • When amplification does not abort, the resulting state has energy μ ± ε with high probability.The proof separates the probability of aborting from the energy of the state when the procedure succeeds.Source: Appendix C · p. 6
  • If an eigenvalue lies within μ ± 2^-k/(2π√η), the overlap used by amplification is at least |α_0|^2/2.For a random initial state, the text says |α_0| exceeds 1/(2√N) with exponentially high probability, sufficient for amplification success.Source: Appendix C · p. 6
  • With k growing polynomially in log(n) and η polynomially in n, the energy error decreases as 1/poly(n), and candidate μ values can be swept to polynomial accuracy in polynomial time.The energy-error scaling is stated separately from the polynomial-time sweep over μ.Source: Appendix C · p. 6

APPENDIX D: DETAILED ANALYSIS FOR PROBLEMS IN QMA

For QMA verification, the appendix uses Jordan’s projector framework on the scratchpad-zero subspace and the accepting subspace. Alternating measurements encode verification outcomes, and the resulting filter is amplified to find accepting witnesses.

APPENDIX D: DETAILED ANALYSIS FOR PROBLEMS IN QMA

  • The circuit uses k alternating measurements of R and Q, coherently recording their outcomes on k auxiliary qubits initialized to zero.Its behavior on an eigenstate of QRQ is analyzed using Jordan’s result.Source: Appendix D · pp. 6–7
  • For a verification circuit V_x, R projects onto its accepting subspace, while Q projects onto the all-zero scratchpad state.The eigenstates of QRQ in the image of Q correspond to witnesses with zero scratchpads and accepting probability p_a.Source: Appendix D · p. 7
  • The analysis initializes the first m qubits in a random state supported on R and prepares the k auxiliary qubits in |μ⟩.The initial state is prepared by setting the first qubit to |1⟩, the remaining qubits to a random stabilizer state, and applying a unitary transformation.Source: Appendix D · p. 7
  • After applying the inverse circuit, the filter excludes terms outside the image of Q ⊗ |0^k⟩⟨0^k|, which Grover amplification then targets.The appendix says the remaining analysis proceeds as for the ground-state algorithm.Source: Appendix D · p. 7
Loading 0809.2705v1…