Implementation
##Implementation
ProbablyProbably the best way is to create a function IsBlackBoxConstant which takes the oracle as input, then runs the Deutsch Oracle program to determine whether it is constant. You can select the oracle at random, if you want. Here it is, implemented in Q#:
operation IsBlackBoxConstant(blackBox: ((Qubit, Qubit) => ())) : (Bool)
{
body
{
mutable inputResult = Zero;
mutable outputResult = Zero;
// Allocate two qbits
using (qbits = Qubit[2])
{
// Label qbits as inputs and outputs
let input = qbits[0];
let output = qbits[1];
// Pre-processing
X(input);
X(output);
H(input);
H(output);
// Send qbits into black box
blackBox(input, output);
// Post-processing
H(input);
H(output);
// Measure both qbits
set inputResult = M(input);
set outputResult = M(output);
// Clear qbits before release
ResetAll(qbits);
}
// If input qbit is 1, then black box is constant; if 0, is variable
return One == inputResult;
}
}
operation IsBlackBoxConstant(blackBox: ((Qubit, Qubit) => ())) : (Bool)
{
body
{
mutable inputResult = Zero;
mutable outputResult = Zero;
// Allocate two qbits
using (qbits = Qubit[2])
{
// Label qbits as inputs and outputs
let input = qbits[0];
let output = qbits[1];
// Pre-processing
X(input);
X(output);
H(input);
H(output);
// Send qbits into black box
blackBox(input, output);
// Post-processing
H(input);
H(output);
// Measure both qbits
set inputResult = M(input);
set outputResult = M(output);
// Clear qbits before release
ResetAll(qbits);
}
// If input qbit is 1, then black box is constant; if 0, is variable
return One == inputResult;
}
}
What's the point?
(a) Query complexity
##What's the point? ###Query complexity ComputationalComputational complexity is a field concerned with classifying algorithms according to the quantity of resources they consume as a function of input size. These resources include time (measured in steps/instructions), memory, and also something called query complexity. Query complexity is concerned with the number of times an algorithm has to query a black-box oracle function.
(b) Applications in the real world
###Applications in the real world IfIf you aren't a complexity theorist, you might reasonably not care very much about query complexity and instead want to know why the Deutsch oracle problem is important in a "no rules" world where you're allowed to look inside the black box. Trying to analyze an oracle problem as a non-oracle problem is fraught with difficulty, and I don't believe anybody has solved the question of the best classical algorithm for the Deutsch oracle problem when you are allowed to analyze the oracle circuit. You might think - what is there to analyze? There are only four possible circuits! In fact, it is much more complicated.
$H_0Z_0H_0$$$H_0Z_0H_0\,.$$
It turns out that, for any input, you could ever give:
$H_0Z_0H_0|\psi\rangle = X_0|\psi\rangle$$$H_0Z_0H_0|\psi\rangle = X_0|\psi\rangle\,.$$
$H_0Z_0H_0 = \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}} \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix} \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}} \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} = X_0$$$H_0Z_0H_0 = \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}} \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix} \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}} \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} = X_0\,.$$
$(H_0(Z_0(H_0|\psi\rangle))) = (((H_0Z_0)H_0)|\psi\rangle) = X_0|\psi\rangle$$$(H_0(Z_0(H_0|\psi\rangle))) = (((H_0Z_0)H_0)|\psi\rangle) = X_0|\psi\rangle\,.$$
###Important for historical & pedagogical reasons
