3
$\begingroup$

Here are the 4 classical functions over $1$ bit we're examining, $f(x) = \{0,1\}, x \in\{0,1\}$:

  • identity (balanced) -> $f(x) = x$: \begin{bmatrix}1&0\\0&1\end{bmatrix}
  • negation (balanced) -> $f(x) = \neg x$: \begin{bmatrix}0&1\\1&0\end{bmatrix}
  • constant one (constant) -> $f(x) = 1$: \begin{bmatrix}0&0\\1&1\end{bmatrix}
  • constant zero (constant) -> $f(x) = 0$: \begin{bmatrix}1&1\\0&0\end{bmatrix}

The goal is to determine if a black-box is implementing a balanced or a constant function. Classically, this would require two queries. The proposition is that a quantum algorithm can solve the problem more efficiently by evaluating the black-box function over an equal superposition.

Fine, let's examine the quantum versions of those $4$ functions.

The balanced functions are reversible and one can use them in quantum algorithms, however, the constant functions are not. To make them reversible, Deutsch adds an ancilla qubit like this $f(|x\rangle|y\rangle)=|𝑥\rangle|y\oplus f(x)\rangle$;

Once I start converting the classical matrices to their quantum versions, I have no problem with the balanced ones. For example, negation becomes:

\begin{bmatrix}0&1&0&0\\1&0&0&0\\0&0&1&0\\0&0&0&1\end{bmatrix}

By presetting the ancilla qubit to $0$, I get the classical behavior:

  • $|0\rangle|0\rangle\mapsto|0\rangle|1\rangle$
  • $|0\rangle|1\rangle\mapsto|0\rangle|0\rangle$

$0$ turns to $1$, $1$ turns to $0$ as I would expect. The identity matrix also satisfies me, since:

  • $|0\rangle|0\rangle\mapsto|0\rangle|0\rangle$
  • $|0\rangle|1\rangle\mapsto|0\rangle|1\rangle$

Now, let's look at the quantum matrix for constant one:

\begin{bmatrix}0&1&0&0\\1&0&0&0\\0&0&0&1\\0&0&1&0\end{bmatrix}

  • $|0\rangle|0\rangle\mapsto|0\rangle|1\rangle$
  • $|0\rangle|1\rangle\mapsto|0\rangle|0\rangle$

I'm bothered that $01$ gets converted to $00$. I would expect the result to be $01$. It seems that this gate is not the quantum equivalent of the constant $1$, since it cannot be used over classical states to achieve the same result as the classical gate. It's a completely different gate.

If that's really the case, how can I justify that the quantum and classical solutions of Deutsch's problem are even solving the same problem?

$\endgroup$

1 Answer 1

4
$\begingroup$

In your framing, the second qubit is the ancilla that's initialized to $\vert 0\rangle$. That is, the first qubit is the input qubit, which remains the same after application of the oracle, and the second qubit is the answer qubit, which stores the answer, but must be preset to $|0\rangle$.

Asking about the behavior when the second qubit is initialized to $|1\rangle$ is outside the scope of the setup of Deutsch's algorithm.

As long as the second qubit is initialed to $|0\rangle$, then after application of the oracle the second qubit will constantly be $|1\rangle$ (if the oracle is the constant-$1$ function).

Thus when you ask about why $01$ doesn't get mapped to $01$, it's because in that question, the second qubit is initialized to $|1\rangle$ (which doesn't satisfy the setup).

$\endgroup$
2
  • 1
    $\begingroup$ Your answer helped me get it. What was missing is that the input qubit remains the same and the ancilla qubit is the one that holds the result. I can now see that when applying the constant 1 with the ancilla preset to 0, I get: 00 -> 01 & 10 -> 11; The input (left) qubit remains the same to guarantee reversibility, the second (ancilla) qubit shows the result. Is that right? $\endgroup$ Feb 13 at 16:33
  • 1
    $\begingroup$ Yeah, you got it. $\endgroup$
    – Mark S
    Feb 13 at 16:44

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.