# Quantum problems that input arithmetic circuits

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.

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: You can, for example, construct a classical AND gate: and with that, of course, the universal NAND gate. For a real circuit you also need fanout: 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).

• 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? Feb 18 at 17:45