Deutsch-Jozsa Algorithm

• Related: Quantum Computing, Calcolabilità e Complessità
• Source: qiskit, Learn Quantum Computing with Python and Q [Ap.D]
• see Jupiter Notebook Extract

The first example of a quantum algorithm performing better than the best classical algorithm.

The algorithm can be applied to an oracle $‘U_f‘$ where $‘f‘$ is either constant or balanced and decide in $‘O(1)‘$ whether it’s one or the other, in a single application.

Algorithm

1. prepare two qubits, control and target, in the $‘|0⟩\otimes |0⟩‘$ state
2. prepare the state $| + - ⟩$¹
3. apply the oracle $‘U_f‘$ to input state $‘|+-⟩‘$
4. measure control in the $‘X\text{-basis}‘$
   • if 0 then $‘f‘$ is constant, otherwise $‘f‘$ is balanced

The algorithm can be extended to $‘n‘$ qubits with functions of form

$$f(x_0,x_1,\cdots ,x_n)$$

and n-qubits oracles

$$U_f|x_0{x}_1\cdots x_{n}y⟩=|x_0{x}_1\cdots x_n⟩\otimes |f(x_0,x_1,\cdots ,x_n)\oplus y⟩$$

Circuit for Deutsch-Jozsa

Code

Algorithm

namespace DeutschJozsa {
    open Microsoft.Quantum.Intrinsic;
    open Microsoft.Quantum.Measurement;
    open Microsoft.Quantum.Diagnostics;

    operation CheckIfOracleIsBalanced(oracle : ((Qubit, Qubit) => Unit))
    : Bool {
        use control = Qubit();
        use target = Qubit();

        H(control);
        X(target);
        H(target);

        oracle(control, target);

        H(target);
        X(target);

        return MResetX(control) == One;
    }

    operation RunDeutschJozsaAlgorithm() : Unit {
        Fact(not CheckIfOracleIsBalanced(ApplyZeroOracle),
            "Test failed for zero oracle.");
        Fact(not CheckIfOracleIsBalanced(ApplyOneOracle),
            "Test failed for one oracle.");
        Fact(CheckIfOracleIsBalanced(ApplyIdOracle),
            "Test failed for id oracle.");
        Fact(CheckIfOracleIsBalanced(ApplyNotOracle),
            "Test failed for not oracle.");

        Message("All tests passed!");
    }
}

Oracles

namespace DeutschJozsa {
    open Microsoft.Quantum.Intrinsic;

    operation ApplyZeroOracle(control : Qubit, target : Qubit) : Unit {
    }

    operation ApplyOneOracle(control : Qubit, target : Qubit) : Unit {
        X(target);
    }

    operation ApplyIdOracle(control : Qubit, target : Qubit) : Unit {
        CNOT(control, target);
    }

    operation ApplyNotOracle(control : Qubit, target : Qubit) : Unit {
        X(control);
        CNOT(control, target);
        X(control);
    }
}

Footnotes

1. shortand for $‘|+⟩\otimes |-⟩‘$ ↩