Source-linked AI summary
Improving Quantum Algorithms for Quantum Chemistry
M. B. Hastings, D. Wecker, B. Bauer, M. Troyer
TL;DR
Quantum-chemistry simulation circuits face costly Jordan-Wigner strings, limited parallelism, and Trotter error. The paper introduces string cancellation, ancilla-assisted nesting, and interleaved term ordering, reducing gate-depth scaling and empirically lowering Trotter error.
Problem
Quantum-chemistry simulation is limited by coherent gate counts, while Jordan-Wigner strings and Trotter-Suzuki ordering impose substantial circuit costs.
Method
The paper modifies Jordan-Wigner circuits, uses additional ancillas for parallel nesting, and orders Trotter-Suzuki terms using Hartree-Fock orbital structure.
Results
O(N^9) gate-depth scaling is reduced to O(N^7), while interleaved ordering consistently produces large Trotter-error reductions and can yield two- to three-order-of-magnitude depth reductions for Fe2S2.
Takeaways & Limitations
Combining circuit cancellation, nesting, and term ordering can substantially improve quantum-chemistry simulation depth while trading for a small number of additional ancilla qubits.
Takeaways & Limitations
The approach is most applicable to quantum chemistry, because other models may require a basis transformation that substantially increases the Hamiltonian's term count.
Abstract
from arXiv · showhide
We present several improvements to the standard Trotter-Suzuki based algorithms used in the simulation of quantum chemistry on a quantum computer. First, we modify how Jordan-Wigner transformations are implemented to reduce their cost from linear or logarithmic in the number of orbitals to a constant. Our modification does not require additional ancilla qubits. Then, we demonstrate how many operations can be parallelized, leading to a further linear decrease in the parallel depth of the circuit, at the cost of a small constant factor increase in number of qubits required. Thirdly, we modify the term order in the Trotter-Suzuki decomposition, significantly reducing the error at given Trotter-Suzuki timestep. A final improvement modifies the Hamiltonian to reduce errors introduced by the non-zero Trotter-Suzuki timestep. All of these techniques are validated using numerical simulation and detailed gate counts are given for realistic molecules.
1. CANCELLING JORDAN-WIGNER STRINGS
The paper reduces the cost of implementing Hpqrs terms by moving Jordan-Wigner strings outside repeated basis changes and ordering successive terms to maximize cancellation. An ancilla-assisted circuit further cancels residual strings and supports efficient processing of sparse nonzero terms.
- Subterms: Different Hpqrs subterms use even numbers of σX and σY operators and require distinct basis-change choices.The standard circuit can contain up to eight copies, with Hadamard gates replaced by other basis-change gates for different subterms.
- Alternative circuit: The standard Hpqrs circuit repeats Jordan-Wigner strings across several subterms, while the alternative circuit places the string outside all basis changes.This changes the string from appearing once per subterm to once per term, reducing its overhead by a constant factor.
- Term ordering: Lexicographic ordering causes successive Jordan-Wigner strings to largely cancel when only s changes.All but O(1) CNOTs can cancel between adjacent terms because a CNOT squared is the identity.
- Ancilla-assisted cancellation: An ancilla can track the parity between orbital intervals, allowing a modified ordering that cancels the residual CNOT string created when r increments after s reaches N.The described circuit uses an ancilla initialized to |0⟩ and alternates increasing and decreasing s for each p, q, r choice.
- Sparse Hamiltonians: The ancilla circuit can also exploit cancellations among nonconsecutive nonzero terms, including strings whose CNOT targets are shared by commuting gates.This matters because many molecules do not have every Hpqrs term nonzero.
- Parity reuse: The basic mechanism is reuse of a previously computed parity when the next Jordan-Wigner string differs by only a small set of qubits.For example, incrementing s adds a single qubit to an already computed parity.
2. PARALLELIZATION
Additional ancilla qubits enable nesting and substantially greater parallelization of Hpqrs terms than disjoint-qubit scheduling. This reduces parallel depth by Θ(N) relative to serial execution, yielding a total Θ(N^2) improvement over the original circuit.
- Baseline scheduling: Disjoint-qubit scheduling alone provides only a constant-factor parallelization improvement.Two Hpqrs terms can run simultaneously when their four orbital indices are separated and act on distinct qubits.
- Nesting: Additional ancilla qubits enable nesting, allowing Hpqrs terms whose Jordan-Wigner strings intersect at an even number of sites to execute in parallel.Nested terms can be moved through one another's Jordan-Wigner strings without changing parity.
- Nesting: Θ(N) terms can be executed in parallel with appropriate term ordering, although the optimum ordering was not fully explored.Nesting places one term inside another when their endpoint ordering permits it.
- Depth reduction: Θ(N) parallel-depth improvement over serial gate count produces a total Θ(N^2) improvement compared with the original circuit.The improvement uses additional ancillas while leaving the total gate count unchanged.
3. IMPLEMENTATION ON LIQUi|⟩
The authors used LIQUi|⟩ to evaluate cancellation and nesting in circuits for real molecules, reporting parallel-depth gate counts under an explicit parallel-execution rule. The measured gains are modest for the studied sizes but increase with N.
- Simulation procedure: LIQUi|⟩automatically searched for CNOT and Hadamard cancellations, nestings, and cancellations between CNOTs appearing in different orders.The simulator received sequences of p, q, r, s defining individual Jordan-Wigner steps.
- Results: Figure 10 compares parallel-depth gate counts for real molecules as a function of spin-orbital number.The Hpq and Hpqrs terms were obtained using PyQuante, and many Hpqrs terms vanish because of molecular symmetries.
- Counting convention: Gate-count results use parallel depth, allowing gates on distinct qubits to execute simultaneously, including rotations sharing the phase-estimation control.The same depth could be obtained with a small number of additional ancillas if shared control were disallowed.
- Results: Θ(N) gains from removing Jordan-Wigner strings and parallelization produce modest improvements for the studied molecule sizes but increase with N.The ratios were approximately fit by a + b*N with b << a, suggesting larger relative gains at larger N.
- Circuit optimizations: The HalfUp qubit ordering and optimized PQRS sub-term sequence provide additional constant-factor reductions in gate depth.The optimized sequence permits cancellation of basis-change gates at successive steps.
- Simulation setting: First-order Trotter-Suzuki simulations were used, and similar improvements occur with second-order decomposition.For this setting, the paper states that first-order and second-order decompositions have the same error scaling.
4. TROTTER-SUZUKI TERM ORDERING
The paper proposes an interleaved Trotter-Suzuki term ordering based on Hartree-Fock structure, prioritizing larger and commuting term classes before the numerous Hpqrs terms. It empirically reduces Trotter error, though large-molecule scaling is not theoretically characterized and performance depends on the basis.
- Motivation: Hartree-Fock structure motivates the ordering because effective hopping becomes diagonal in the chosen basis and Hartree-Fock occupancies are often close to 0 or 1.The paper presents this as an approximate basis-dependent rationale for the ordering.
- Interleaved Term Order: The interleaved ordering executes Hpp and Hpqqp terms, then Hpq with Hprrq terms for each p, q, and finally all Hpqrs terms.The Hpqrs terms are ordered separately to minimize parallel depth because they are the most numerous.
- Error reduction: Consistent large reductions in Trotter error were found empirically, largely because Hpq terms are much larger than the others.H2O showed the reduction; improvements were slightly smaller for other molecules, with N2 a notable exception.
- Limitation: The error scaling for large molecules is not yet theoretically understood.The reported reductions are empirical rather than supported by a theory of asymptotic error scaling.
- Scope: The approach generally relies on a basis satisfying Eq. (6), limiting its direct applicability beyond quantum chemistry.For the Hubbard model, a Fourier basis can satisfy the condition but increases the number of Hamiltonian terms.
5. CORRECTED HAMILTONIAN
The paper modifies the Hamiltonian coefficients to compensate for errors caused by finite Trotter-Suzuki timesteps. The correction gives a slight consistent improvement, while avoiding computationally expensive higher-order fermionic terms.
- Correction: The corrected simulation uses a different Hamiltonian whose coefficients approach the original values as δt →0.The coefficients t_pq and V_pqrs are modified for a given timestep.
- Correction: The method separates diagonal and off-diagonal Hamiltonian terms and derives the correction from second-order perturbation theory.An effective diagonal term is defined before calculating the off-diagonal energy shift.
- Results: A slight consistent improvement occurs in all tested cases, although the correction is justified only to second order.Figure 11 labels the corrected results “Diagonal Fix.”
- Scope: The approach is described as a renormalization group corrected Hamiltonian, while adding six-or-more-fermion terms is avoided because they are computationally expensive.
6. DISCUSSION
The discussion reports that circuit cancellations and nesting reduce the gate-depth scaling from N^9 to O(N^7). Assuming interleaved ordering remains effective for larger molecules, combined reductions can reach two to three orders of magnitude for Fe2S2 with 112 spin orbitals.
- Scaling: Jordan-Wigner string cancellation and nesting improve gate-depth scaling from N^9 to O(N^7).
- Scaling: Even with free Clifford operations, nesting reduces rotation time scaling from N^8 to N^7 through additional parallelization.
- Molecular examples: Two to three orders of magnitude of combined gate-depth reduction are obtained for Fe2S2 with 112 spin orbitals, assuming interleaved-ordering gains persist.Larger improvements arise when smaller Trotter error is required.
Appendix A: Error Scaling in First Order Trotter-Suzuki
The appendix explains why first-order Trotter-Suzuki can achieve the same ground-state energy error scaling as second order for the real, non-degenerate-ground-state Hamiltonians used in quantum chemistry. This scaling depends on those conditions and can fail for degenerate ground states or non-real Hamiltonians.
- Trotter formulas: The first-order approximation has per-step error O(δt^2), while the second-order approximation has higher formal accuracy.
- Error scaling: The total evolution is divided into n steps with δt = t/n, yielding expected global error scaling of 1/n for first order and 1/n^2 for second order.
- Error scaling: In practice, both orders show ground-state energy errors proportional to 1/n, with first-order Trotter-Suzuki performing better than expected.
- Scope: The improved scaling assumes a real Hamiltonian and a non-degenerate ground state; a non-zero magnetic field removes the reality condition.
- Explanation: The leading correction has zero ground-state expectation because the ground state is real while the correction is pure imaginary, and the Hermitian expectation must be real.
- Explanation: For a real Hamiltonian with a non-degenerate ground state, the first-order Trotter-Suzuki ground-state energy error is O(δt^2), equivalent to 1/n^2 scaling.The result follows because the ground-state expectation of the leading correction vanishes.
- Scope: A degenerate ground state can restore 1/n error scaling, as shown by a single-qubit example with H = 0.