← Quantum Store · Guides · Lessons · Glossary · Packages · About · Türkçe

Quantum Store editors

First quantum algorithms: Deutsch-Jozsa and Bernstein-Vazirani

The first two algorithms in which a quantum computer beats a classical one, Deutsch-Jozsa and Bernstein-Vazirani, which solve a black-box function with a single query. Tested with Qiskit, explained step by step.

Who is this package for?

For anyone who knows the qubit, the H gate and the CNOT and wants to see the first concrete answer to the question "what does a quantum computer actually do faster?". If you have tried the "Interference" examples in the site's in-browser playground, you are ready.

The black box (oracle) idea

Both algorithms involve a function whose inside we cannot see: a black box. We can give it an input and get its answer. The question is: in how many queries can we work out the box's secret?

Deutsch-Jozsa

The box is either a constant function (the same answer for every input) or a balanced one (0 for half the inputs, 1 for the other half). For 3-bit inputs a classical approach needs 5 queries in the worst case. The quantum circuit asks about all inputs at once in superposition and, thanks to interference, decides with a single query:

• If the measurement is 000, the box is constant.
• Any other result means it is balanced.

Bernstein-Vazirani

The box hides a secret bit string s inside f(x) = s·x (mod 2). Classically each bit needs a separate query (4 bits, 4 queries). The quantum circuit gives the secret string in a single query, directly as the measurement result. In the example the string 1011 was found in 500 out of 500 measurements.

Why do these examples matter?

They are not practically useful problems. But they show, in the simplest form, how superposition and interference together give a speed-up. Grover's and Shor's algorithms are built on the same idea.

Next steps

1. Change the GIZLI (secret) variable to hide a different string.
2. Write your own balanced function (for example qc.cx(1, N)) and see the algorithm catch it too.
3. Then move on to the "Factor 15 with Shor's algorithm" package.

Installation and running

pip install qiskit
python ilk_algoritmalar.py

Tested with: qiskit 2.5.2, Python 3.12.

Links

• Deutsch-Jozsa paper (1992)
• Qiskit documentation

Package contents

• ilk_algoritmalar.py
• README.en.md — this file
• README.md — the same guide in Turkish
• LICENSE — the licence of the files in this package
• KAYNAK.json — a machine-readable summary of the official source

Licence

This package was prepared by the Quantum Store editors and is distributed under the MIT licence.

Quantum Store — https://hakanerdogan.com/en

Example code

The example shipped in the package, run and checked. Comments and printed messages are in Turkish; the code is the same in any language. Everything is in the ZIP.

ilk_algoritmalar.py

"""İlk kuantum algoritmaları: Deutsch-Jozsa ve Bernstein-Vazirani (Qiskit).

Çalıştırma:
    pip install qiskit
    python ilk_algoritmalar.py
"""

from qiskit import QuantumCircuit
from qiskit.primitives import StatevectorSampler

sampler = StatevectorSampler(seed=7)


def olc(qc: QuantumCircuit) -> dict[str, int]:
    return dict(sorted(sampler.run([qc], shots=500).result()[0].data.c.get_counts().items()))


# --- Deutsch-Jozsa -----------------------------------------------------------
# Kara kutu bir f(x) fonksiyonu ya "sabit" (her girdiye aynı cevap) ya da
# "dengeli" (girdilerin yarısına 0, yarısına 1). Klasik olarak en kötü durumda
# 2**(n-1)+1 kez sormak gerekir; kuantum devre tek sorguda karar verir.
N = 3


def deutsch_jozsa(oracle) -> dict[str, int]:
    qc = QuantumCircuit(N + 1, N)
    qc.x(N)
    qc.h(range(N + 1))
    oracle(qc)
    qc.h(range(N))
    qc.measure(range(N), range(N))
    return olc(qc)


def sabit_1(qc: QuantumCircuit) -> None:
    qc.x(N)  # f(x) = 1, girdiden bağımsız


def dengeli(qc: QuantumCircuit) -> None:
    qc.cx(0, N)  # f(x) = x0 XOR x2: girdilerin tam yarısında 1
    qc.cx(2, N)


for ad, oracle in [("sabit", sabit_1), ("dengeli", dengeli)]:
    sayim = deutsch_jozsa(oracle)
    karar = "sabit" if set(sayim) == {"0" * N} else "dengeli"
    print(f"Deutsch-Jozsa, {ad:7s} kara kutu → ölçüm {sayim} → karar: {karar}")
    assert karar == ad, sayim

# --- Bernstein-Vazirani -------------------------------------------------------
# Kara kutu f(x) = s·x (mod 2) içinde gizli bir bit dizisi s saklıyor.
# Klasik olarak her bit için bir sorgu (n sorgu) gerekir; kuantumda tek sorgu yeter.
GIZLI = "1011"
n = len(GIZLI)
qc = QuantumCircuit(n + 1, n)
qc.x(n)
qc.h(range(n + 1))
for i, bit in enumerate(reversed(GIZLI)):  # Qiskit'te sağdaki bit 0. kübittir.
    if bit == "1":
        qc.cx(i, n)
qc.h(range(n))
qc.measure(range(n), range(n))
print(qc.draw(output="text"))
sayim = olc(qc)
print(f"Bernstein-Vazirani: gizli dizi {GIZLI}, tek sorguda ölçülen {sayim}")
assert sayim == {GIZLI: 500}, sayim
print("Tamam: iki algoritma da kara kutuyu tek sorguda çözdü.")

Related concepts

• Quantum interference · Quantum interference is the way amplitudes add up like waves, raising the probability of some results and cancelling others to zero.
• Grover’s algorithm · Grover’s algorithm finds a marked item among N unsorted items in about √N steps, a quadratic speed-up over classical search.
• Deutsch–Jozsa algorithm · The Deutsch–Jozsa algorithm is one of the first quantum algorithms: it decides with certainty, in a single query, whether a function is constant or balanced.
• Bernstein–Vazirani algorithm · The Bernstein–Vazirani algorithm finds the hidden bit string s inside a function f(x) = s·x in a single query, instead of the n queries needed classically.

← All packages

Share: X · LinkedIn