Efficient quantum circuits for arbitrary sparse unitaries

Abstract

Arbitrary exponentially large unitaries cannot be implemented efficiently by quantum circuits. However, we show that quantum circuits can efficiently implement any unitary provided it has at most polynomially many nonzero entries in any row or column, and these entries are efficiently computable. One can formulate a model of computation based on the composition of sparse unitaries which includes the quantum Turing machine model, the quantum circuit model, anyonic models, permutational quantum computation, and discrete time quantum walks as special cases. Thus we obtain a simple unified proof that these models are all contained in BQP. Furthermore our general method for implementing sparse unitaries simplifies several existing quantum algorithms.

4 pages. Substantially expanded since v1

References in corpus (2)

• Quantum algorithm for solving linear systems of equations
• Spatial search and the Dirac equation

Cited by in corpus (18)

• Quantum Circuits for Sparse Isometries
• Variational quantum eigensolvers for sparse Hamiltonians
• Black-box Hamiltonian simulation and unitary implementation
• Quantum Simulation of Nuclear Inelastic Scattering
• Lattice Boltzmann-Carleman quantum algorithm and circuit for fluid flows at moderate Reynolds number
• Efficient quantum circuits for Szegedy quantum walks
• Superdiffusive quantum stochastic walk definable of arbitrary directed graph
• Efficient simulation of sparse Markovian quantum dynamics
• Hamiltonian simulation with nearly optimal dependence on spectral norm
• Efficient quantum circuits for continuous-time quantum walks on composite graphs
• Efficient implementation of discrete-time quantum walks on quantum computers
• Efficient quantum circuits for Toeplitz and Hankel matrices
• Two-qudit topological phase evolution under dephasing
• Code Generator for Quantum Simulated Annealing
• Permutational Quantum Computing
• Compressed Sensing Tomography for qudits in Hilbert spaces of non-power-of-two dimensions
• Quantum Machine Learning For Classical Data
• New perspectives on quantum kernels through the lens of entangled tensor kernels