Quantum Information HT24, Query complexity
Flashcards
What is an oracle?
A theoretical black box which provides solutions to specific problems instantly.
Suppose we have an oracle $\mathcal B _ f$ which answers questions about some function $f$ we are interested in. What is the query complexity of a problem?
The minimum number of queries to the oracle needed to solve the problem (this might be infinity if the oracle is unrelated to the problem).
When considering classical (i.e. non-quantum) solutions to problems with an oracle that gives information about a function $f$, what is a reasonable choice for the oracle to define the query complexity of that problem?
The function itself.
Suppose:
- $f : \{0, 1, \cdots, M-1\} \to \{0, 1, \cdots, N - 1\}$
For classical problems, we can just take the oracle for this function to be the function itself. Why is this not possible if we wish to implement $f$ as some quantum circuit, and hence what is the quantum oracle for this function?
Since every quantum circuit is reversible, it’s impossible to implement non-invertible functions (in partcular).
Hence we “remember” the input by defining the oracle as the unitary gate $U _ f$ acting on $\mathbb C^M \otimes \mathbb C^N$ defined by the relation
\[U _ f( \vert x\rangle \otimes \vert y\rangle) := \vert x\rangle \otimes \vert y \oplus f(x) \rangle\]where $\oplus$ denotes addition modulo $N$.
Suppose:
- $f : \{0, 1, \cdots, M-1\} \to \{0, 1, \cdots, N - 1\}$
- $U _ f$ acting on $\mathbb C^M \otimes \mathbb C^N$ is the corresponding quantum oracle for this function, defined by the relation $U _ f( \vert x\rangle \otimes \vert y\rangle) := \vert x\rangle \otimes \vert y \oplus f(x) \rangle$ where $\oplus$ denotes addition modulo $N$.
What is the inverse of this gate?
where $\ominus$ denotes subtraction modulo $N$.
Suppose:
- $f : \{0, 1, \cdots, M-1\} \to \{0, 1, \cdots, N - 1\}$
- $U _ f$ acting on $\mathbb C^M \otimes \mathbb C^N$ is the corresponding quantum oracle for this function, defined by the relation $U _ f( \vert x\rangle \otimes \vert y\rangle) := \vert x\rangle \otimes \vert y \oplus f(x) \rangle$ where $\oplus$ denotes addition modulo $N$.
In what sense is this gate at least as powerful as the classical oracle $f$ (which is just the function itself), and how is actually stricly more powerful than the classical oracle?
We can ask questions about specific values of $f$ by computing
\[U _ f ( \vert x\rangle \otimes \vert 0\rangle) = \vert x\rangle \otimes \vert f(x)\rangle\]and then measuring in the computational basis.
But we can also determine global properties of $f$, e.g. if we compute
\[U _ f( \vert e _ 0\rangle \otimes \vert 0\rangle)\]where
\[\vert e _ 0\rangle = \frac{\sum^{M-1} _ {x = 0} \vert x\rangle}{\sqrt M}\](a Fourier basis state), then we obtain
\[\begin{aligned} U _ f( \vert e _ 0 \rangle \otimes \vert 0\rangle) &= \frac{\sum^{M-1} _ {x = 0} U _ f( \vert x\rangle \otimes \vert 0\rangle)}{\sqrt M} \\\\ &= \frac{\sum^{M-1} _ {x = 0} \vert x\rangle \otimes \vert f(x)\rangle}{\sqrt M} \end{aligned}\]