メインコンテンツまでスキップ

# The Deutsch–Jozsa algorithm

In this tutorial, some circuits are constructed with the controlled_on option. This is the experimental multi-controlled circuit feature, which is not yet released in the latest version of QURI Parts.

The Deutsch-Josza algorithm is an algorithm that deterministically solves the following problem:

Given an oracle that implements the function

$$$f: \{0, 1\}^n \rightarrow \{0, 1\}$$$

where $\{0, 1\}^n$ is a bit string of length $n$ and the function is guaranteed to be either constant (maps all possible bit strings to either 0 or 1[1]) or balanced (map half of the bit strings to 0 and the other half to 1.)

In this example, we demostrate how to use QURI Parts to:

• Build the problem oracle
• Embed the oracle into the solution circuit
• Execute the solution circuit

[1] ^ In the case of constant function, the algorithm works for oracle that implements $f(x) = 0$ and $f(x) = 1$. However, without loss of generality, we only build the oracle such that it implements $f(x) = 0$ in the case of constant function.

## The problem oracle​

In this section, we build the oracle circuit with QURI Parts. If the oracle implements a constant function, we simply return a function with no gates. If the oracle implements a balanced function, we randomly pick $2^{n-1}$ bit strings out of $2^n$ possible input bit strings that satisfies $f(x) = 1$.

For bit strings of lenth $n$, the oracle is implemented as a circuit with $n+1$ qubits. The first $n$ qubits represent the input bit string and the last qubit represents the output. Thus, the oracles are implemented as several multi-controlled X gates where the first $n$ qubits are control qubits controlled on those bit strings that makes the function $f$ output 1. For example, if $f(0010) = 1$, we add a multi-controlled X gate to the circuit where the first 4 qubits are control indices with control values 0, 1, 0, 0.

from numpy.random import choicefrom quri_parts.circuit import QuantumCircuitdef get_dj_oracle(n_bit_length: int, balanced: bool) -> QuantumCircuit:    n_qubits = n_bit_length + 1    if not balanced:        return QuantumCircuit(n_qubits)        flipped = choice(2**n_bit_length, size=2**(n_bit_length-1), replace=False)    circuit = QuantumCircuit(n_qubits)        for f in flipped:        controlled_on = {i: (f >> i) & 1 for i in range(n_bit_length)}        circuit.add_X_gate(n_qubits-1, controlled_on)        return circuit

Here, we show the circuit

from quri_parts.circuit.utils.circuit_drawer import draw_circuitdraw_circuit(get_dj_oracle(n_bit_length=4, balanced=True))
#output                                                                                                                                                0 ----●-------○-------○-------○-------●-------○-------○-------●---          |       |       |       |       |       |       |       |             |       |       |       |       |       |       |       |             |       |       |       |       |       |       |       |       1 ----●-------○-------●-------●-------●-------●-------●-------○---          |       |       |       |       |       |       |       |             |       |       |       |       |       |       |       |             |       |       |       |       |       |       |       |       2 ----○-------○-------○-------●-------●-------○-------●-------●---          |       |       |       |       |       |       |       |             |       |       |       |       |       |       |       |             |       |       |       |       |       |       |       |       3 ----○-------●-------●-------○-------●-------○-------●-------●---          |       |       |       |       |       |       |       |            _|_     _|_     _|_     _|_     _|_     _|_     _|_     _|_          | X |   | X |   | X |   | X |   | X |   | X |   | X |   | X |     4 --|0  |---|1  |---|2  |---|3  |---|4  |---|5  |---|6  |---|7  |-        |___|   |___|   |___|   |___|   |___|   |___|   |___|   |___| 

Let's confirm that the circuit does implement the correct oracle

from quri_parts.core.state import ComputationalBasisStatefrom quri_parts.qulacs.simulator import evaluate_state_to_vectorimport numpy as npimport pandas as pdbit_length = 4n_qubit = bit_length + 1oracle = get_dj_oracle(bit_length, True)function_output_dict = {}for i in range(2**bit_length):    out_vector = evaluate_state_to_vector(        ComputationalBasisState(n_qubit, bits=i).with_gates_applied(oracle)        ).vector    res = np.where(out_vector == 1)[0][0] >> bit_length    function_output_dict[bin(i)[2:].zfill(bit_length)] = resprint(    pd.DataFrame.from_dict(        function_output_dict, orient="index", columns=["function output"]    ).reset_index().rename(columns={"index": "function input"}).sort_values(        "function output"    ).reset_index(drop=True).T.to_markdown())
0123456789101112131415
function input0000010001010110011110001011111100010010001110011010110011011110
function output0000000011111111

