Skrytý problém lineární funkce - Hidden linear function problem

The skrytý problém lineární funkce, je problém s hledáním který zobecňuje Bernstein – Vazirani problém.^[1] V problému Bernstein – Vazirani je skrytá funkce implicitně specifikována v věštec; zatímco v 2D skrytý problém lineární funkce (2D HLF), skrytá funkce je výslovně specifikována maticí a binárním vektorem. 2D HLF lze vyřešit přesně pomocí konstantní hloubky kvantový obvod omezeno na 2-dimenzionální mřížku qubits pomocí omezeného fan-in brány, ale nelze je vyřešit žádnou subexponenciální velikostí, klasickým obvodem s konstantní hloubkou pomocí neomezeného fan-inu A, NEBO, a NE brány.^[2]Zatímco Bernstein – Vaziraniho problém byl navržen tak, aby prokázal věštecké oddělení mezi nimi třídy složitosti BQP a BPP „2D HLF byl navržen tak, aby prokázal explicitní oddělení mezi třídami obvodů ${ displaystyle QNC ^ {0}}$ a ${ displaystyle NC ^ {0}}$ (${ displaystyle QNC ^ {0} nsubseteq NC ^ {0}}$).^[1]

Prohlášení o problému 2D HLF

Dáno ${ displaystyle A in mathbb {F} _ {2} ^ {n krát n}}$(horní trojúhelníkový binární matice velikosti ${ displaystyle n krát n}$) a ${ displaystyle b in mathbb {F} _ {2} ^ {n}}$ (A binární vektor délky ${ displaystyle n}$),

definovat funkci ${ displaystyle q: mathbb {F} _ {2} ^ {n} to mathbb {Z} _ {4}}$:

${ displaystyle q (x) = (2x ^ {T} Axe + b ^ {T} x) { bmod {4}} = left (2 sum _ {i, j} A_ {i, j} x_ {i} x_ {j} + sum _ {i} b_ {i} x_ {i} right) { bmod {4}},}$

a

${ displaystyle { mathcal {L}} _ {q} = { Big {} x in mathbb {F} _ {2} ^ {n}: q (x oplus y) = (q (x ) + q (y)) { bmod {4}} ~~ pro všechny y in mathbb {F} _ {2} ^ {n} { Big }}.}$

Existuje a ${ displaystyle z in mathbb {F} _ {2} ^ {n}}$ takhle

${ displaystyle q (x) = 2z ^ {T} x ~~ na všech x in { mathcal {L}} _ {q}.}$

Nalézt ${ displaystyle z}$.^[1]

Algoritmus 2D HLF

Se 3 registry; první hospodářství hospodářství ${ displaystyle A}$, druhý obsahující ${ displaystyle b}$ a třetí nesoucí ${ displaystyle n}$- qubitový stav, obvod má řízené brány které implementují ${ displaystyle U_ {q} = prod _ {1$ z prvních dvou registrů do třetího.

Tento problém lze vyřešit kvantovým obvodem, ${ displaystyle H ^ { otimes n} U_ {q} H ^ { otimes n} mid 0 ^ {n} rangle}$, kde H je Hadamardova brána, S je S brána a CZ je CZ brána. Je to řešeno tímto obvodem, protože s ${ displaystyle p (z) = left | langle z | H ^ { otimes n} U_ {q} H ^ { otimes n} | 0 ^ {n} rangle right | ^ {2}}$, ${ displaystyle p (z)> 0}$ iff ${ displaystyle z}$ je řešení.^[1]

Reference

externí odkazy

• Implementace problému skryté lineární funkce