# 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.

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.