We introduce an efficient classical algorithm for designing quantum circuits to simulate local manybody quantum dynamics efficiently without requiring commutativity of the the local terms summed to construct the Hamiltonian, a Hamiltonian oracle, or ancillary qubits. Our efficient algorithm with its resultant low-cost quantum circuit will be valuable for near-future quantum-simulation experiments, and we apply our circuit-design algorithm to two examples: Kitaev’s toric-code and honeycomb models.
We introduce an efficient classical algorithm for designing quantum circuits to simulate local manybody quantum dynamics efficiently without requiring commutativity of the the local terms summed to construct the Hamiltonian, a Hamiltonian oracle, or ancillary qubits. Our efficient algorithm with its resultant low-cost quantum circuit will be valuable for near-future quantum-simulation experiments, and we apply our circuit-design algorithm to two examples: Kitaev’s toric-code and honeycomb models.
We construct an efficient autonomous quantum-circuit design algorithm for creating efficient quantum circuits to simulate Hamiltonian many-body quantum dynamics for arbitrary input states. The resultant quantum circuits have optimal space complexity and employ a sequence of gates that is close to optimal with respect to time complexity. We also devise an algorithm that exploits commutativity to optimize the circuits for parallel execution. As examples, we show how our autonomous algorithm constructs circuits for simulating the dynamics of Kitaev's honeycomb model and the Bardeen–Cooper–Schrieffer model of superconductivity. Furthermore, we provide numerical evidence that the rigorously proven upper bounds for the simulation error here and in previous work may sometimes overestimate the error by orders of magnitude compared to the best achievable performance for some physics-inspired simulations.
Simulating the Hamiltonian dynamics of quantum systems is one of the most promising applications of digital quantum computers. In this dissertation, we develop an understanding of quantum simulation algorithms concerning their design, analysis, implementation, and application. We implement three leading simulation algorithms, employing diverse techniques to tighten their error analyses and optimize circuit implementations. We produce concrete resource estimates for simulating a Heisenberg spin system, a problem arising in condensed matter physics that is otherwise difficult to solve on a classical computer. The resulting circuits are orders of magnitude smaller than those for the simplest classically-infeasible instances of factoring and quantum chemistry, suggesting the simulation of spin systems as a promising candidate for an early demonstration of practical quantum computation. We design new simulation algorithms by using classical randomness. We show that by simply randomizing how the terms in the Hamiltonian are ordered, one can prove stronger bounds for product formulas and thereby give more efficient quantum simulations. We also develop a classical sampler for time-dependent Hamiltonians, using which we give a simulation algorithm that substantially improves over previous approaches when the Hamiltonian varies significantly with time. We propose a general theory to analyzing product formulas, an approach to quantum simulation widely used in experimental demonstrations but whose error scaling was poorly understood. Our approach directly exploits the commutativity of Hamiltonian, overcoming the limitations of prior error analyses. We prove new speedups of product formulas for simulating many quantum systems, including simulations of nearest-neighbor lattice systems, second-quantized plane-wave electronic structure, k-local Hamiltonians, rapidly decaying power-law interactions, and clustered Hamiltonians, nearly matching or even outperforming the best previous results in quantum simulation. We accompany our analysis with numerical calculation, which suggests that the bounds also have nearly tight constant prefactors. We identify applications of quantum simulation to designing other quantum algorithms and improving quantum Monte Carlo methods. We develop an algorithmic framework ``quantum singular value transformation'' using techniques from quantum simulation and apply it to implement principal component regression. We also apply our new analysis of product formulas and obtain improved quantum Monte Carlo simulations of the transverse field Ising model and quantum ferromagnets.
One of the main concerns in the era of noisy intermediate-scale quantum (NISQ) computing and fault-tolerant quantum computing is the optimization of circuit implementation for quantum oracles, particularly with limited resources. Synthesizing a satisfiability (SAT) oracle, a crucial component in solving SAT problems, presents a significant challenge. The current state-of-the-art implementation of anm-clause SAT-oracle necessitates2m−1ancillary qubits and a linear number of elementary gates. We develop two efficient and ancilla-adjustable synthesis algorithms to reduce the overall quantum resource usage. Our first quantum oracle algorithm achieves quadratic optimization in the number of ancillary qubits with merely eight times increased circuit size. We also show that using only three ancillary qubits with quadratic circuit size expansion is enough. Our second algorithm optimizes the circuit depth of the SAT oracle toO~(logm)usingmancillary qubits. By running our algorithms on classical intractable SAT instances featured in SAT competitions, the experiment results show that our required quantum resources align well with our theoretical analysis. Our algorithms highlight the scalability of SAT-oracle-based algorithms in near-term quantum devices, such as Grover’s algorithm.
Abstract Determining the ground and excited state properties of materials is considered one of the most promising applications of quantum computers. On near-term hardware, the limiting constraint on such simulations is the requisite circuit depths and qubit numbers, which currently lie well beyond near-term capabilities. Here we develop a quantum algorithm which reduces the estimated cost of material simulations. For example, we obtain a circuit depth improvement by up to 6 orders of magnitude for a Trotter layer of time-dynamics simulation in the transition-metal oxide SrVO3compared with the best previous quantum algorithms. We achieve this by introducing a collection of connected techniques, including highly localised and physically compact representations of materials Hamiltonians in the Wannier basis, a hybrid fermion-to-qubit mapping, and an efficient circuit compiler. Combined together, these methods leverage locality of materials Hamiltonians and result in a design that generates quantum circuits with depth independent of the system’s size. Although the requisite resources for the quantum simulation of materials are still beyond current hardware, our results show that realistic simulation of specific properties may be feasible without necessarily requiring fully scalable, fault-tolerant quantum computers, providing quantum algorithm design incorporates deeper understanding of the target materials and applications.
Simulating large-scale coupled-oscillator systems presents substantial computational challenges for classical algorithms, particularly when pursuing first-principles analyses in the thermodynamic limit. Motivated by the quantum algorithm framework proposed by Babbush et al. (2023), we present and implement a detailed quantum circuit construction for simulating one-dimensional spring–mass systems. Our approach incorporates key quantum subroutines, including block encoding, quantum singular value transformation (QSVT), and amplitude amplification, to realize the unitary time-evolution operator associated with simulating classical oscillators dynamics. In the uniform mass–spring setting, our circuit construction requires a gate complexity ofO(log22Nlog2(1/ε)), where N is the number of oscillators and$\varepsilon isthetargetaccuracyoftheapproximation.Formoregeneral,heterogeneousmass–springsystems,thetotalgatecomplexityis\mathcal {O}\bigl (N\log _{2} N\,\log _{2}(1/\varepsilon )\bigr ).Bothsettingsrequire\mathcal {O}(\log _{2} N)$qubits. Numerical simulations agree with classical solvers across all tested configurations, indicating that this circuit-based Hamiltonian simulation approach can substantially reduce computational costs and potentially enable larger-scale many-body studies on future quantum hardware.
Gibbs state preparation, or Gibbs sampling, is a key computational technique extensively used in physics, statistics, and other scientific fields. Recent efforts for designing fast mixing Gibbs samplers for quantum Hamiltonians have largely focused on commuting local Hamiltonians (CLHs), a non-trivial subclass of Hamiltonians which include highly entangled systems such as the Toric code and quantum double model. Most previous Gibbs samplers relied on simulating the Davies generator, which is a Lindbladian associated with the thermalization process in nature.Instead of using the Davies generator, we design a different Gibbs sampler for various CLHs by giving a reduction to classical Hamiltonians, in the sense that one can efficiently prepare the Gibbs state for some CLH H on a quantum computer as long as one can efficiently do classical Gibbs sampling for the corresponding classical Hamiltonian H ( c ) . We demonstrate that our Gibbs sampler is able to replicate state-of-the-art results as well as prepare the Gibbs state in regimes which were previously unknown, such as the low temperature region, as long as there exists fast mixing Gibbs samplers for the corresponding classical Hamiltonians. Our reductions are as follows.– If H is a 2-local qudit CLH, then H ( c ) is a 2-local qudit classical Hamiltonian.– If H is a 4-local qubit CLH on 2D lattice and there are no classical qubits, then H ( c ) is a 2-local qudit classical Hamiltonian on a planar graph. As an example, our algorithm can prepare the Gibbs state for the (defected) Toric code at any non-zero temperature in O ( n 2 p o l y ( l o g n ) ) time.– If H is a 4-local qubit CLH on 2D lattice and there are classical qubits, assuming that quantum terms are uniformly correctable, then H ( c ) is a constant-local classical Hamiltonian.