Deutsch-Jozsa-algoritmus

Magyar

Kiejtés

• IPA: [ ˈdɛut͡ʃhjoʒɒɒlɡoritmuʃ]

Főnév

Deutsch-Jozsa-algoritmus

1. (matematika)

Deutsch–Jozsa-algoritmus

A **Deutsch–Jozsa-algoritmus** az egyik első kvantumalgoritmus, amely megmutatta, hogy a kvantumszámítógépek bizonyos problémákat gyorsabban tudnak megoldani, mint a klasszikus számítógépek. A problémája egy adott $f(x)$ függvény tulajdonságainak meghatározása a lehető legkevesebb lekérdezéssel.

Probléma

Adott egy $f(x)$ függvény, amely $\{0,1\}^{n}\to \{0,1\}$ leképezést végez. A függvény:

1. **Konstans**, ha minden bemenethez ugyanazt az értéket adja (vagy mindig 0, vagy mindig 1).
2. **Kiegyensúlyozott**, ha a kimenetek fele 0, fele pedig 1.

Cél: Meg kell állapítani, hogy $f(x)$ konstans vagy kiegyensúlyozott.

Klasszikus algoritmus

A klasszikus algoritmusnak a legrosszabb esetben $2^{n-1}+1$ lekérdezésre van szüksége:

• El kell kérnie több bemenetet, és összehasonlítania kell a kimeneteket.

Kvantumos algoritmus

A Deutsch–Jozsa-algoritmus kvantumszámítógépen garantáltan egyetlen függvényértékeléssel meg tudja oldani a problémát.

Kvantumos működés

1. Regiszterek inicializálása:

  * Egy $n$-qubites bemeneti regiszter $|0\rangle ^{\otimes n}$.
  * Egy további qubit ($|1\rangle$) a függvényérték tárolására.

1. Hadamard transzformáció alkalmazása:

  * Az összes qubit Hadamard-transzformációja (Hadamard kapu) szuperpozícióba helyezi az állapotot:
    $$H^{\otimes n}|0\rangle ={\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}|x\rangle$$

1. Függvény ($U_{f}$) alkalmazása:

  * A kvantum kapu formájában megvalósított $f(x)$ módosítja a qubit állapotát:
    $$|x\rangle |y\rangle \to |x\rangle |y\oplus f(x)\rangle$$

1. Mérés előkészítése:

  * A második regiszteren újabb Hadamard-transzformáció.

1. Mérés:

  * Ha az első regiszter minden qubitje $|0\rangle$, akkor $f(x)$ konstans.
  * Egyébként $f(x)$ kiegyensúlyozott.

Matematikai részletek

A kvantumállapot az alábbi lépéseken megy keresztül:

1. Inicializálás:

  $$|0\rangle ^{\otimes n}\otimes |1\rangle$$

1. Hadamard alkalmazása:

  $$H^{\otimes n+1}\left(|0\rangle ^{\otimes n}\otimes |1\rangle \right)={\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}|x\rangle \otimes {\frac {|0\rangle -|1\rangle }{\sqrt {2}}}$$

1. Függvény kiértékelése:

  $${\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}|x\rangle \otimes {\frac {|0\oplus f(x)\rangle -|1\oplus f(x)\rangle }{\sqrt {2}}}$$

1. Kimeneti regiszter redukciója:

  A függvény hatása szuperpozícióba helyezi az eredményt, és az első regiszterben maradt interferencia határozza meg a konstans vagy kiegyensúlyozott tulajdonságot.

Python implementáció (Qiskit)

from qiskit import QuantumCircuit, Aer, execute

def deutsch_jozsa(is_balanced=True):
    n = 1  # Egy qubites függvény
    qc = QuantumCircuit(n + 1, n)

    # Inicializálás
    qc.x(n)  # Második regiszter állapota: |1⟩
    qc.h(range(n + 1))  # Hadamard minden qubiten

    # Fekete doboz függvény implementálása
    if is_balanced:
        qc.cx(0, 1)  # Kiegyensúlyozott
    else:
        pass  # Konstans (nem történik változtatás)

    # Hadamard az első regiszteren
    qc.h(range(n))

    # Mérés
    qc.measure(range(n), range(n))

    # Szimuláció
    simulator = Aer.get_backend('qasm_simulator')
    result = execute(qc, backend=simulator, shots=1).result()
    counts = result.get_counts()

    # Eredmény kiértékelése
    return "Balanced" if '1' in counts else "Constant"

# Példa futtatása
print(deutsch_jozsa(is_balanced=True))  # "Balanced"
print(deutsch_jozsa(is_balanced=False))  # "Constant"

Eredmény

• **Konstans függvény esetén**:

 Az első regiszter minden qubitje $|0\rangle$ lesz.

• **Kiegyensúlyozott függvény esetén**:

 Az első regiszterben legalább egy qubit $|1\rangle$-t eredményez.

Előnyök

1. **Gyorsabb, mint a klasszikus algoritmus**:

  * Egyetlen függvényértékeléssel dönthető el a függvény tulajdonsága.

1. **Egyszerű kvantumos működés**:

  * Demonstrálja a kvantumalgoritmusok előnyét.

Hátrányok

1. **Speciális probléma**:

  * Csak a konstans/kiegyensúlyozott tulajdonságra korlátozódik.

1. **Nem skálázható általános problémákra**:

  * Nagyobb, gyakorlati problémákhoz nem használható.

Összefoglalás

A **Deutsch–Jozsa-algoritmus** az első kvantumalgoritmusok egyike, amely megmutatja a kvantumszámítógépek erejét. Bár gyakorlati alkalmazása korlátozott, kiváló példája annak, hogy a kvantummechanikai tulajdonságok hogyan gyorsíthatják fel bizonyos számításokat.

Fordítások

Tartalom

angol: Deutsch–Jozsa algorithm (en)

További információk

• Deutsch-Jozsa-algoritmus - Értelmező szótár (MEK)
• Deutsch-Jozsa-algoritmus - Etimológiai szótár (UMIL)
• Deutsch-Jozsa-algoritmus - Szótár.net (hu-hu)
• Deutsch-Jozsa-algoritmus - DeepL (hu-de)
• Deutsch-Jozsa-algoritmus - Яндекс (hu-ru)
• Deutsch-Jozsa-algoritmus - Google (hu-en)
• Deutsch-Jozsa-algoritmus - Helyesírási szótár (MTA)
• Deutsch-Jozsa-algoritmus - Wikidata
• Deutsch-Jozsa-algoritmus - Wikipédia (magyar)