6
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I have this as a followup: I don't know how to build, physically, any classical n-ary gate without breaking it down into smaller gates using dominos, electricity, etc. But I believe I can build any n-ary quantum gate by computing the right pulses and then just firing the magic quantum gun. Like the U3 gate on IBM systems takes three parameters and can represent any unary gate. I could be convinced an analog is possible for an n-ary system. If you say we fix a circuit basis, some unary operations might take more than a few steps, when in the real world using the U3 gate, it takes one step. $\endgroup$
    – abrahimladha
    Apr 30, 2021 at 18:09
  • $\begingroup$ I'm not familiar with the U3 gate, but I'm not sure I believe or understand the statement "some unary operations might take more than a few steps, when in the real world using the U3 gate, it takes one step". Perhaps you are asking about a single rotation gate being able to apply a rotation of a qubit about an arbitrary angle, in which case the Solovay-Kitaev theorem states that a single qubit gate (a unary gate in your language) generates a dense subset of $\mathrm{SU}(2)$ efficiently. But that says nothing about $n$-ary ($n$-input) gates. $\endgroup$
    – Mark S
    Apr 30, 2021 at 19:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.