Approximation by Quantum Circuits
read the original abstract
In a recent preprint by Deutsch et al. [1995] the authors suggest the possibility of polynomial approximability of arbitrary unitary operations on $n$ qubits by 2-qubit unitary operations. We address that comment by proving strong lower bounds on the approximation capabilities of g-qubit unitary operations for fixed g. We consider approximation of unitary operations on subspaces as well as approximation of states and of density matrices by quantum circuits in several natural metrics. The ability of quantum circuits to probabilistically solve decision problem and guess checkable functions is discussed. We also address exact unitary representation by reducing the upper bound by a factor of n^2 and by formalizing the argument given by Barenco et al. [1995] for the lower bound. The overall conclusion is that almost all problems are hard to solve with quantum circuits.
This paper has not been read by Pith yet.
Forward citations
Cited by 5 Pith papers
-
Arts & crafts: Strong random unitaries and geometric locality
Two constructions yield strong unitary k-designs and pseudorandom unitaries on D-dimensional grids with provably optimal depth.
-
Approximate Sparse State Preparation with the Grover-Rudolph Algorithm
Two enhancements to the Grover-Rudolph algorithm reduce CNOT gates and control qubits for sparse quantum state preparation, including an approximate variant with a classically computable overlap estimate.
-
Cartan-Khaneja-Glaser decomposition of $SU(2^n)$ via involutive automorphisms
Reformulation of Cartan-Khaneja-Glaser decomposition for SU(2^n) via involutive automorphisms and symmetric Lie algebra decompositions yields a stable recursive factorization with open-source Python code validated on ...
-
Quantum Monte Carlo algorithm for option pricing and its complexity analysis
A quantum Monte Carlo algorithm solves multidimensional Black-Scholes PDEs for option pricing with polynomial complexity in dimension d and accuracy 1/ε, with rigorous error bounds and a claimed speedup over classical...
-
Computational and physical complexity of synthesizing random multi-qudit quantum states and unitary operators
Computational complexity of random multi-qudit states and unitaries scales exponentially with qudit number, while physical complexity scales more slowly.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.