The Deutsch-Jozsa algorithm

Problem statement

The problem addressed by the Deutsch-Jozsa algorithm involves determining the nature of a given Boolean function f . The function is either constant (returns the same output for all inputs) or balanced (returns 0 for half of the inputs and 1 for the other half).

Classical Solution:

In the classical case, determining whether a function is constant or balanced would require evaluating the function for multiple inputs to see if there is any variation in the output. This would take 2^{n-1}+1 queries in the worst case for a function with n bits.

Quantum computers only need one query for the function to determine if f is constant or balanced.

Quantum Solution

Implementation in Qiskit

from qiskit import Aer, QuantumCircuit, transpile, assemble
from qiskit.visualization import plot_histogram

def deutsch_jozsa_algorithm(oracle_type='balanced'):
    # Define the oracle function based on the input type
    if oracle_type == 'constant':
        oracle = QuantumCircuit(2, name='Oracle')
    elif oracle_type == 'balanced':
        oracle = QuantumCircuit(2, name='Oracle')
        oracle.cx(0, 1)  # Apply a CNOT gate to make the function balanced

    # Create the Deutsch-Jozsa circuit
    dj_circuit = QuantumCircuit(2, 1)
    dj_circuit.x(1)  # Set the second qubit to |1⟩
    dj_circuit.h([0, 1])  # Apply Hadamard gates to both qubits
    dj_circuit += oracle  # Add the oracle to the circuit
    dj_circuit.h(0)  # Apply Hadamard gate to the first qubit
    dj_circuit.measure(0, 0)  # Measure the first qubit

    return dj_circuit

# Simulate the algorithm for a balanced oracle

dj_circuit_balanced = deutsch_jozsa_algorithm('balanced')
backend = Aer.get_backend('qasm_simulator')
compiled_circuit = transpile(dj_circuit_balanced, backend)
result = backend.run(compiled_circuit, shots=1).result()
counts = result.get_counts()
print(f"Result for balanced oracle: {counts}")

# Simulate the algorithm for a constant oracle

dj_circuit_constant = deutsch_jozsa_algorithm('constant')
compiled_circuit = transpile(dj_circuit_constant, backend)
result = backend.run(compiled_circuit, shots=1).result()
counts = result.get_counts()
print(f"Result for constant oracle: {counts}")