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 7 Pith papers
-
Practical Tests and Witnesses of Fermionic non-Gaussianity
Introduces practical witnesses of fermionic non-Gaussianity via antiflatness from covariance matrices, with two efficient measurement protocols, a purity-corrected version for mixed states, and experimental results on...
-
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.
-
Statistical and Algorithmic Foundations of Probing Quantum Systems with Compressive Measurements: A Review
A survey of structured quantum state tomography covering compact representations, measurement design, and optimization algorithms, connected to compressive sensing for sample efficiency.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.