This concept, from the theory of quantum computation within physics and computer science, develops the quantum circuit model as a formal model of computation over the Hilbert space of n qubits, where gates are unitary transformations acting on a small number of qubits and complexity is defined relative to a preferred tensor-product decomposition into subsystems. It establishes three foundational results: gate-error accumulation is at most linear (total operator-norm error is bounded by T times per-gate error epsilon), so per-gate accuracy must scale as delta/T; the quantum complexity class BQP is contained in PSPACE via a Feynman path-integral (sum-over-histories) simulation that trades exponential time for polynomial memory; and two-qubit gates are exactly universal, meaning any unitary on n qubits can be realized precisely by a circuit of two-qubit gates. The exact-universality result is the theoretical core, proving that entangling two-qubit interactions plus single-qubit gates suffice to generate the entire unitary group.
This concept, from the theory of quantum computation within physics and computer science, develops the quantum circuit model as a formal model of computation over the Hilbert space of n qubits, where…