0
$\begingroup$

In computer science, problems can input arithmetic circuits. For example, let's just consider an example search problem:

You are given an input $x \in \mathcal{I}$. $x$ is a tuple $(n, C)$, where $C$ is an arithmetic circuit inputting $n$ bits and outputting a value. Your task is to compute this output. Assume that $C$ can be computed in polynomial time.

My question is this:

This problem can be solved in polynomial time classically, as $C$ is polynomial in size. But how could this problem be solved on a quantum computer, for example if $C$ could not be represented as a unitary matrix? Even if $C$ could be represented as a unitary matrix, isn't it an assumption that the quantum algorithm's user would have access to such a quantum gate?

If this question doesn't make much sense: I am essentially asking how we can assume the interchange between classical (arithmetic) circuits (that need not be unitary) and quantum circuits.

$\endgroup$

1 Answer 1

1
$\begingroup$

I may misunderstand your question but in general it is possible to convert any classical logic circuit to a quantum circuit (I assume your arithmetic circuit is a digital logic circuit and not something analog). With these quantum gates:

enter image description here

You can, for example, construct a classical AND gate:

enter image description here

and with that, of course, the universal NAND gate. For a real circuit you also need fanout:

enter image description here

You may wonder whether that would violate the no-cloning theorem but it does not. You can clone qubit states that are in pure $|0\rangle$ or $|1\rangle$ states.

With these constructions you should be able to compute your problem on a quantum computer (unless, again, I might have misunderstood your question).

$\endgroup$
1
  • $\begingroup$ Thank you for your answer. The use of an "output" register is useful to convert classical circuits to quantum ones is interesting. But my question is really about "how are we able to assume that we know how to convert between the two in polynomial time." For example, with your AND gate example: what algorithm would convert a classical AND to a quantum AND with an output register, and would it be run in polynomial time? If we were given an arbitrary classical circuit, could we convert it? $\endgroup$
    – wavosa
    Feb 18, 2023 at 17:45

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.