We can see here that the oracle indeed implements a balanced function.

## The algorithm​

Now, we implement the Deutsch-Jozsa algorithm that determines whether the function is balanced or not. The circuit is given by the below figure.

def get_algorithm_circuit(oracle: QuantumCircuit) -> QuantumCircuit:    n_qubits = oracle.qubit_count    n_func_arg = oracle.qubit_count - 1    circuit = QuantumCircuit(n_qubits, n_func_arg)        circuit.add_X_gate(n_qubits-1)    for i in range(n_qubits):        circuit.add_H_gate(i)    circuit.extend(oracle)    for i in range(n_func_arg):        circuit.add_H_gate(i)    return circuit

As an example, we demonstrate an oracle of 4 qubits embedded inside the solution algorithm

oracle = get_dj_oracle(3, True)algorithm = get_algorithm_circuit(oracle)draw_circuit(algorithm)
#output         ___                                             ___          | H |                                           | H |     0 --|1  |-------------○-------●-------●-------●-----|9  |-        |___|             |       |       |       |     |___|          ___              |       |       |       |      ___          | H |             |       |       |       |     | H |     1 --|2  |-------------●-------●-------○-------●-----|10 |-        |___|             |       |       |       |     |___|          ___              |       |       |       |      ___          | H |             |       |       |       |     | H |     2 --|3  |-------------●-------○-------●-------●-----|11 |-        |___|             |       |       |       |     |___|          ___     ___     _|_     _|_     _|_     _|_                  | X |   | H |   | X |   | X |   | X |   | X |             3 --|0  |---|4  |---|5  |---|6  |---|7  |---|8  |---------        |___|   |___|   |___|   |___|   |___|   |___|         

Finally, we run the algorithm with a sampler. The algorithm is deterministic, so one shot is enough to determine if the function is balanced or not.

from quri_parts.qulacs.sampler import create_qulacs_vector_samplerfrom quri_parts.core.utils.recording import Recorder, recordablefrom collections import Counter@recordabledef run_algorithm(recorder: Recorder, oracle: QuantumCircuit, n_shots: int=1) -> bool:    """If function is balanced return 1. Otherwise return 0    """    algorithm = get_algorithm_circuit(oracle)    sampler = create_qulacs_vector_sampler()    sampling_count = sampler(algorithm, n_shots)        # pick out the measurement result from the first n qubits.    fnc_arg_cnt = Counter()    filter_str = 2**(oracle.qubit_count-1) - 1    for qubit, cnt in sampling_count.items():        fnc_arg_cnt += Counter({qubit & filter_str: cnt})    recorder.info("sampling count", fnc_arg_cnt)    is_balanced = 0 not in fnc_arg_cnt    return is_balanced

We first run the algorithm with an oracle that implements a constant function.

In the Deutsch-Jozsa algorithm, the measured outcome of the first $n$ qubits should all be zero.

from quri_parts.core.utils.recording import INFO, RecordSessionimport matplotlib.pyplot as pltimport seaborn as snsimport pandas as pdsession_constant = RecordSession()session_constant.set_level(INFO, run_algorithm)with session_constant.start():    oracle = get_dj_oracle(4, balanced=False)    print("is balanced:", run_algorithm(oracle, 1000))constant_group, = session_constant.get_records().get_history(run_algorithm)ax = sns.barplot(    pd.DataFrame.from_dict(        constant_group.entries[0].data[1], orient='index', columns=["count"]    ).T)ax.set(    xlabel = "Measurement result of the first 4 qubits",    ylabel = "Count",    title = "Statistics")plt.show()
#output    is balanced: False

Finally, we run the algorithm with an oracle that implements a balanced function.

session_balanced = RecordSession()session_balanced.set_level(INFO, run_algorithm)with session_balanced.start():    oracle = get_dj_oracle(4, balanced=True)    print("is balanced:", run_algorithm(oracle, 1000))balanced_group, = session_balanced.get_records().get_history(run_algorithm)table = pd.DataFrame.from_dict(    balanced_group.entries[0].data[1], orient='index', columns=["count"]).Ttable.columns = list(map(lambda x: bin(x)[2:].zfill(4), table.columns))ax = sns.barplot(table)ax.set(    xlabel = "Measurement result of the first 4 qubits",    ylabel = "Count",    title = "Statistics")plt.show()
#output    is balanced: True