This content will become publicly available on November 1, 2022
 Publication Date:
 NSFPAR ID:
 10321372
 Journal Name:
 2021 International Conference on Rebooting Computing (ICRC)
 Sponsoring Org:
 National Science Foundation
More Like this

Understanding the computational power of noisy intermediatescale quantum (NISQ) devices is of both fundamental and practical importance to quantum information science. Here, we address the question of whether erroruncorrected 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 realtime dynamics of 1D noisy random quantum circuits via matrix product operators (MPOs) and characterize the computational power of the 1D noisy quantummore »

Abstract The quantum simulation of quantum chemistry is a promising application of quantum computers. However, for
N molecular orbitals, the 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 twostep lowrank 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}^{4})$$ $O\left({N}^{4}\right)$ gate complexity in small simulations, which reduces to$${\mathcal{O}}({N}^{3})$$ $O\left({N}^{3}\right)$ gate complexity in the asymptotic regime; and unitary Coupled Cluster Trottermore »$${\mathcal{O}}({N}^{2})$$ $O\left({N}^{2}\right)$ 
We present a quasipolynomial time classical algorithm that estimates the partition function of quantum manybody systems at temperatures above the thermal phase transition point. It is known that in the worst case, the same problem is NPhard 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 »

Adiabatic computing with two degrees of freedom of 2local Hamiltonians has been theoretically shown to be equivalent to the gate model of universal quantum computing. But today’s quantum annealers, namely DWave’s 2000Q platform, only provide a 2local 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 DWave. The problem is of interest because gatebased quantum platforms are currently limited to 20 qubits while DWave provides 2,000 qubits. However, when transforming entire gate circuits into QUBOs, additional qubits will be required.more »

Abstract The proposal of faulttolerant 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 nonAbelian (NA) topological term. These are solidstate systems having twodimensional electrons, which are coupled to magneticfluxquanta 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 »