Technische Samenvatting: Kwantumtoestandsvoorbereiding met Optimale T-count

Probleemstelling

Het artikel behandelt de fundamentele vraag naar het kwantificeren van de "magie" (niet-Cliffordheid) die vereist is voor het implementeren van willekeurige kwantumtoestanden en operaties in fouttolerante kwantumcomputers. Specifiek onderzoekt het de minimale hoeveelheid $T$-poorten (de $T$-count) die nodig is om een willekeurige $n$-qubit kwantumtoestand of een willekeurige diagonale $n$-qubit unitaire operatie $\varepsilon$-benaderend te implementeren binnen een fout $\varepsilon$ in de $\ell_2$-norm (voor toestanden) of de operatornorm (voor unitaire operaties).

Vorig werk door Low, Kliuchnikov en Schaeffer (LKS) stelde een bovengrens vast van $O(\sqrt{2^n n \log(n/\varepsilon)} + \log^2(n/\varepsilon))$ voor toestandsvoorbereiding met behulp van ancilla-qubits. De auteurs zoeken naar een manier om te bepalen of deze schaling optimaal is, of dat de overheads gerelateerd aan het aantal qubits $n$ en de foutafhankelijkheid $\log(n/\varepsilon)$ kunnen worden verminderd.

Methodologie

Het artikel maakt gebruik van een combinatie van constructieve synthesealgoritmen en informatietheoretische ondergrenzen.

1. Diagonale Unitaire Synthese

De kern van de technische innovatie is een nieuwe methode voor het synthetiseren van diagonale unitaire operaties. De auteurs beschouwen een $n$-qubit diagonale unitaire operatie $D$ als een enkele-qubit unitaire operatie $G_y$ die wordt aangestuurd door $n-1$ qubits.

• Benadering: Elke enkele-qubit unitaire operatie $G_y$ wordt benaderd door een sequentie van $O(\log(1/\varepsilon))$ Hadamard- en $T$-poorten (met behulp van bestaande optimale enkele-qubit synthesetechnieken zoals Ross-Selinger).
• Oracle Implementatie: Een Booleaanse oracle $B$ wordt geconstrueerd om de beschrijving van deze poortsequentie (een bitreeks $s_y$) te berekenen op basis van de controlebits $y$. Deze oracle wordt geïmplementeerd met de LKS-techniek voor Booleaanse functies, wat een $T$-count bereikt van $O(\sqrt{2^n \log(1/\varepsilon)})$.
• Gecontroleerde Toepassing: De eigenlijke poorten worden toegepast op de doel-qubit, aangestuurd door de bits van de berekende reeks $s_y$. Deze stap brengt een kostenpost met zich mee die proportioneel is aan de lengte van $s_y$, oftewel $O(\log(1/\varepsilon))$.
• Uncomputation: De oracle wordt ongedaan gemaakt (uncomputed) om de ancilla's terug te brengen naar de nul-toestand.

2. Kwantumtoestandsvoorbereiding

Het algoritme voor toestandsvoorbereiding verfijnt de Grover-Rudolph methode en de LKS-constructie:

• Grof Benadering: In plaats van de standaard Grover-Rudolph aanpak die $O(n)$ gecontroleerde rotaties vereist, gebruiken de auteurs een variant van recente methoden (Rosenthal, INN+22) om het probleem te reduceren tot het synthetiseren van slechts $O(1)$ diagonale unitaire operaties. Ze construeren een toestand $|\phi\rangle$ met een constante overlap met de doeltoestand $|\psi\rangle$ met behulp van twee Booleaanse diagonale unitaire operaties ($B_1, B_2$) en Hadamard-lagen.
• Iteratieve Verfijning: Om de fout van een constante naar $\varepsilon$ te verminderen, gebruiken de auteurs een iteratieve aanpak. Ze benaderen de verschiltoestand $|\psi\rangle - |\phi\rangle$ met dezelfde grove benaderingstechniek. Dit genereert een reeks toestanden $|\phi_k\rangle$.
• Lineaire Combinatie van Unitaire Operaties (LCU): De uiteindelijke toestand wordt voorbereid als een gewogen som van deze grove benaderingen met behulp van de LCU-methode.
• Amplitude Amplificatie: Exacte amplitude-amplificatie wordt gebruikt om de "junk"-componenten uit de superpositie te filteren, waardoor de uiteindelijke toestand $\varepsilon$-nabij de doeltoestand wordt. Dit vereist het afstemmen van de amplitude van de "geflagde" toestand naar een specifieke waarde ($\sin(\pi/10)$) om exacte amplificatie in een constant aantal rondes mogelijk te maken.

3. Ondergrenzen

De ondergrenzen worden vastgesteld in een sterk model van adaptieve Clifford+T circuits, wat mid-circuit metingen en klassieke feed-forward toestaat.

