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.
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.
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.
The quantum circuit model is the de-facto way of designing quantum algorithms. Yet any level of abstraction away from the underlying hardware incurs overhead. In this work, we develop quantum algorithms for Hamiltonian simulation "one level below" the circuit model, exploiting the underlying control over qubit interactions available in most quantum hardware and deriving analytic circuit identities for synthesising multi-qubit evolutions from two-qubit interactions. We then analyse the impact of these techniques under the standard error model where errors occur per gate, and an error model with a constant error rate per unit time. To quantify the benefits of this approach, we apply it to time-dynamics simulation of the 2D spin Fermi-Hubbard model. Combined with new error bounds for Trotter product formulas tailored to the non-asymptotic regime and an analysis of error propagation, we find that e.g. for a 5 × 5 Fermi-Hubbard lattice we reduce the circuit depth from 1, 243, 586 using the best previous fermion encoding and error bounds in the literature, to 3, 209 in the per-gate error model, or the circuit-depth-equivalent to 259 in the per-time error model. This brings Hamiltonian simulation, previously beyond reach of current hardware for non-trivial examples, significantly closer to being feasible in the NISQ era.
Many-body systems arising in condensed matter physics and quantum optics inevitably couple to the environment and need to be modelled as open quantum systems. While near-optimal algorithms have been developed for simulating many-body quantum dynamics, algorithms for their open system counterparts remain less well investigated. We address the problem of simulating geometrically local many-body open quantum systems interacting with a stationary Gaussian environment. Under a smoothness assumption on the system-environment interaction, we develop near-optimal algorithms that, for a model with N spins and evolution time t, attain a simulation error δ in the system-state with O(Nt(Nt/δ)o(1)) gates, O(t(Nt/δ)o(1)) parallelized circuit depth and O~(N(Nt/δ)o(1)) ancillas. We additionally show that, if only simulating local observables is of interest, then the circuit depth of the digital algorithm can be chosen to be independent of the system size N. This provides theoretical evidence for the utility of these algorithms for simulating physically relevant models, where typically local observables are of interest, on pre-fault tolerant devices. Finally, for the limiting case of Markovian dynamics with commuting jump operators, we propose two algorithms based on sampling a Wiener process and on a locally dilated Hamiltonian construction, respectively. These algorithms reduce the asymptotic gate complexity on N compared to currently available algorithms in terms of the required number of geometrically local gates.
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.
Quantum circuit synthesis is one of the major areas of current research in the field of quantum computing.Analogous to its Boolean counterpart, the task involves constructing arbitrary quantum gates using only those available within a small set of universal gates that can be realized physically.However, unlike the latter, there are an infinite number of single qubit quantum gates, all of which constitute the special unitary group SU(2).Realizing any given single qubit gate using a given universal gate family is a complex task.Although gates can be synthesized to arbitrary degree of precision as long as the set of finite strings of the gate family is a dense subset of SU(2), it is desirable to accomplish the highest level of precision using only the minimum number of universal gates within the string approximation.Almost all algorithms that have been proposed for this purpose are based on the Solovay-Kitaev algorithm.The crux of the Solovay-Kitaev algorithm is the use of a procedure to decompose a given quantum gate into a pair of group commutators with the pair being synthesized separately.The Solovay-Kitaev algorithm involves group commutator decomposition in a recursive manner, with a direct approximation of a gate into a string of universal gates being performed only at the last level, i.e. in the leaf nodes of the search tree representing the execution of the Solovay-Kitaev algorithm.The main contribution of this research is in integrating conventional optimization procedures within the Solovay-Kitaev algorithm.Two specific directions of research have been studied.Firstly, optimization is incorporated within the group commutator decomposition, so that a more optimal pair of group commutators are obtained.As the degree of precision of the synthesized gate is explicitly minimized by means of this optimization procedure, the enhanced algorithm allows for more accurate quantum gates to be synthesized than what the original Solovay-Kitaev algorithm achieves.Simulation results with random gates indicate that the obtained accuracy is an order of magnitude better than before.Two versions of the new algorithm are examined, with the optimization in the first version being invoked only at the bottom level of Solovay-Kitaev algorithm and when carried out across all levels of the search tree in the next.Extensive simulations show that the second version yields better results despite equivalent computation times.Theoretical analysis of the proposed algorithm is able to provide a more formal, quantitative explanation underlying the experimentally observed phenomena.The other direction of investigation of this research involves formulating the group commutator decomposition in the form of bi-criteria optimization.This phase of research relaxed the equality constraint in the previous approach and with relaxation, a bi-criteria optimization is proposed.This optimization algorithm is new and has been devised primarily when the objective needs to be relaxed in different stages.This bi-criteria approach is able to provide comparably accurate synthesis as the previous approach.
Quantum computing holds immense promise for solving complex problems intractable for classical computers. However, the inherent complexity of quantum circuits necessitates sophisticated optimization techniques. This paper introduces a novel dynamic adaptive quantum circuit optimization algorithm, designed to automatically adjust quantum gate parameters based on the circuit's dynamic state. The algorithm leverages a feedback loop that continuously monitors the circuit's evolution, dynamically re-optimizing gate parameters to minimize error rates and maximize performance. We present a detailed theoretical analysis and demonstrate its effectiveness through a series of rigorous simulations and experiments. The core mechanism focuses on a closed-loop optimization process that adapts to the circuit's inherent variability. The results indicate a significant improvement in quantum circuit performance compared to existing static optimization methods. We conclude by discussing potential applications and future research directions.