What is the rationale behind black-box quantum circuit?

Question

I've read some material about quantum computers and quantum circuits. A certain number of already known algorithms (Simon's algorithm, period-finding algorithm, Grover's algorithm, …) have the following form:

Suppose I have an unknown classical function f: {0,1}^n -> {0, 1}^m satisfying a certain number of statements. I can associate the (unknown) quantum circuit U_f to it and plug the |0.. 0> input state. Now let us define circuit X and show that when appended to U_f, the global output can be measured to extract some information about f.

Wait a minute... What is the relation with classical circuits? A classical problem would refer to an unknown input that satisfies certain properties, this input representing a state coming from outside (user action, file system, database, server, whatever). In case this state is rather generated by another circuit/algorithm the logic applies to the input before. In the end we don't reason about unknown circuits but about unknown inputs. The circuits (the algorithms/ the functions) are the known/chosen components.

Here I came to realize that the common name "circuit" was somehow misleading. In a classical world gate inputs can be thought as values coexisting with outputs. But quantum gates seem to require a temporal interpretation: inputs and outputs represent temporal evolution of the same qubits.

Now this does not really explain how you transform a given bunch of a priori unknown classical input bits (that I believe your keyboard will keep on generating in the future except maybe if Schrödinger's cat is sitting on it) into a "black box quantum circuit" transforming |0…0> into something to be reversed. For example Grover's algorithm propose, for a quantum circuit corresponding to a function f: {0, 1}^n -> {0, 1} that yields 1 for a single unknown input, an efficient method to determine this input. Nice! But how and why would you have to start with such a circuit in the first place?

Answer 1

In practice, the 'unknown function black box' is just a circuit that checks if its input meets some criteria or is the solution to a problem.

This is useful because it's easier to make a circuit that detects a solution than it is to actually find a solution. Grover's algorithm then augments our detector circuit into a solver circuit:

---

The classical equivalent of Grover's algorithm is a brute-force search function like this:

def bruteForceSearch(min, max, predicate):
    for i in min..max:
        if predicate(i):
            return i
    return none

which you would use it like so:

let mersennePrimeWithFiveDigitExponent = bruteForceSearch(
     10000,
     99999,
     i => isMersennePrime(2**i - 1))

Notice how the brute force search turns our knowledge of how to recognize something into a mechanism for finding something. Grover's algorithm does the same thing, but quadratically faster and with the caveat that the recognizer must be implemented as a reversible circuit.