1995/08/08 by Emanuel Knill, E. Knill, Knill, E. · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #Combinatorics (math.CO) #FOS: Mathematics #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #Quantum and electron transport phenomena #math.CO #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/9508007
uuencoded compressed postscript, LACES 68Q-95-30
arxiv created 1995/08/08 · openalex publication_date 1995/08/08 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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-εeven for exponentially small ε. 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-ε. 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.