Physics – Quantum Physics
Scientific paper
1995-08-08
Physics
Quantum Physics
uuencoded compressed postscript, LACES 68Q-95-30
Scientific paper
It was recently shown that for reasonable notions of approximation of states and functions by quantum circuits, almost all states and functions are exponentially hard to approximate [Knill 1995]. The bounds obtained are asymptotically tight except for the one based on total variation distance (TVD). TVD is the most relevant metric for the performance of a quantum circuit. In this paper we obtain asymptotically tight bounds for TVD. We show that in a natural sense, almost all states are hard to approximate to within a TVD of 2/e-\epsilon even for exponentially small \epsilon. The quantity 2/e is asymptotically the average distance to the uniform distribution. Almost all states with probability amplitudes concentrated in a small fraction of the space are hard to approximate to within a TVD of 2-\epsilon. These results imply that non-uniform quantum circuit complexity is non-trivial in any reasonable model. They also reinforce the notion that the relative information distance between states (which is based on the difficulty of transforming one state to another) fully reflects the dimensionality of the space of qubits, not the number of qubits.
No associations
LandOfFree
Bounds for Approximation in Total Variation Distance by Quantum Circuits does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Bounds for Approximation in Total Variation Distance by Quantum Circuits, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bounds for Approximation in Total Variation Distance by Quantum Circuits will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-88940