Is there a way to build a mostly classical Turing machine with a special quantum oracle that's equivalent in power to a quantum Turing machine?
I am vaguely familiar with the concept of an oracle machine from other contexts. In particular, I've seen the construction used to attach a halting oracle to an ordinary Turing machine. The construction I'm most familiar with has two additional tapes, one for encoding a question to ask the oracle, one tape for receiving the answer, and a special instruction for asking the oracle a question, which causes the oracle to write its answer on the answer tape. In this construction the oracle is completely opaque. Each additional tape also has an additional head.
My question is twofold.
A) Is it possible to use a similar construction to make a Turing machine with a quantum circuit simulator as an oracle (henceforth a quantum oracle machine) instead of a halting oracle?
B) Assuming it's possible to define a quantum oracle machine, is it equivalent in terms of efficiency to a quantum Turing machine or does a quantum oracle machine incur an exponential penalty when emulating a quantum Turing machine as an ordinary Turing machine would?
The Wikipedia article does not completely nail down what a quantum Turing machine is and offers an informal sketch instead. I'm assuming for the purposes of this question that there is a single agreed upon notion of what a quantum Turing machine is and that it therefore makes sense to compare my attempted definition to the real definition.
What follows is my attempt to define a quantum oracle machine, which is an ordinary Turing machine with a quantum oracle attached to it.
As a summary of this construction. I am defining an assembly-language-like notation for a small subset of possible quantum circuits and insisting by fiat that the quantum oracle samples from the resulting state and dumps the output into a special output tape.
I will define a Turing machine with four tapes. A tape is a mapping from $\mathbb{N}$ to $\Sigma$, the alphabet. Let $Q$ be the set of states of the Turing machine with $q_0$ as the starting state.
- An input tape $A$ (initially blank unless otherwise specified)
- An output tape $B$ (initially blank)
- A quantum oracle input tape $C$ (initially blank)
- A quantum oracle output tape $D$ (initially blank)
All tapes share the same alphabet $\Sigma$. Let $b \in \Sigma$ be the designated blank symbol.
Let $I$ be the set of instructions. $I$ contains $L_A$ which moves the $A$ tape left one space and $R_A$ which moves the $A$ tape right one space or does nothing if it is at position zero. $I$ contains similar shifting operations for each tape.
$I$ also contains the instruction $W_A(x)$ which writes the symbol $x$ to the current position in the tape $A$ and likewise for each of the other tapes.
$I$ also contains the instruction $=\!\!(x)$, which sets the current state to $x$.
$I$ also contains the instruction $h$ halt.
$I$ also contains the instruction $s$ which queries the quantum oracle, clears the tape $C$, and causes the tape $D$ to be populated with the response. I'm not sure whether the construction differs significantly with regard to computational efficiency if we allow repeated queries from the oracle with the same quantum circuit without needing to "rebuild" the quantum circuit for each distinct measurement.
This completes the construction of $I$.
We have a transition function $\delta : Q \times \Sigma^4 \to \mathrm{FinSeq}[I]$. $Q$ is a total function mapping every combination of the state of the head and current symbol on each of the tapes to a finite sequence of instructions.
Next, I am going to define the behavior of the quantum oracle. I am really uncertain about this.
Based on the comments to this question I asked previously, a Deutsch gate $D(\theta)$ is universal when $\theta$ is not a rational multiple of $\pi$. Based on this, I am going to use $D(\frac{1}{2})$ as my sole gate in my quantum circuit.
I will describe a quantum circuit and its initial state (which will always be pure and never be mixed) in an assembly language of sorts, defined below.
Let $a[0] := 1$ set the zeroth qubit to $1$. Let $a[0] := 0$ set the zeroth qubit to $0$. Let $a[n] := k$ set the $n$th qubit to $k$ where $k \in \{0, 1\}$. All qubits are implicitly initialized with the pure classical state $0$.
I additionally define the construction $d(i, j, k)$ which takes the $i$th, $j$th, and $k$th qubit and applies the transformation $D(\frac{1}{2})$ to them and only them.
For example, here is a quantum assembly program. It does nothing useful as far as I know.
a[0] := 1
a[1] := 1
a[3] := 1
d(0, 1, 2)
d(1, 2, 3)
When the instruction $s$ is called, the quantum oracle reads the program encoded in the tape $C$, runs it, and performs a measurement on the entire sequence of qubits $a[0], a[1], \cdots$ and dumps the result into the tape $D$. The $i$th element of the tape $D$ is the sample value of the qubit $a[i]$. Finally, the tape $C$ is cleared. The tape $C$ is cleared to capture the intuition that repeatedly sampling from a quantum state requires building it up, from scratch, over and over again.
This completes my toy construction of the quantum oracle machine.
I have some serious misgivings about many of the details of this construction. For example, constructing a "fair coin" that's $0$ with probability $\frac{1}{2}$ and $1$ with probability $\frac{1}{2}$ is impossible. Also, the quantum oracle in this toy construction is instantaneous and costs nothing to run, I attempted to capture the "cost" of quantum computation by requiring the user to write into the tape $C$ repeatedly.