Where is the problem stored in a quantum computer?

Question

I am trying to develop a more intuitive understanding of quantum computing -- I suppose Feynman would tell me that’s impossible! Let’s try: if we are trying to find the minimum of a surface or function, I can picture a grouping of qubits that would somehow consider the whole surface somewhat simultaneously, eventually finding the minimum. (Feel free to correct or improve upon that description, or tell me it’s completely useless.) My question is this: Where is the function specified, in the arrangement or connection of qubits, or in the classical programming of the inputs (and outputs?).

Answer 1

It depends on how you encode the problem with a quantum computer. There are different ways but I can explain one easily.

So we will call a set of qubits a register. Let's say our problem can be represented by n qubits and the output of the function on m qubits. You start usually in the $ | 0 \rangle^n | 0 \rangle^m $ state. You can create a superposition, which will represent all the candidates in the register of size n : $$ \sum_i | i \rangle | 0 \rangle^m$$

You can see the $ | i \rangle $ as binary strings, which can be considered candidate values/input of your problem. Note that sometimes the $| i \rangle $ are considered as indexes or adresses. In that case, you can either have values in another register and they will be "entangled" or linked with the $| i \rangle $, that is you have for each i an $x_i$ value, $| i \rangle | x_i \rangle $, but often in quantum algorithms it is left to an "oracle" which is a shortcut for stating any ways that will do it for us, or any ways of accessing those values (and computing the function most of the time).

Now by using quantum gates, which is a unitary transformation representing our function (call it U), we apply and we get the output for each candidate in the register of size m: $$ U \sum_i | i \rangle | 0 \rangle^m \rightarrow \sum_i | i \rangle | f(i) \rangle or \sum_i | i \rangle | x_i \rangle | f(x_i) \rangle $$

The unitary may just be a translation of bit operations into quantum gates, representing the classical computation of this function but abstractly we denote by any unitary transformations U. This can also be shortcuted as an "oracle". Note that with measurements, you get only one output at a time.

The second type of encoding I have seen is encoding values in amplitudes of a quantum register. For example having a vector (which will be considered normalized) of real components $x_i$, it will be encoded in a n-qubit register as : $$ \sum_{i=1}^{2^n} x_i | i \rangle $$
But that is non trivial to carry out and this way you are not representing every possibilities in superposition, but again computing the function is like applying a unitary operation.

Conclusion : You specify the function as a unitary operation or an "oracle". The storing of a problem on a quantum computer is not restricted to one way and is an exercise on its own. Still you have one more natural way I tried explaining. And this is also the case classically.

Answer 2

Generally speaking if you're doing, say, Grover's algorithm (function inversion in $\sqrt{N}$ rather than $N$ time) you would want to program the function itself using the quantum gates that your qubits are passing through. Hypothetically that information could be stored in a "program" of classical bits stored alongside, if you have the ability to control which of a set of quantum gates is applied with a classical computer.

The hazard here is that quantum gates can only describe reversible logic whereas usual logic gates like AND and OR are not reversible. So your first step would typically involve implementing a reversible logic gate that is universal, like Toffoli (also called CCNOT, toffoli_3(x, y, z) = (x AND y) XOR z.