Approximation by Quantum Circuits

arXivquant-ph/9508006MaRDI QIDQ6502376FDOQ6502376

Authors: Emanuel Knill 

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 page was built for publication: Approximation by Quantum Circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6502376)