Deutsch-Jozsa-algoritmus

• IPA:

Deutsch-Jozsa-algoritmus

1. (matematika)

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 ${\displaystyle f(x)}$ függvény tulajdonságainak meghatározása a lehető legkevesebb lekérdezéssel.

Adott egy ${\displaystyle f(x)}$ függvény, amely ${\displaystyle \{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 ${\displaystyle f(x)}$ konstans vagy kiegyensúlyozott.

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

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

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.

1. Regiszterek inicializálása:

  * Egy ${\displaystyle n}$-qubites bemeneti regiszter ${\displaystyle |0\rangle ^{\otimes n}}$.
  * Egy további qubit (${\displaystyle |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:
    $${\displaystyle H^{\otimes n}|0\rangle ={\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}|x\rangle }$$

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

  * A kvantum kapu formájában megvalósított ${\displaystyle f(x)}$ módosítja a qubit állapotát:
    $${\displaystyle |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 ${\displaystyle |0\rangle }$, akkor ${\displaystyle f(x)}$ konstans.
  * Egyébként ${\displaystyle f(x)}$ kiegyensúlyozott.

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

1. Inicializálás:

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

1. Hadamard alkalmazása:

  $${\displaystyle 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:

  $${\displaystyle {\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.

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"

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

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

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

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

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.

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ó.

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.

• 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)