Many problems in computer science input boolean circuits to problems.

Just as a toy example, let's define the below problem to be called $A$:

Given a polynomial depth circuit with $N$ bits of output, C, does there exist an input $x$ such that $C(x) = 0$?

Is it correct to say that an equivalent problem, on a quantum computer is this:

Given a quantum gate, $U | x, y \rangle = | x, y \oplus C(x) \rangle$ determine if there is an $x$ such that $C(x) = 0$

Now suppose problem $A$ is complete for a complexity class $B$. If a quantum algorithm existed to solve $A$ with a polynomial complexity, would that imply that $B \subseteq BQP$? Is there any oracle separation business to worry about here?


1 Answer 1


No, it's obviously not equivalent, because computation on a quantum computer is not known to be equivalent to computation on a classical computer.

Also, it's not clear what you mean by a "quantum gate" or how it is specified on the input.

Yes, depending on the notion of completeness - it may depend on under what notion of reduction you are using for completeness. If the notion of reduction you are using is polynomial time algorithms (as is common), then yes, it follows that. You should spend some time trying to prove it. It follows directly from the definitions -- so see what you can come up with.

  • $\begingroup$ I'm not sure I understand. You are saying that problem A is not equivalent to the "quantum" variant (where the circuit is specified as a quantum oracle), so how can the problem be solved by a quantum algorithm? Is there another scheme to represent classical problems that input circuits on quantum computers? $\endgroup$
    – Loic Stoic
    Mar 17, 2023 at 9:22
  • $\begingroup$ Actually, I think I may understand. We cannot input a quantum gate to a quantum algorithm, but we can input a binary string. We can encode a circuit into this string, and run our algorithm on that. $\endgroup$
    – Loic Stoic
    Mar 17, 2023 at 10:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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