7

Take a quantum circuit on $n$ qubits, you have some sequence of gates.

You can represent these gates as hermitian matrices, and then with some padding, you could take the product of these matrices, by closure would be a hermitian matrix, a quantum operation. Then you have who knows how many gates into one single, but complicated $n$-ary gate.

On a perfect fidelity machine, this could be o(1) right. Does this logic make sense? I feel like it shouldn't be independent of the depth, or a lot of classical circuit problems become constant time on a QC.

glS
  • 27,510
  • 7
  • 37
  • 125
abrahimladha
  • 215
  • 1
  • 5

1 Answers1

7

The same could be said about any classically computable function. We could use the Cook-Levin theorem to unroll any Turing machine into a single but complicated $n$-input gate, and then claim it's $o(1)$.

Thus because we don't want this silly exception, usually when speaking of $\mathrm{BQP}$ or $\mathrm{P}$ in a circuit model, we have to limit our gate set (to, say, NAND gates classically and Hadamard/CCNOT gates quantumly).

Further we should put in a uniformity condition: given $n$ you'll need a Turing machine to provide the requisite quantum circuit (classical circuit) in polynomial time.

Mark Spinelli
  • 15,378
  • 3
  • 26
  • 83