Quantum Circuit Complexity

Formally, the circuit complexity C(U) of a unitary U is the minimum number of two-qubit gates from a fixed universal gate set needed to approximate U to within epsilon in operator norm. For pure state complexity, the same definition applies with U restricted to state-preparation circuits that map |0…0> to the target state. The notion is basis-dependent in a mild sense (different universal gate sets give complexities that differ by at most a polynomial factor), but the qualitative behavior is universal: almost all n-qubit unitaries have complexity exponential in n, because the set of unitaries reachable with polynomially many gates is exponentially small in the full unitary group.

The Brown-Susskind conjecture, proposed in the context of holographic duality and the AdS/CFT correspondence, identifies the interior volume of an Einstein-Rosen bridge (wormhole) connecting two entangled black holes with the quantum circuit complexity of the boundary quantum state. This conjecture, sometimes called “complexity equals volume,” predicts that complexity grows linearly in time for times exponentially long after the black hole forms, matching the known dynamics of the wormhole interior. The conjecture has driven significant interest in complexity theory among high-energy physicists, and proving or disproving it would require resolving deep open questions about the hardness of computing circuit complexity.

Circuit complexity is distinct from entanglement entropy. Two states can have high entanglement entropy but low circuit complexity (e.g., n EPR pairs, created by n Hadamard and CNOT gates) or low entanglement entropy but high circuit complexity (e.g., a highly scrambled product state). This distinction matters for classical simulation: tensor network methods efficiently simulate low-entanglement states regardless of their circuit complexity, while other classical methods target low-complexity circuits regardless of entanglement. Neither property alone determines classical simulability.

Computing the circuit complexity of a given unitary or state is believed to be classically intractable in general. No efficient classical algorithm is known for determining the minimum gate count of an arbitrary n-qubit unitary, and the problem is related to the difficulty of breaking quantum-secure cryptographic hash functions based on random circuits. For quantum advantage, circuit complexity provides a natural separating measure: problems that require exponentially complex unitaries to solve on a classical computer may be solved with polynomial-depth circuits on a quantum computer, giving a formal basis for quantum speedup beyond the BQP vs. BPP question.