10
$\begingroup$

I am trying to simulate Deutsch's algorithm (elementary case of Deutsch-Josza algorithm), and I am not entirely sure how I would go about implementing the quantum oracle necessary for the algorithm to function, without defeating the purpose of the algorithm and "looking" at what the inputted function is, by evaluating the function.

$\endgroup$
  • $\begingroup$ This may be helpful: quantumcomputing.stackexchange.com/a/2262/2645 $\endgroup$ – meowzz Oct 30 '18 at 16:53
  • $\begingroup$ Why not pick it at random each time you run the test? That way you can't know. $\endgroup$ – DaftWullie Oct 30 '18 at 17:16
  • $\begingroup$ @DaftWullie Are you referring to picking a function at random in each simulation? The issue still arises that the computer has to know what the outputs of the inputted function are, in order to create the needed function, through a quantum oracle. $\endgroup$ – Jack Ceroni Oct 30 '18 at 17:39
  • $\begingroup$ Yes, the computer needs to know, but you can localise it to a single function that takes as input a quantum state, and gives a quantum state as output. Only that function would know it (and something has to know it). Moreover, if the random choice is local to that function, and is different every time it's called, that sits nicely with the fact it should only get called once. $\endgroup$ – DaftWullie Oct 31 '18 at 11:43
  • $\begingroup$ @DaftWullie If you compute a property of a random function, why not just immediately produce a random output? $\endgroup$ – Norbert Schuch Oct 31 '18 at 12:32
7
$\begingroup$

There are two questions here. The first asks how you might actually implement this in code, and the second asks what's the point if you know which oracle you're passing in.

Implementation

Probably 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;
    }
}

What's the point?

Query complexity

Computational 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.

The Deutsch oracle problem is interesting to complexity theorists because the quantum algorithm only has to query the black box once, but the classical algorithm has to query it twice. With the generalized Deutsch-Josza problem where an $n$-bit oracle contains a function which is either constant or balanced, the quantum algorithm again only has to query it once but the (deterministic) classical algorithm requires $2^{n-1}$ queries.

It should be noted that a probabilistic classical algorithm exists which solves the Deutsch-Josza problem in much fewer than $2^{n-1}$ queries by randomly sampling oracle inputs: if the oracle continues to output the same value no matter the input, the probability that the oracle is constant grows very quickly. This means Deutsch-Josza is not a good candidate for a quantum supremacy/advantage problem, which leads into...

Applications in the real world

If 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.

If we look at the simplest representation of the one-bit Deutsch Oracle, the gate construction is as follows:

Identity: $C_{1,0}$

Negation: $X_0C_{1,0}$

Constant-0: $\mathbb{I}_4$

Constant-1: $X_0$

However, these are by no means the only way to implement the oracles. All of these can be rewritten using hundreds, thousands, even millions of logic gates! All that matters is the cumulative effect of these logic gates is equivalent to the above simple construction. Consider the following alternative implementation of Constant-1:

$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$

This is because of the associativity of matrix multiplication. If you write out the actual matrices for $H_0Z_0H_0$ and multiply them together, you get $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$

So we have:

$(H_0(Z_0(H_0|\psi\rangle))) = (((H_0Z_0)H_0)|\psi\rangle) = X_0|\psi\rangle$

So you can pass in the circuit $H_0Z_0H_0$ (or something vastly more complicated) into your quantum Deutsch Oracle algorithm instead of $X_0$, and the algorithm still works! It will tell you whether the oracle is constant or variable, regardless of how complicated its internals are. So an algorithm which "cheats" and looks inside the black box doesn't have quite as simple a time as you might think. Consider the case of I, a stranger on the internet, giving you a very complicated circuit guaranteed to be constant or variable then asking you which it is. Not something so easily solved by just looking at it!

Important for historical & pedagogical reasons

Primarily, the Deutsch Oracle problem is important for historical and pedagogical reasons. It's the first algorithm taught to students because it's the simplest, and seems to demonstrate quantum speedup as long as you don't ask too many questions. It also serves as a good launching point for learning Simon's Periodicity Problem and then Shor's Algorithm.

$\endgroup$
  • $\begingroup$ I was with you until the Gotteman-Knill thing. Why do you restrict your complicated circuit to (i) one-qubit gates and (ii) stabilizer gates? $\endgroup$ – Norbert Schuch Oct 31 '18 at 12:33
  • $\begingroup$ As I understand it, there are efficient algorithms for determining whether an arbitrary quantum circuit implements one of several simple classical circuits. Random circuits being studied for quantum advantage require more complicated behaviour. $\endgroup$ – ahelwer Oct 31 '18 at 17:07
  • $\begingroup$ I don't think this is true. If I am not mistaken, asking if two circuits do the same thing is QMA-complete. It is only your restriction to Clifford gates which allow simulability through Gottesman-Knill. $\endgroup$ – Norbert Schuch Oct 31 '18 at 17:27
  • $\begingroup$ You're correct, I'll research the circuit reduction thing some more then update my post to clarify the role of Gottesman-Knill. $\endgroup$ – ahelwer Oct 31 '18 at 17:47
  • $\begingroup$ I updated my answer after asking Robin Kothari some questions over email. $\endgroup$ – ahelwer Nov 5 '18 at 20:20
3
$\begingroup$

There is no way to build the oracle in a way which would not defeat the point of Deutsch's algorithm - that's why it is an oracle-based algorithm.

The only way would be if you would come up with an incredibly hard to compute function (this is, an incredibly long circuit) which would take one input bit $x$ and give one output bit $f(x)$ (but on the way could use as many ancillas as you want), and where for some reason you would only be interested whether $f(0)=f(1)$. Then, you could use Deutsch's algorithm to save half the time (since you have to run this circuit only once).

Now, this sounds pretty contrived, and it is. On the other hand, it sounds equally contrived that there might be function $f(x)$ where $1 \leq x \leq N$ and $f(x)$ integer, and you would like to find some $y$ such that $f(x+y)=f(x)$, without the need to learn $f(x)$ itself - yet, it turns out this is exactly what is required for factoring.

So the point is that oracle-based algorithms prove that you can get a speed-up if you have a problem with that structure (i.e. where you only want to learn some specific property of a function), but it doesn't tell you if such a problem exists.

So if you want to implement Deutsch, any way of doing the oracle is fine - it is a "proof-of-principle" algorithm and does not yield an actual speed-up on a real problem (at least none we know of).

$\endgroup$
2
$\begingroup$

You have two examples on the IBM Q Experience page about the algorithm. They show an example of a function. This could inspire you for your simulations I hope.

$\endgroup$
2
$\begingroup$

I don't have an example for Deutsch's algorithm handy, but here and here are two tutorials which walk you through implementing the Deutsch-Jozsa algorithm and the oracles it uses in Q#.

The idea for these two algorithms is the same: you have to provide the oracle to the algorithm as an operation implemented elsewhere. This way the algorithm doesn't know which oracle it is given and doesn't have a way to "look" at the oracle other than by calling it. These tutorials also have a harness which counts how many times the oracle is called, so that if your solution calls it more than once, it fails the test.

Admittedly, this still has a problem which oracle algorithms frequently have: a human can look at the implementation of the test and of the oracle passed and figure out the answer by figuring out which oracle is implemented. This can be countered by randomizing the oracle choice, as DaftWullie suggested.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.