Someone argues: "A quantum computer on qubits has a state described by complex amplitudes

PHYSICS · Multi-part · Fermi University Physics · Quantum Information & Technology · The quantum circuit model and quantum algorithms · The quantum circuit model and quantum algorithms

Quantum Information and Technology, Ch What quantum computers can compute efficiently

Problem

Someone argues: "A quantum computer on

100

qubits has a state described by

2^{100}

complex amplitudes. This is a huge but finite number. Since every

\mathrm{PSPACE}

computation can, in principle, be carried out by trying every configuration of a polynomial-size memory, and

2^{100}

already exceeds the number of configurations of any memory of a few hundred bits, the quantum computer's state secretly contains the answer to any

\mathrm{PSPACE}

problem among its amplitudes after one polynomial-size circuit. So

\mathrm{PSPACE}\subseteq\mathrm{BQP}

." ((a)) Find the error in this argument. ((b)) State the containment between

\mathrm{BQP}

and

\mathrm{PSPACE}

that is actually proved, and in one sentence say how the path-sum computation of an amplitude such as

\langle y|C|x\rangle

establishes it.

Browse the problem library