skip to main content

This content will become publicly available on November 1, 2022

Title: Optimized Quantum Program Execution Ordering to Mitigate Errors in Simulations of Quantum Systems
Simulating the time evolution of a physical system at quantum mechanical levels of detail - known as Hamiltonian Simulation (HS) - is an important and interesting problem across physics and chemistry. For this task, algorithms that run on quantum computers are known to be exponentially faster than classical algorithms; in fact, this application motivated Feynman to propose the construction of quantum computers. Nonetheless, there are challenges in reaching this performance potential. Prior work has focused on compiling circuits (quantum programs) for HS with the goal of maximizing either accuracy or gate cancellation. Our work proposes a compilation strategy that simultaneously advances both goals. At a high level, we use classical optimizations such as graph coloring and travelling salesperson to order the execution of quantum programs. Specifically, we group together mutually commuting terms in the Hamiltonian (a matrix characterizing the quantum mechanical system) to improve the accuracy of the simulation. We then rearrange the terms within each group to maximize gate cancellation in the final quantum circuit. These optimizations work together to improve HS performance and result in an average 40% reduction in circuit depth. This work advances the frontier of HS which in turn can advance physical and chemical modeling more » in both basic and applied sciences. « less
Authors:
; ; ; ; ; ;
Award ID(s):
1730449 2110860 2016136 1818914
Publication Date:
NSF-PAR ID:
10321372
Journal Name:
2021 International Conference on Rebooting Computing (ICRC)
Sponsoring Org:
National Science Foundation
More Like this
  1. Understanding the computational power of noisy intermediate-scale quantum (NISQ) devices is of both fundamental and practical importance to quantum information science. Here, we address the question of whether error-uncorrected noisy quantum computers can provide computational advantage over classical computers. Specifically, we study noisy random circuit sampling in one dimension (or 1D noisy RCS) as a simple model for exploring the effects of noise on the computational power of a noisy quantum device. In particular, we simulate the real-time dynamics of 1D noisy random quantum circuits via matrix product operators (MPOs) and characterize the computational power of the 1D noisy quantummore »system by using a metric we call MPO entanglement entropy. The latter metric is chosen because it determines the cost of classical MPO simulation. We numerically demonstrate that for the two-qubit gate error rates we considered, there exists a characteristic system size above which adding more qubits does not bring about an exponential growth of the cost of classical MPO simulation of 1D noisy systems. Specifically, we show that above the characteristic system size, there is an optimal circuit depth, independent of the system size, where the MPO entanglement entropy is maximized. Most importantly, the maximum achievable MPO entanglement entropy is bounded by a constant that depends only on the gate error rate, not on the system size. We also provide a heuristic analysis to get the scaling of the maximum achievable MPO entanglement entropy as a function of the gate error rate. The obtained scaling suggests that although the cost of MPO simulation does not increase exponentially in the system size above a certain characteristic system size, it does increase exponentially as the gate error rate decreases, possibly making classical simulation practically not feasible even with state-of-the-art supercomputers.« less
  2. Abstract

    The quantum simulation of quantum chemistry is a promising application of quantum computers. However, forNmolecular orbitals, the$${\mathcal{O}}({N}^{4})$$O(N4)gate complexity of performing Hamiltonian and unitary Coupled Cluster Trotter steps makes simulation based on such primitives challenging. We substantially reduce the gate complexity of such primitives through a two-step low-rank factorization of the Hamiltonian and cluster operator, accompanied by truncation of small terms. Using truncations that incur errors below chemical accuracy allow one to perform Trotter steps of the arbitrary basis electronic structure Hamiltonian with$${\mathcal{O}}({N}^{3})$$O(N3)gate complexity in small simulations, which reduces to$${\mathcal{O}}({N}^{2})$$O(N2)gate complexity in the asymptotic regime; and unitary Coupled Cluster Trottermore »steps with$${\mathcal{O}}({N}^{3})$$O(N3)gate complexity as a function of increasing basis size for a given molecule. In the case of the Hamiltonian Trotter step, these circuits have$${\mathcal{O}}({N}^{2})$$O(N2)depth on a linearly connected array, an improvement over the$${\mathcal{O}}({N}^{3})$$O(N3)scaling assuming no truncation. As a practical example, we show that a chemically accurate Hamiltonian Trotter step for a 50 qubit molecular simulation can be carried out in the molecular orbital basis with as few as 4000 layers of parallel nearest-neighbor two-qubit gates, consisting of fewer than 105non-Clifford rotations. We also apply our algorithm to iron–sulfur clusters relevant for elucidating the mode of action of metalloenzymes.

    « less
  3. We present a quasi-polynomial time classical algorithm that estimates the partition function of quantum many-body systems at temperatures above the thermal phase transition point. It is known that in the worst case, the same problem is NP-hard below this point. Together with our work, this shows that the transition in the phase of a quantum system is also accompanied by a transition in the hardness of approximation. We also show that in a system of n particles above the phase transition point, the correlation between two observables whose distance is at least Ω(logn) decays exponentially. We can improve the factormore »of logn to a constant when the Hamiltonian has commuting terms or is on a 1D chain. The key to our results is a characterization of the phase transition and the critical behavior of the system in terms of the complex zeros of the partition function. Our work extends a seminal work of Dobrushin and Shlosman on the equivalence between the decay of correlations and the analyticity of the free energy in classical spin models. On the algorithmic side, our result extends the scope of a recent approach due to Barvinok for solving classical counting problems to quantum many-body systems.« less
  4. Adiabatic computing with two degrees of freedom of 2-local Hamiltonians has been theoretically shown to be equivalent to the gate model of universal quantum computing. But today’s quantum annealers, namely D-Wave’s 2000Q platform, only provide a 2-local Ising Hamiltonian abstraction with a single degree of freedom. This raises the question what subset of gate programs can be expressed as quadratic unconstrained binary problems (QUBOs) on the D-Wave. The problem is of interest because gate-based quantum platforms are currently limited to 20 qubits while D-Wave provides 2,000 qubits. However, when transforming entire gate circuits into QUBOs, additional qubits will be required.more »The objective of this work is to determine a subset of quantum gates suitable for transformation into single-degree 2-local Ising Hamiltonians under a common qubit base representation such that they comprise a compound circuit suitable for pure quantum computation, i.e., without having to switch between classical and quantum computing for different bases. To this end, this work contributes, for the first time, a fully automated method to translate quantum gate circuits comprised of a subset of common gates expressed as an IBM Qiskit program to single-degree 2-local Ising Hamiltonians, which are subsequently embedded in the D-Wave 2000Q chimera graph. These gate elements are placed in the chimera graph and augmented by constraints that enforce inter-gate logical relationships, resulting in an annealer embedding that completely characterizes the overall gate circuit. Annealer embeddings for several example quantum gate circuits are then evaluated on D-Wave 2000Q hardware.« less
  5. Abstract The proposal of fault-tolerant quantum computations, which promise to dramatically improve the operation of quantum computers and to accelerate the development of the compact hardware for them, is based on topological quantum field theories, which rely on the existence in Nature of physical systems described by a Lagrangian containing a non-Abelian (NA) topological term. These are solid-state systems having two-dimensional electrons, which are coupled to magnetic-flux-quanta vortexes, forming complex particles, known as anyons. Topological quantum computing (TQC) operations thus represent a physical realization of the mathematical operations involving NA representations of a braid group B n , generated bymore »a set of n localized anyons, which can be braided and fused using a “tweezer” and controlled by a detector. For most of the potential TQC material systems known so far, which are 2D-electron–gas semiconductor structure at high magnetic field and a variety of hybrid superconductor/topological-material heterostructures, the realization of anyon localization versus tweezing and detecting meets serious obstacles, chief among which are the necessity of using current control, i.e., mobile particles, of the TQC operations and high density electron puddles (containing thousands of electrons) to generate a single vortex. Here we demonstrate a novel system, in which these obstacles can be overcome, and in which vortexes are generated by a single electron. This is a ~ 150 nm size many electron InP/GaInP 2 self-organized quantum dot, in which molecules, consisting of a few localized anyons, are naturally formed and exist at zero external magnetic field. We used high-spatial-resolution scanning magneto-photoluminescence spectroscopy measurements of a set of the dots having five and six electrons, together with many-body quantum mechanical calculations to demonstrate spontaneous formation of the anyon magneto-electron particles ( e ν ) having fractional charge ν  =  n / k, where n  = 1–4 and k  = 3–15 are the number of electrons and vortexes, respectively, arranged in molecular structures having a built-in (internal) magnetic field of 6–12 T. Using direct imaging of the molecular configurations we observed fusion and braiding of e ν - anyons under photo-excitation and revealed the possibility of using charge sensing for their control. Our investigations show that InP/GaInP 2 anyon-molecule QDs, which have intrinsic transformations of localized e ν - anyons compatible with TQC operations and capable of being probed by charge sensing, are very promising for the realization of TQC.« less