• Reductie naar Toestandsvoorbereiding: Voor unitaire synthese wordt het probleem gereduceerd tot toestandsvoorbereiding door de werking van het circuit op een maximaal verstrengelde toestand (Choi-toestand) te overwegen.
• Telling-argument: De auteurs gebruiken een sfeerverpakking-argument. Ze tonen aan dat het aantal onderscheidbare toestanden (of unitaire operaties) binnen fout $\varepsilon$ schaalt als $(1/\varepsilon)^{\Theta(2^n)}$.
• Canonieke Vorm: Ze maken gebruik van een canonieke vorm voor Clifford-circuits met Pauli postselecties (als generalisatie van het werk van Beverland et al.) om het aantal unieke circuits te beperken die bereikbaar zijn met een gegeven $T$-count $t$. Door het aantal beschikbare circuits gelijk te stellen aan het aantal onderscheidbare doelwitten, leiden ze de ondergrens $t = \Omega(\sqrt{2^n \log(1/\varepsilon)} + \log(1/\varepsilon))$ af.

Belangrijkste Bijdragen en Resultaten

Hoofdtheorema's

1. Optimale Toestandsvoorbereiding (Theorema 1.1):
   Elke $n$-qubit toestand kan worden voorbereid tot fout $\varepsilon$ met een Clifford+T circuit met een $T$-count van:
   $$\Theta\left(\sqrt{2^n \log(1/\varepsilon)} + \log(1/\varepsilon)\right)$$
   Deze grens is optimaal, zelfs in het adaptieve model met metingen.

2. Optimale Diagonale Unitaire Synthese (Theorema 1.2):
   Elke diagonale unitaire operatie op $n$ qubits kan worden geïmplementeerd tot fout $\varepsilon$ met dezelfde optimale $T$-count:
   $$\Theta\left(\sqrt{2^n \log(1/\varepsilon)} + \log(1/\varepsilon)\right)$$

3. Gebundelde Synthese (Theorema 1.3):
   Een tensorproduct van $m = O(\log \log(1/\varepsilon))$ enkele-qubit unitaire operaties kan worden geïmplementeerd met een $T$-count van $O(\log(1/\varepsilon))$. Dit impliceert dat het synthetiseren van een klein aantal unitaire operaties de asymptotische kosten niet verhoogt boven de kosten van een enkele unitaire operatie.

4. Massaproductie (Theorema 1.4):
   Het implementeren van $m$ kopieën van een enkele-qubit unitaire operatie $U^{\otimes m}$ vereist een $T$-count van $O(m + \log(1/\varepsilon))$. Dit is optimaal en verbetert eerdere strategieën die een $\log(m)$ factor met zich meebrachten.

Verbeteringen t.o.v. Vorig Werk

• Het artikel verwijdert de $O(\sqrt{n})$ en $O(\log n)$ overheads die aanwezig waren in de LKS-toestandsvoorbereidingsgrens, en bereikt daarmee de informatie-theoretische ondergrens.
• De $T$-count voor diagonale unitaire operaties is verbeterd van $O(\sqrt{2^n} \log(n/\varepsilon))$ naar $O(\sqrt{2^n \log(1/\varepsilon)})$.

Betekenis en Claims

De auteurs beweren dat zij de worst-case $T$-count voor kwantumtoestandsvoorbereiding en diagonale unitaire synthese hebben gekarakteriseerd, waarbij zij hebben vastgesteld dat de eerder bekende bovengrenzen niet nauwkeurig waren vanwege onnodige overheads.

• Optimaliteit: De resultaten vormen het "beste van beide werelden", waarbij een bovengrens wordt geboden in het zwakke (unitaire) model en een overeenkomende ondergrens in het sterke (adaptieve) model.
• Resource Trade-offs: De constructie bereikt bijna optimale trade-offs tussen het aantal ancilla-qubits en de $T$-count, hoewel de exacte optimale trade-off nog een open vraag blijft.
• Applicaties: De verbeterde grenzen leiden tot lichte verbeteringen in de ondergrenzen voor de stabilizer rank van magic states en de decompositie van Booleaanse functies. Het resultaat over "massaproductie" wordt benadrukt als een specifieke toepassing waarbij het synthetiseren van identieke unitaire operaties aanzienlijk goedkoper is dan het synthetiseren van verschillende unitaire operaties.

Het artikel merkt expliciet op dat hoewel de $T$-count nu optimaal is, het aantal Clifford-poorten $O(2^n \log(1/\varepsilon))$ blijft, wat dicht bij de optimale $\Omega(2^n/n)$ ligt maar nog niet is gematcht. Voorts blijft de optimale $T$-count voor algemene (niet-diagonale) $n$-qubit unitaire operaties een open probleem, met een kloof tussen de ondergrens $\tilde{\Omega}(2^n)$ en de beste bekende bovengrens $\tilde{O}(2^{1.5n})$.