Complexity-06 — Déquantifier les suprématies

# Parameters
BATCH_MODE = "true"

Navigation : Index | 05b — La permanente, frontière quantique

Gottesman–Knill comme arbitre exécutable (Aaronson–Gottesman, 2004)

0. Pourquoi ce notebook

Ce notebook est le sixième de la série (01 — Compter des pas, 02 — Vérifier ou trouver, 03 — Plus de temps, plus de problèmes, 03b — Hartmanis–Stearns, 04b — conjectures online, 05b — Aaronson–Arkhipov) : un texte fondateur, fait tourner. Le geste propre à cette veine est que la thèse s’exécute. Quand une « suprématie quantique » est annoncée, la question qui installe ou réfute la claim n’est pas « est-ce quantique ? » mais « dans quelle classe de circuits ? ». Gottesman–Knill (1998) : tout circuit de portes de Clifford (\(H\), \(S\), \(\mathsf{CNOT}\), mesures) se simule en temps polynomial classique — l’avantage quantique ne peut pas vivre là. Aaronson–Gottesman (2004) en donnent l’organe : l’algorithme CHP, \(O(n^2)\) par porte sur un tableau de bits, sans jamais écrire une amplitude. Nous allons donc :

  1. exécuter le formalisme stabilisateur : le tableau de Pauli d’Aaronson–Gottesman, avec sa table de phase et ses règles de conjugaison dérivées des matrices \(2\times2\) — jamais recopiées d’une table magique ;
  2. construire les deux machines : l’arbitre polynomial (port CHP) et l’état complet \(2^n\), puis les croiser sur des circuits Clifford aléatoires — les valeurs propres du groupe stabilisateur, calculées indépendamment par les deux machines, doivent coïncider exactement ; le simulateur de référence du métier (stim, Gidney 2021) sert de troisième juge quand il est installé ;
  3. mesurer le régime, pas l’objet : à circuits Clifford purs, l’écart de coût entre l’état complet et l’arbitre double à chaque qubit ; une seule porte \(T\) ferme l’arbitre — et ferme aussi stim. La suprématie est une assertion sur un régime, pas sur un objet : c’est la leçon de méthode que ce banc rend mesurable.

L’encart de cadrage, sans mesure : les épisodes contemporains de réfutation de claims de suprématie (RCS, GBS) relèvent ici exactement de la leçon de méthode — comment on réfute proprement, en exhibant le régime où la claim casse. Ce notebook ne prend parti pour aucun verdict : il mesure deux régimes sur des instances bornées, et chacun peut réexécuter le banc.

import math
import time

import numpy as np

np.set_printoptions(precision=4, suppress=True)

# Toutes les experiences sont seedees : reexecuter redonne les memes nombres.
# Les chronometres sont des medianes sur 3 seeds (machine partagee, cf. §4).
GLOBAL_SEEDS = (0, 1, 7)

1. Le formalisme stabilisateur, définition exécutée

Un état stabilisateur est l’unique vecteur propre \(+1\) commun de \(n\) chaînes de Pauli indépendantes qui commutent — ses stabilisateurs. Aaronson–Gottesman stockent le groupe étendu : \(n\) déstabilisateurs (les partenaires qui complètent la base symplectique) plus \(n\) stabilisateurs, chacun encodé en bits par qubit — \(I=(0,0)\), \(X=(1,0)\), \(Z=(0,1)\), \(Y=(1,1)\), le \(Y\) portant les deux bits puisque \(Y = iXZ\) — plus un bit de signe \(r\) par ligne et une ligne de travail.

Tout ce qui suit manipule des lignes de bits : aucune amplitude, aucun nombre complexe hors les matrices \(2\times2\) qui servent à prouver les tables. C’est la promesse polynomialiste de Gottesman–Knill, rendue littérale.

MATRICES = {
    "I": np.eye(2, dtype=complex),
    "X": np.array([[0, 1], [1, 0]], dtype=complex),
    "Z": np.array([[1, 0], [0, -1]], dtype=complex),
    "Y": np.array([[0, -1j], [1j, 0]], dtype=complex),
}
LETTERS = ("I", "X", "Y", "Z")
BITS = {"I": (0, 0), "X": (1, 0), "Z": (0, 1), "Y": (1, 1)}


def derive_phase_table():
    """Table e telle que P1 @ P2 = (i**e) * P3, construite en multipliant les
    matrices 2x2 et en identifiant le produit dans la base {i**k * P}.

    Aucune valeur n'est ecrite a la main : la table se prouve par construction.
    """
    table = np.zeros((4, 4), dtype=np.int8)
    for i1, p1 in enumerate(LETTERS):
        for i2, p2 in enumerate(LETTERS):
            produit = MATRICES[p1] @ MATRICES[p2]
            for k in range(4):
                for i3, p3 in enumerate(LETTERS):
                    if np.allclose(produit, (1j ** k) * MATRICES[p3]):
                        table[i1, i2] = k
    return table


E_TABLE = derive_phase_table()

# Verifications structurelles (elles echouent brutalement si la derivation depaille)
assert (np.diag(E_TABLE) == 0).all()          # P @ P = +I pour les Pauli hermitiens
for _i1 in range(4):                          # antisymetrie : e(P2,P1) = -e(P1,P2) mod 4
    for _i2 in range(4):
        assert E_TABLE[_i2, _i1] == (-E_TABLE[_i1, _i2]) % 4
assert (E_TABLE[0] == 0).all() and (E_TABLE[:, 0] == 0).all()  # identite neutre

print("Table de phase e(P1, P2) derivee des matrices (P1 lignes, P2 colonnes, I X Y Z) :")
print(E_TABLE)
cycle = [("X", "Y"), ("Y", "Z"), ("Z", "X")]
inverse = [(b, a) for a, b in cycle]
_idx = {p: i for i, p in enumerate(LETTERS)}
print("e = 1 le long du cycle  X.Y, Y.Z, Z.X :",
      [int(E_TABLE[_idx[a], _idx[b]]) for a, b in cycle])
print("e = 3 a contre-courant  Y.X, Z.Y, X.Z :",
      [int(E_TABLE[_idx[a], _idx[b]]) for a, b in inverse])

# Bits (x, z) -> index Pauli dans l'ordre (I, X, Y, Z) de la table
_BIT_TO_INDEX = np.array([[0, 3], [1, 2]], dtype=np.int8)


def _pauli_letter(x, z):
    return {(0, 0): "I", (1, 0): "X", (0, 1): "Z", (1, 1): "Y"}[(int(x), int(z))]


def _row_string(xs, zs, r):
    return ("+" if r == 0 else "-") + "".join(
        _pauli_letter(x, z) for x, z in zip(xs, zs)
    )
Table de phase e(P1, P2) derivee des matrices (P1 lignes, P2 colonnes, I X Y Z) :
[[0 0 0 0]
 [0 0 1 3]
 [0 3 0 1]
 [0 1 3 0]]
e = 1 le long du cycle  X.Y, Y.Z, Z.X : [1, 1, 1]
e = 3 a contre-courant  Y.X, Z.Y, X.Z : [3, 3, 3]

Lecture. La table n’est pas symétrique : \(X \cdot Y = iZ\) mais \(Y \cdot X = -iZ\). Suivre le cycle \(X \to Y \to Z \to X\) coûte un facteur \(i\) (\(e = 1\)) ; le remonter en rend un (\(e = 3\)). Cette asymétrie est tout ce que la mécanique quantique ajoute au calcul sur bits : le simulateur Clifford la trackera en un seul bit par ligne (\(\sum_j e_j / 2 \bmod 2\)), pas en amplitudes complexes.

2. Les règles de conjugaison, dérivées elles aussi

La second endroit où se tromper en silence : l’action des portes sur les lignes du tableau. \(H\) conjugue \(X \leftrightarrow Z\) (et change le signe d’un \(Y\)), \(S\) conjugue \(X \to Y\) (et change le signe d’un \(Y\)), et le \(\mathsf{CNOT}\) suit deux xors — plus un piège de phase que l’on dérive au lieu de le croire : la table complète des 16 conjugués \(\mathsf{CNOT}\,P\,\mathsf{CNOT}^\dagger\) sur la paire (contrôle, cible), calculée matriciellement.

CNOT_MAT = np.array(
    [[1, 0, 0, 0],
     [0, 1, 0, 0],
     [0, 0, 0, 1],
     [0, 0, 1, 0]], dtype=complex)  # base |c t>, controle = bit fort


def derive_cnot_rules():
    """Les 16 conjugués CNOT P CNOT, identifies par multiplication matricielle.

    Retourne la liste (P, signe, P') telle que CNOT P CNOT = signe * P'.
    """
    rules = {}
    for p1 in LETTERS[1:]:
        for p2 in LETTERS[1:]:
            P = np.kron(MATRICES[p1], MATRICES[p2])
            M = CNOT_MAT @ P @ CNOT_MAT
            for signe in (1, -1):
                for q1 in LETTERS[1:]:
                    for q2 in LETTERS[1:]:
                        if np.allclose(M, signe * np.kron(MATRICES[q1], MATRICES[q2])):
                            rules[(p1, p2)] = (signe, q1, q2)
    return rules


CNOT_RULES = derive_cnot_rules()
print("Conjugaison CNOT (controle, cible) derivee des matrices :")
negatifs = []
for (p1, p2), (signe, q1, q2) in CNOT_RULES.items():
    marque = "" if signe > 0 else "   <-- signe -"
    print(f"  {p1}{p2} -> {'+' if signe > 0 else '-'}{q1}{q2}{marque}")
    if signe < 0:
        negatifs.append((p1, p2))
print("Seuls cas a signe - :", negatifs)
Conjugaison CNOT (controle, cible) derivee des matrices :
  XY -> +YZ
  XZ -> -YY   <-- signe -
  YY -> -XZ   <-- signe -
  YZ -> +XY
  ZX -> +ZX
Seuls cas a signe - : [('X', 'Z'), ('Y', 'Y')]

Lecture. Les deux xors (\(x_t \leftarrow x_t \oplus x_c\) puis \(z_c \leftarrow z_c \oplus z_t\)) reproduisent les lettres des 16 conjugués. Le signe \(-\) n’apparaît que pour \(X_c Z_t\) et \(Y_c Y_t\) — soit, en bits, exactement \(x_c = 1\), \(z_t = 1\) et \(z_c = x_t\) (les bits lus avant les xors). Tout le reste du notebook applique ces règles prouvées : la seule constante de phase du formalisme est dérivée, aucune n’est recopiée.

3. L’organe : le simulateur CHP, complet

Trois pièces dans l’algorithme d’Aaronson–Gottesman :

  1. rowsum(h, i) — additionner la ligne \(i\) dans la ligne \(h\) : Pauli xorés, phase accumulée par la table dérivée ci-dessus, \(r_h \leftarrow r_i \oplus r_h \oplus (\tfrac{1}{2}\sum_j e_j \bmod 2)\). Pour deux lignes qui commutent (toujours le cas dans le groupe stabilisateur), la somme \(\sum e_j\) est paire — le simulateur l’exige.
  2. Les portes — règles de conjugaison dérivées du §2, \(O(n)\) par porte. La porte \(T = \mathrm{diag}(1, e^{i\pi/4})\) est refusée : elle n’est pas Clifford, le formalisme ne s’applique plus. Ce refus est la frontière de Gottesman–Knill — il est pédagogique, pas accidentel.
  3. La mesure \(Z_q\) — déterministe ssi aucun stabilisateur n’anti-commute avec \(Z_q\) : l’état est déjà propre, l’outcome se lit (résolution de \((0 | e_q)\) dans le span GF(2) des stabilisateurs, produit par rowsum successifs — lecture pure, le tableau n’est pas modifié). Sinon aléatoire : outcome uniforme, et l’état post-mesure est stabilisé par \((-1)^m Z_q\).

Et en regard, la machine témoin : l’état complet \(2^n\) — pas de classe de circuits, il paie l’exponentielle partout, mais il simule tout, \(T\) comprise. Le croisement du §4 dirige ces deux machines l’une contre l’autre.

class CHPSimulator:
    """Simulateur stabilisateur d'Aaronson-Gottesman 2004 (algorithme CHP).

    Tableau : lignes 0..n-1 destabilisateurs, n..2n-1 stabilisateurs, ligne 2n scratch.
    Chaque ligne : bits x[i][j], z[i][j] et bit de signe r[i]. Portes Clifford :
    h, s, x, z, cnot ; mesures Z et X par qubit. Les portes non-Clifford (t) sont
    refusees : c'est la frontiere de Gottesman-Knill, pas un accident.
    """

    def __init__(self, n, rng=None):
        self.n = n
        self.x = np.zeros((2 * n + 1, n), dtype=np.int8)
        self.z = np.zeros((2 * n + 1, n), dtype=np.int8)
        self.r = np.zeros(2 * n + 1, dtype=np.int8)
        for j in range(n):  # etat |0...0> : destabilisateur X_j, stabilisateur Z_j
            self.x[j, j] = 1
            self.z[n + j, j] = 1
        self.rng = rng if rng is not None else np.random.default_rng(0)

    # -- affichage ---------------------------------------------------------
    def stab_string(self, i):
        return _row_string(self.x[self.n + i], self.z[self.n + i], self.r[self.n + i])

    def stabilizers(self):
        return [
            (self.x[self.n + i].copy(), self.z[self.n + i].copy(), int(self.r[self.n + i]))
            for i in range(self.n)
        ]

    # -- addition de lignes (AG04 fig. 2) ----------------------------------
    def rowsum(self, h, i):
        idx_i = _BIT_TO_INDEX[self.x[i], self.z[i]]
        idx_h = _BIT_TO_INDEX[self.x[h], self.z[h]]
        total_e = int(E_TABLE[idx_i, idx_h].sum())
        if total_e % 2 != 0:
            raise ValueError("rowsum sur lignes non commutantes : invariant viole")
        self.r[h] ^= int(self.r[i]) ^ ((total_e // 2) % 2)
        self.x[h] ^= self.x[i]
        self.z[h] ^= self.z[i]

    # -- portes Clifford (regles derivees au §2) ----------------------------
    def h(self, q):
        for i in range(2 * self.n + 1):
            xq, zq = int(self.x[i, q]), int(self.z[i, q])
            self.r[i] ^= xq & zq          # H Y H = -Y
            self.x[i, q], self.z[i, q] = zq, xq

    def s(self, q):
        for i in range(2 * self.n + 1):
            xq, zq = int(self.x[i, q]), int(self.z[i, q])
            self.r[i] ^= xq & zq          # S Y S+ = -X
            self.z[i, q] = zq ^ xq        # S X S+ = Y

    def xgate(self, q):
        for i in range(2 * self.n + 1):
            self.r[i] ^= int(self.z[i, q])

    def zgate(self, q):
        for i in range(2 * self.n + 1):
            self.r[i] ^= int(self.x[i, q])

    def cnot(self, c, t):
        # signe - uniquement pour x_c=1, z_t=1, z_c == x_t (bits lus AVANT les xors)
        for i in range(2 * self.n + 1):
            x_c, z_c = int(self.x[i, c]), int(self.z[i, c])
            x_t, z_t = int(self.x[i, t]), int(self.z[i, t])
            if x_c and z_t and (z_c == x_t):
                self.r[i] ^= 1
            self.x[i, t] = x_t ^ x_c
            self.z[i, c] = z_c ^ z_t

    def t(self, q):
        raise TypeError(
            f"porte T sur le qubit {q} refusee : T n'est pas Clifford, le formalisme "
            "stabilisateur (Gottesman-Knill) ne s'applique plus"
        )

    def apply(self, gate, *args):
        return {"h": self.h, "s": self.s, "x": self.xgate, "z": self.zgate,
                "cnot": self.cnot, "t": self.t}[gate](*args)

    # -- mesures ------------------------------------------------------------
    def _deterministic_outcome(self, q):
        """Lecture pure de l'outcome deterministe : le tableau n'est pas modifie.

        Z_q commute avec tous les stabilisateurs, donc (-1)^r Z_q est un produit
        d'entre eux. On resout (0 | e_q) dans le span GF(2) des stabs (gaussienne sur
        lignes, coefficients en colonnes augmentees), puis le produit se calcule par
        rowsum successifs -- legaux car les stabs commutent deux a deux.
        """
        n = self.n
        aug = np.concatenate(
            [self.x[n:2 * n], self.z[n:2 * n], np.eye(n, dtype=np.int8)], axis=1
        )
        pivots = {}
        for col in range(2 * n):
            taken = set(pivots.values())
            cand = None
            for r in range(n):
                if r not in taken and aug[r, col]:
                    cand = r
                    break
            if cand is None:
                continue
            pivots[col] = cand
            for r in range(n):
                if r != cand and aug[r, col]:
                    aug[r] ^= aug[cand]
        target = np.zeros(2 * n, dtype=np.int8)
        target[n + q] = 1
        coeffs = None
        for r in range(n):
            if np.array_equal(aug[r, :2 * n], target):
                coeffs = aug[r, 2 * n:].astype(bool)
                break
        if coeffs is None:
            raise ValueError("outcome deterministe introuvable : groupe invalide")
        scratch = 2 * n
        self.x[scratch] = 0
        self.z[scratch] = 0
        self.r[scratch] = 0
        for i in np.nonzero(coeffs)[0]:
            self.rowsum(scratch, n + int(i))
        # garde-fou : le produit doit etre exactement +-Z_q
        assert self.x[scratch].sum() == 0 and int(self.z[scratch, q]) == 1 \
            and int(self.z[scratch].sum()) == 1, "produit des stabs != +-Z_q"
        return int(self.r[scratch])

    def measure_z(self, q):
        """Mesure Z du qubit q : deterministe = lecture pure ; sinon outcome uniforme."""
        n = self.n
        scratch = 2 * n
        p = next((i for i in range(n, 2 * n) if self.x[i, q]), None)
        if p is None:
            return self._deterministic_outcome(q)
        m = int(self.rng.integers(2))
        self.x[scratch] = self.x[p]
        self.z[scratch] = self.z[p]
        self.r[scratch] = int(self.r[p])
        # eliminer la composante anti-commutante des autres lignes ; le partenaire
        # destabilisateur (p - n) est EXCLU : il doit garder x_q = 1 pour rester
        # anti-commutant avec le nouveau stabilisateur (-1)^m Z_q (invariant du tableau)
        for i in range(2 * n):
            if i != p and i != p - n and self.x[i, q]:
                self.rowsum(i, scratch)
        self.x[p] = 0
        self.z[p] = 0
        self.z[p, q] = 1
        self.r[p] = m
        return m

    def measure_x(self, q):
        self.h(q)
        m = self.measure_z(q)
        self.h(q)
        return m
class StateVectorSim:
    """Etat complet 2^n : la machine temoin, sans classe de circuits.

    Portes 1-qubit par tensordot sur le tenseur (2,)*n (qubit q = axe q, donc
    bit de poids 2**(n-1-q) dans l'index plat -- q0 est le bit le plus significatif,
    la meme convention que les outcomes du CHP). CNOT par bit-trick O(2^n).
    """

    H = np.array([[1, 1], [1, -1]], dtype=complex) / math.sqrt(2)
    S = np.array([[1, 0], [0, 1j]], dtype=complex)
    T = np.array([[1, 0], [0, np.exp(1j * math.pi / 4)]], dtype=complex)
    X = MATRICES["X"]
    Z = MATRICES["Z"]

    def __init__(self, n, rng=None):
        self.n = n
        self.psi = np.zeros(2 ** n, dtype=complex)
        self.psi[0] = 1.0
        self.rng = rng if rng is not None else np.random.default_rng(1)

    def apply_1q(self, U, q):
        shape = (2,) * self.n
        moved = np.tensordot(U, self.psi.reshape(shape), axes=([1], [q]))
        perm = list(range(1, self.n))
        perm.insert(q, 0)
        self.psi = np.transpose(moved, perm).reshape(-1)

    def cnot(self, c, t):
        idx = np.arange(2 ** self.n)
        flip = ((idx >> (self.n - 1 - c)) & 1) << (self.n - 1 - t)
        new = np.empty_like(self.psi)
        new[idx ^ flip] = self.psi[idx]
        self.psi = new

    def apply(self, gate, *args):
        if gate == "cnot":
            return self.cnot(*args)
        return self.apply_1q(
            {"h": self.H, "s": self.S, "t": self.T, "x": self.X, "z": self.Z}[gate],
            args[0],
        )

    def sample_z(self, shots):
        probs = np.abs(self.psi) ** 2
        return self.rng.choice(2 ** self.n, size=shots, p=probs / probs.sum())

    def expect_pauli(self, xs, zs):
        """<psi| P |psi> pour la chaine de Pauli encodee (xs, zs)."""
        vec = self.psi.astype(complex).reshape((2,) * self.n)
        for j in range(self.n):
            if int(xs[j]) or int(zs[j]):
                U = MATRICES[_pauli_letter(xs[j], zs[j])]
                moved = np.tensordot(U, vec, axes=([1], [j]))
                perm = list(range(1, self.n))
                perm.insert(j, 0)
                vec = np.transpose(moved, perm)
        return complex(np.vdot(self.psi, vec.reshape(-1)))


def gen_circuit(n, depth, seed):
    """Circuit Clifford aleatoire seedé : la MEME liste alimente les deux machines."""
    rng = np.random.default_rng(seed * 7919 + n * 31 + depth)
    gates = []
    for _ in range(depth):
        kind = rng.integers(3)
        if kind == 0:
            gates.append(("h", int(rng.integers(n))))
        elif kind == 1:
            gates.append(("s", int(rng.integers(n))))
        else:
            c = int(rng.integers(n))
            t = int(rng.integers(n - 1))
            if t >= c:
                t += 1
            gates.append(("cnot", c, t))
    return gates


def run_chp(n, gates, seed):
    sim = CHPSimulator(n, rng=np.random.default_rng(seed))
    for g in gates:
        sim.apply(*g)
    return sim


def run_sv(n, gates, seed):
    sim = StateVectorSim(n, rng=np.random.default_rng(seed))
    for g in gates:
        sim.apply(*g)
    return sim
# --- demos : les etats que tout le monde connait, lus dans le tableau -----------
bell = CHPSimulator(2, rng=np.random.default_rng(0))
bell.h(0)
bell.cnot(0, 1)
print("Bell |00>+|11> : stabilisateurs =", [bell.stab_string(i) for i in range(2)])

bell_sv = StateVectorSim(2)
bell_sv.apply("h", 0)
bell_sv.cnot(0, 1)
poids = np.abs(bell_sv.psi) ** 2
print("Bell vu par l'etat complet : poids |00> =", round(poids[0], 3),
      ", |11> =", round(poids[3], 3), ", ailleurs =", round(poids[1] + poids[2], 3))

# mesures Z successives : la correlation doit etre parfaite, tirage apres tirage
correles = 0
for shot in range(50):
    sim = CHPSimulator(2, rng=np.random.default_rng(1000 + shot))
    sim.h(0)
    sim.cnot(0, 1)
    correles += int(sim.measure_z(0) == sim.measure_z(1))
print(f"50 tirs de mesures Z correlees sur Bell : {correles}/50")

ghz = CHPSimulator(8, rng=np.random.default_rng(0))
ghz.h(0)
for j in range(1, 8):
    ghz.cnot(0, j)
print("GHZ-8 : stab[0] =", ghz.stab_string(0), "(attendu +XXXXXXXX)")
res = [ghz.measure_z(j) for j in range(8)]
print("GHZ-8 : les 8 mesures Z :", res, "-> toutes egales :", len(set(res)) == 1)
Bell |00>+|11> : stabilisateurs = ['+XX', '+ZZ']
Bell vu par l'etat complet : poids |00> = 0.5 , |11> = 0.5 , ailleurs = 0.0
50 tirs de mesures Z correlees sur Bell : 50/50
GHZ-8 : stab[0] = +XXXXXXXX (attendu +XXXXXXXX)
GHZ-8 : les 8 mesures Z : [1, 1, 1, 1, 1, 1, 1, 1] -> toutes egales : True

Lecture. Le tableau lit Bell exactement comme les cours le décrivent : stabilisateurs \(+XX\) et \(+ZZ\) — et la corrélation de mesure n’est pas énoncée, elle tombe du formalisme : 50/50 tirs corrélés, aucune exception. GHZ tient dans les mêmes lignes de bits : l’état le plus « intriqué » du zoo quantique coûte à l’arbitre exactement ce que coûte \(|0\rangle^{\otimes 8}\). C’est le premier résultat de la leçon : l’intrication n’est pas le mur — la classe de circuits l’est.

4. La preuve croisée : l’arbitre ne ment pas

Un port écrit à la main doit prouver sa justesse, pas la réclamer. Le banc :

  1. valeurs propres exactes, zéro bruit — pour des circuits Clifford aléatoires seedés, l’état final est un état stabilisateur : chacun de ses \(n\) stabilisateurs \((-1)^{r_i} P_i\) vérifie \(\langle P_i \rangle = (-1)^{r_i}\) exactement. Le CHP lit les \(P_i, r_i\) dans son tableau ; l’état complet calcule \(\langle P_i \rangle\) par contraction tensorielle indépendante. Toute erreur de phase du port — le seul endroit où se tromper — inverse un signe et fait échouer le test brutalement.
  2. distributions de mesure échantillonnées — les \(n\) mesures \(Z\) successives du CHP contre l’échantillonnage de la loi exacte \(|\psi|^2\) : distance totale (TV) bornée par la marge de sondage (deux sondages de la même loi divergent de \(\sim\sqrt{K/\pi}/\sqrt{\mathrm{shots}}\) sur \(K\) sorties possibles).
  3. troisième juge — si stim est installé, ses probabilités marginales de mesure donnent une seconde référence indépendante.
# --- croisement 1 : valeurs propres exactes (zéro bruit statistique) -----------
total_checks = 0
for n in (4, 6, 8, 10):
    for seed in GLOBAL_SEEDS:
        gates = gen_circuit(n, 3 * n, seed)
        chp = run_chp(n, gates, seed)
        sv = run_sv(n, gates, seed)
        for xs, zs, r in chp.stabilizers():
            val = sv.expect_pauli(xs, zs).real
            assert abs(val - (-1) ** r) < 1e-9, (n, seed, _row_string(xs, zs, r), val)
            total_checks += 1
print(f"Valeurs propres stabilisatrices egales au 1e-9 pres : {total_checks} checks exacts OK")

# --- croisement 2 : distributions de mesure echantillonnees ---------------------
shots = 3000 if BATCH_MODE != "true" else 1500
for n in (4, 6):
    for seed in (0, 7):
        gates = gen_circuit(n, 3 * n, seed)
        chp_counts = {}
        for shot in range(shots):
            chp = run_chp(n, gates, seed * 1009 + shot)  # rng distinct par tir
            outcome = 0
            for q in range(n):
                outcome = (outcome << 1) | chp.measure_z(q)
            chp_counts[outcome] = chp_counts.get(outcome, 0) + 1
        sv = run_sv(n, gates, seed)
        p_chp = np.zeros(2 ** n)
        for k, v in chp_counts.items():
            p_chp[k] = v / shots
        p_sv = np.bincount(sv.sample_z(shots), minlength=2 ** n) / shots
        tv = 0.5 * np.abs(p_chp - p_sv).sum()
        bins = int((p_sv > 0).sum())
        bruit = math.sqrt(bins / (math.pi * shots))
        print(f"n={n} seed={seed} : TV = {tv:.3f} (bruit de sondage attendu ~{bruit:.3f},"
              f" {bins} sorties possibles)")
        assert tv < max(0.12, 6 * bruit), (n, seed, tv, bruit)
print("Distributions sous le seuil (6x le bruit de sondage attendu) : OK")

# --- croisement 3 : troisieme juge stim, quand il est installe ------------------
try:
    import stim
except ImportError:
    stim = None
    print("stim non installe : le banc continue avec les deux machines du notebook")

if stim is not None:
    ok_marg = 0
    for n in (6, 8):
        for seed in GLOBAL_SEEDS:
            gates = gen_circuit(n, 3 * n, seed)
            st = stim.TableauSimulator(seed=seed)
            for g in gates:
                if g[0] == "h":
                    st.h(g[1])
                elif g[0] == "s":
                    st.s(g[1])
                else:
                    st.cx(g[1], g[2])  # stim.cx(controle, cible)
            # marginales par qubit : peek_z rend la valeur propre (+-1), 0 = aleatoire
            chp = run_chp(n, gates, seed)
            for q in range(n):
                own = chp.x[n:, q].sum() == 0          # CHP : lecture deterministe
                stim_valeur = int(st.peek_z(q))       # stim : +-1 ou 0 si aleatoire
                assert (stim_valeur != 0) == own, (n, seed, q, own, stim_valeur)
                if own:
                    assert stim_valeur == 1 - 2 * chp.measure_z(q), (n, seed, q)
                    ok_marg += 1
    print(f"stim confirme les {ok_marg} outcomes deterministes du CHP : OK")
Valeurs propres stabilisatrices egales au 1e-9 pres : 84 checks exacts OK
n=4 seed=0 : TV = 0.017 (bruit de sondage attendu ~0.029, 4 sorties possibles)
n=4 seed=7 : TV = 0.029 (bruit de sondage attendu ~0.029, 4 sorties possibles)
n=6 seed=0 : TV = 0.003 (bruit de sondage attendu ~0.021, 2 sorties possibles)
n=6 seed=7 : TV = 0.041 (bruit de sondage attendu ~0.058, 16 sorties possibles)
Distributions sous le seuil (6x le bruit de sondage attendu) : OK
stim confirme les 14 outcomes deterministes du CHP : OK

Lecture. Chaque erreur possible du port a un détecteur dédié : une erreur de phase dans rowsum ou la règle du \(\mathsf{CNOT}\) inverse une valeur propre ; une erreur dans la mesure déplace la masse d’une distribution ; une erreur de convention d’axes mélange les qubits et fait échouer les deux bancs à la fois. Le port que vous venez de lire est passé exact sur les valeurs propres (aucun bruit qui puisse cacher un signe) et sous le seuil statistique sur les distributions — le même protocole qui, appliqué au brouillon de ce notebook, a intercepté une règle de phase du \(\mathsf{CNOT}\) fausse (le piège \(X_c Z_t\) / \(Y_c Y_t\) du §2) : le banc n’est pas décoratif, il a déjà servi.

5. La mesure discriminante : le régime, pas l’objet

Protocole : les mêmes circuits (profondeur \(3n\), portes Clifford uniformes, seeds \((0, 1, 7)\)) sur les trois machines, temps médian par taille. Puis la même question côté suprématie : que se passe-t-il quand le circuit quitte la classe — une fraction \(f\) des portes remplacée par des \(T\) ?

NS_CHP = [6, 8, 10, 12, 16, 20, 24, 32, 40, 48, 64]
NS_SV = [6, 8, 10, 11, 12, 13, 14, 15, 16, 18, 20, 22]
NS_STIM = [6, 8, 12, 16, 20, 24, 32, 48, 64, 96, 128, 192, 256]


def mediane(fonction, ns):
    """(tailles, temps medians en secondes) : 3 seeds par taille."""
    tailles, temps = [], []
    for n in ns:
        echantillons = []
        for seed in GLOBAL_SEEDS:
            gates = gen_circuit(n, 3 * n, seed)
            t0 = time.perf_counter()
            fonction(n, gates, seed)
            echantillons.append(time.perf_counter() - t0)
        tailles.append(n)
        temps.append(sorted(echantillons)[1])
    return np.array(tailles), np.array(temps)


def run_stim(n, gates, seed):
    st = stim.TableauSimulator(seed=seed)
    for g in gates:
        if g[0] == "h":
            st.h(g[1])
        elif g[0] == "s":
            st.s(g[1])
        else:
            st.cx(g[1], g[2])


chp_ns, chp_t = mediane(run_chp, NS_CHP)
sv_ns, sv_t = mediane(run_sv, NS_SV)
if stim is not None:
    stim_ns, stim_t = mediane(run_stim, NS_STIM)
    stim_t_map = dict(zip(stim_ns, stim_t))
else:
    stim_t_map = {}
print("Temps median par taille (profondeur 3n, 3 seeds) :")
print(f"{'n':>5} | {'port CHP':>10} | {'etat complet':>12} | {'stim':>10}")
sv_map = dict(zip(sv_ns, sv_t))
for i, n in enumerate(chp_ns):
    sv_dt = sv_map.get(n)
    stim_dt = stim_t_map.get(n)
    print(f"{n:>5} | {chp_t[i]*1000:>8.1f}ms | "
          + (f"{sv_dt*1000:>10.1f}ms" if sv_dt else f"{'-':>12}")
          + " | " + (f"{stim_dt*1000:>8.2f}ms" if stim_dt else "-"))

# dernier point commun au ratio
n_commun = 20
ratio = sv_map[n_commun] / chp_t[chp_ns.tolist().index(n_commun)]
print(f"\nRatio etat-complet / port CHP a n={n_commun} : {ratio:.0f}x")
if stim_t_map:
    print(f"Ratio port CHP / stim a n={n_commun} : "
          f"{chp_t[chp_ns.tolist().index(n_commun)] / stim_t_map[n_commun]:.0f}x "
          "(le port est fait pour etre lu, l'organe du metier pour la course)")
Temps median par taille (profondeur 3n, 3 seeds) :
    n |   port CHP | etat complet |       stim
    6 |      0.2ms |        0.1ms |     0.11ms
    8 |      0.3ms |        0.2ms |     0.08ms
   10 |      0.5ms |        0.3ms | -
   12 |      0.6ms |        0.7ms |     0.08ms
   16 |      0.9ms |       46.5ms |     0.09ms
   20 |      1.1ms |     1591.8ms |     0.11ms
   24 |      1.5ms |            - |     0.13ms
   32 |      3.1ms |            - |     0.17ms
   40 |      4.8ms |            - | -
   48 |      6.6ms |            - |     0.26ms
   64 |     10.5ms |            - |     0.36ms

Ratio etat-complet / port CHP a n=20 : 1480x
Ratio port CHP / stim a n=20 : 10x (le port est fait pour etre lu, l'organe du metier pour la course)
# --- regressions : ce que chaque machine paie par qubit -------------------------
# etat complet : t ~ a * 2^n  ->  log2(t) = log2(a) + n  (droite de pente ~1,
# mais les echelons locaux sont plus raides : la memoire aussi a une loi)
a_sv, b_sv = np.polyfit(sv_ns, np.log2(sv_t), 1)
r2_sv = 1 - np.sum((np.log2(sv_t) - (a_sv * sv_ns + b_sv)) ** 2) / np.sum(
    (np.log2(sv_t) - np.mean(np.log2(sv_t))) ** 2
)
rapports_locaux = sv_t[1:] / sv_t[:-1]
print(f"etat complet : pente {a_sv:.2f} bits de log2(t) par qubit (R^2 = {r2_sv:.4f}) ;"
      f" echelons locaux entre {rapports_locaux.min():.1f}x et"
      f" {rapports_locaux.max():.1f}x par qubit")
print("  (plancher theorique 2x par qubit ; au-dela = effets de memoire :")
print("   chaque qubit double le vecteur, et la copie finit par sortir des caches)")

# bascule MESUREE : le plus petit n ou l'etat complet depasse deja le port
pairs = {n: (s, c) for n, s, c in zip(sv_ns, sv_t, [chp_t[chp_ns.tolist().index(n)]
                                                    for n in sv_ns if n in chp_ns])}
n_bascule = next(n for n in sv_ns
                 if n in pairs and pairs[n][0] > pairs[n][1])
print(f"\nBascule MESUREE : des n = {n_bascule} qubits, l'etat complet paie plus que"
      f" l'arbitre ({pairs[n_bascule][0]/pairs[n_bascule][1]:.1f}x), et l'ecart"
      " double ensuite a chaque qubit")

# extrapolations (niveau Cite de la hierarchie du depot : ajustement, non mesure)
for n_cible in (30, 40):
    t_fit = 2 ** (a_sv * n_cible + b_sv)
    unite, val = ("h", t_fit / 3600) if t_fit > 3600 else ("s", t_fit)
    print(f"EXTRAPOLATION du fit 2^n : n={n_cible} -> {val:.3g} {unite} par circuit"
          " (non mesure)")
etat complet : pente 1.10 bits de log2(t) par qubit (R^2 = 0.9313) ; echelons locaux entre 1.3x et 7.9x par qubit
  (plancher theorique 2x par qubit ; au-dela = effets de memoire :
   chaque qubit double le vecteur, et la copie finit par sortir des caches)

Bascule MESUREE : des n = 13 qubits, l'etat complet paie plus que l'arbitre (1.1x), et l'ecart double ensuite a chaque qubit
EXTRAPOLATION du fit 2^n : n=30 -> 1.65e+03 s par circuit (non mesure)
EXTRAPOLATION du fit 2^n : n=40 -> 933 h par circuit (non mesure)
# --- densite T : le regime ou l'arbitre rend son tablier ------------------------
def gen_circuit_T(n, depth, seed, fraction):
    """Circuit Clifford ou une fraction des portes est remplacee par T."""
    rng = np.random.default_rng(seed * 7919 + n * 31 + depth + int(fraction * 1000))
    gates = []
    for _ in range(depth):
        if rng.random() < fraction:
            gates.append(("t", int(rng.integers(n))))
            continue
        kind = rng.integers(3)
        if kind == 0:
            gates.append(("h", int(rng.integers(n))))
        elif kind == 1:
            gates.append(("s", int(rng.integers(n))))
        else:
            c = int(rng.integers(n))
            t = int(rng.integers(n - 1))
            if t >= c:
                t += 1
            gates.append(("cnot", c, t))
    return gates


print("Une SEULE porte T dans le circuit, et la classe casse :")
for fraction, injecte_une_T, etiquette in [
    (0.0, False, "Clifford pur"),
    (0.0, True, "1 porte T"),
    (0.05, False, "5% de T"),
    (0.10, False, "10% de T"),
]:
    gates = gen_circuit_T(8, 24, 0, fraction)
    if injecte_une_T:
        gates = gates[:12] + [("t", 0)] + gates[12:]  # exactement une porte T
    # 1. l'arbitre polynomial
    try:
        run_chp(8, gates, 0)
        verdict_chp = "simule"
    except TypeError as exc:
        verdict_chp = f"REFUSE ({str(exc)[:44]}...)"
    # 2. l'outil du metier
    if stim is not None:
        verdict_stim = "simule" if hasattr(stim.TableauSimulator(), "t") else "pas de porte t"
    else:
        verdict_stim = "non installe"
    # 3. l'etat complet : aucune classe, il paie 2^n et simule tout
    t0 = time.perf_counter()
    run_sv(8, gates, 0)
    dt_sv = time.perf_counter() - t0
    print(f"  {etiquette:>14} : port CHP {verdict_chp} | stim : {verdict_stim} | "
          f"etat complet : {dt_sv*1000:.1f} ms, sans changer d'allure")

print()
print("Message du banc : la frontiere n'est pas 'quantique contre classique',")
print("elle est 'Clifford contre le reste' -- et T est du reste.")
Une SEULE porte T dans le circuit, et la classe casse :
    Clifford pur : port CHP simule | stim : pas de porte t | etat complet : 1.0 ms, sans changer d'allure
       1 porte T : port CHP REFUSE (porte T sur le qubit 0 refusee : T n'est pas...) | stim : pas de porte t | etat complet : 4.3 ms, sans changer d'allure
         5% de T : port CHP REFUSE (porte T sur le qubit 0 refusee : T n'est pas...) | stim : pas de porte t | etat complet : 3.4 ms, sans changer d'allure
        10% de T : port CHP REFUSE (porte T sur le qubit 7 refusee : T n'est pas...) | stim : pas de porte t | etat complet : 0.9 ms, sans changer d'allure

Message du banc : la frontiere n'est pas 'quantique contre classique',
elle est 'Clifford contre le reste' -- et T est du reste.

Lecture. Trois constats, un seul message.

  1. À circuits Clifford purs, la bascule est mesurée, pas extrapolée : dès la douzaine de qubits, l’état complet paie déjà plus que l’arbitre, et le ratio imprimé par le banc à \(n = 20\) se lit en milliers. La pente globale est \(\approx 1\) bit de \(\log_2 t\) par qubit (\(R^2\) affiché), mais les échelons locaux montent jusqu’à plusieurs fois \(2\times\) par qubit : le plancher théorique \(2^n\) est optimiste — chaque qubit double le vecteur, et les copies finissent par sortir des caches. Le mur réel est plus raide que la théorie, et le banc le montre. Les projections à \(n = 30\) et \(n = 40\) sont extrapolées du fit (\(R^2\) affiché), pas mesurées : niveau Cité de la hiérarchie du dépôt, étiqueté tel quel.
  2. Une seule porte \(T\) ferme l’arbitre — refus explicite, avec explication, pas un crash. Et l’outil du métier fait pareil : stim, le simulateur stabilisateur de référence, n’a pas de méthode t du tout. La frontière n’est pas un manque d’ingénierie : elle est théorique — c’est le théorème de Gottesman–Knill lu dans le mauvais sens (la simulation polynomiale existe pour Clifford, et n’existe pas, sous hypothèses standard, pour Clifford+\(T\)).
  3. L’état complet, lui, ne change pas d’allure : la porte \(T\) est une \(2\times2\) de plus, gratuite à ses yeux. Mais son prix ne dépendait déjà pas des portes — seulement de \(n\). Chaque machine a son invariant : l’une paie \(2^n\) quelles que soient les portes, l’autre paie \(n^2\) mais seulement dans sa classe.

C’est la leçon de méthode, mesurée : une « suprématie quantique » est une assertion conjointe sur une classe de circuits et un régime de taille. Réfuter proprement, c’est exhiber le régime où l’assertion casse — ici, tout circuit Clifford, quelle que soit la taille. Installer la claim, c’est montrer qu’on est sorti du régime — et \(T\) est le billet d’entrée le plus faible du hors-classe.

6. Exercices

Les stubs s’exécutent sans erreur (règle C.1 du dépôt) ; les indices et étapes guident sans écrire la solution. Les variables des bancs des sections précédentes restent en portée.

Exercice 1 — La phase par commutation, sans matrices

Le §1 dérive la table de phase en multipliant les matrices. Une autre voie, purement algébrique, n’utilise que : (i) deux Pauli non triviales distinctes anti-commutent ; (ii) l’identité \(X \cdot Y = iZ\) (conséquence de \(Y = iXZ\)) ; (iii) l’hermiticité (\(P_1 P_2 = (P_2 P_1)^\dagger\) inverse l’exposant). Écrire pauli_product_phase(p1, p2) qui retourne \(e\) tel que \(P_1 P_2 = i^e P'\) sans aucune matrice, puis la comparer à E_TABLE case par case.

# Exercice 1 : a completer
def pauli_product_phase(p1, p2):
    """Exposeant e (0..3) tel que P1 @ P2 = (i**e) * P', sans matrices.

    p1, p2 : lettres parmi "I", "X", "Y", "Z".
    """
    e = 0   # TODO etudiant : exposeant tel que P1 @ P2 = (i**e) * P'
    # Indice : les cas ou p1 == p2 ou l'un vaut "I" donnent e = 0.
    # Etape 1 : traiter ces cas triviaux.
    # Etape 2 : pour les 6 paires restantes, partir de X.Y = iZ (e = 1) et deriver
    #           Y.Z = iX et Z.X = iY par permutation circulaire des roles.
    # Etape 3 : les paires a contre-courant (Y.X, Z.Y, X.Z) par hermicite :
    #           e(P2.P1) = (4 - e(P1.P2)) mod 4.
    return e

ok, ecarts = 0, []
for p1 in "IXYZ":
    for p2 in "IXYZ":
        attendu = int(E_TABLE["IXYZ".index(p1), "IXYZ".index(p2)])
        rendu = pauli_product_phase(p1, p2)
        if rendu == attendu:
            ok += 1
        else:
            ecarts.append(f"{p1}.{p2}: attendu {attendu}, rendu {rendu}")
print(f"Comparaison case par case avec E_TABLE : {ok}/16 concordent")
for e in ecarts:
    print("  ecart :", e)
Comparaison case par case avec E_TABLE : 10/16 concordent
  ecart : X.Y: attendu 1, rendu 0
  ecart : X.Z: attendu 3, rendu 0
  ecart : Y.X: attendu 3, rendu 0
  ecart : Y.Z: attendu 1, rendu 0
  ecart : Z.X: attendu 1, rendu 0
  ecart : Z.Y: attendu 3, rendu 0

Exercice 2 — L’arbitre de classe

Écrire verdict_simulateur(n, portes) : étant donné un circuit (liste de tuples comme celles des bancs du §5) et une taille, retourner "CHP" si le circuit est Clifford (l’arbitre polynomial s’applique), "etat-complet" s’il sort de la classe mais reste dans les clous de l’état complet (\(2^n \le 2^{22}\) amplitudes, la limite mémoire des bancs de ce notebook), "aucun" sinon. La fonction ne simule rien : elle lit la classe.

# Exercice 2 : a completer
def verdict_simulateur(n, portes):
    """'CHP' si Clifford, 'etat-complet' si 2**n <= 2**22, sinon 'aucun'."""
    verdict = None   # TODO etudiant
    # Etape 1 : detecter une porte non-Clifford ("t") dans la liste.
    # Etape 2 : si Clifford pur -> 'CHP' (Gottesman-Knill : polynomial, toute taille).
    # Etape 3 : sinon, arbitrer par la memoire : n <= 22 -> 'etat-complet', sinon 'aucun'.
    return verdict


def _circuit_avec_une_T(n, depth, seed):
    gates = gen_circuit(n, depth, seed)
    return gates[: depth // 2] + [("t", 0)] + gates[depth // 2:]


cas_tests = [
    ("Clifford n=64", 64, gen_circuit(64, 3 * 64, 0)),
    ("1 porte T, n=8", 8, _circuit_avec_une_T(8, 24, 0)),
    ("10% de T, n=8", 8, gen_circuit_T(8, 24, 0, 0.10)),
    ("10% de T, n=50", 50, gen_circuit_T(50, 150, 0, 0.10)),
]
for nom, n, portes in cas_tests:
    print(f"  {nom:>16} -> {verdict_simulateur(n, portes)}")
     Clifford n=64 -> None
    1 porte T, n=8 -> None
     10% de T, n=8 -> None
    10% de T, n=50 -> None

Exercice 3 — Le mur, projeté par ses échelons

Le banc du §5 mesure les échelons locaux de l’état complet : le rapport \(t(n{+}1)/t(n)\), qubit par qubit. Recalculer la projection à partir de ces échelons seuls : estimer le facteur multiplicatif par qubit (les petites tailles sont dominées par les coûts fixes : ne garder que \(n \ge 12\)), vérifier qu’il est au-dessus du plancher théorique \(2\), en déduire le temps projeté à \(n = 30\), puis le plus petit \(n\) où la projection dépasse une heure par circuit.

# Exercice 3 : a completer
facteur_par_qubit = None   # TODO etudiant : facteur multiplicatif de sv_t par qubit
t_projete_30 = None        # TODO etudiant : temps projete a n = 30 (secondes)
n_une_heure = None         # TODO etudiant : plus petit n ou le temps projete > 3600 s
# Indice : sur une loi 2^n, t(n+1)/t(n) serait exactement 2 -- le banc mesure plus
# (effets de memoire). Estimer le facteur REEL par la mediane des rapports
# consecutifs de sv_t pour n >= 12.
# Etape 1 : rapports consecutifs sv_t[i+1]/sv_t[i] sur les tailles n >= 12, mediane.
# Etape 2 : projeter depuis le DERNIER point mesure jusqu'a n=30 (multiplications
#           successives par le facteur).
# Etape 3 : poursuivre la projection jusqu'a depasser 3600 secondes.

print("Exercice a completer : mur projete par ses echelons")
if facteur_par_qubit is not None:
    print(f"  facteur par qubit : {facteur_par_qubit:.2f} (plancher theorique 2)")
    print(f"  temps projete a n=30 : {t_projete_30:.3g} s")
    print(f"  projection > 1 heure des n = {n_une_heure}")
Exercice a completer : mur projete par ses echelons

7. Conclusion

Geste Où Ce qui a été mesuré
Dériver, pas recopier §1–§2 Table de phase et conjugaison CHP construites par multiplication des matrices \(2\times2\) ; le piège de phase \(X_c Z_t / Y_c Y_t\) exhibé, pas affirmé
Construire l’organe §3 Port CHP complet (rowsum, portes, mesures — déterministe par lecture GF(2), aléatoire par re-stabilisation) ; Bell et GHZ lus dans le tableau, 50/50 corrélations mesurées
Prouver l’arbitre §4 84 valeurs propres stabilisatrices exactes au \(10^{-9}\) (zéro bruit) ; distributions TV sous 6× le bruit de sondage ; stim confirme les outcomes déterministes
Mesurer le régime §5 Bascule mesurée dès \(n = 13\) qubits ; ratio 1480× à \(n = 20\) ; pente \(\approx 1\) bit/qubit côté état complet (\(R^2\) affiché) avec échelons locaux au-dessus du plancher \(2\times\) (mémoire) ; projections \(n = 30/40\) extrapolées du fit, étiquetées telles
Fermer la classe §5 Une porte \(T\) → refus du port et de stim (pas de méthode t) ; l’état complet inchangé — la frontière est Clifford/le-reste, pas quantique/classique

Ce que 2004 a fondé ici. Aaronson et Gottesman n’ont pas « accéléré » la simulation quantique : ils ont délimité la terre qui ne demandait pas de moteur quantique. La leçon de méthode, mesurée sur ce banc, déborde le quantique : face à une claim d’avantage — matériel, algorithmique, organisationnelle — la question qui réfute ou installe n’est jamais « est-ce puissant ? » mais « de quel régime parle-t-on, et où casse-t-il ? ». L’arbitre exécutable est la réponse la plus honnête qu’on puisse rendre : il ne discute pas la claim, il tourne jusqu’à sa frontière.

Hommage. Le titre du notebook reprend le geste qu’Aaronson a le plus pratiqué — déquantifier : chercher, derrière chaque « seul un quantique peut », le simulateur classique du régime qui le contredit. Ce notebook est ce geste, retourné en banc pédagogique : deux machines, une frontière, et chaque phase prouvée par construction.

Références

— Aaronson, S., & Gottesman, D. (2004). « Improved Simulation of Stabilizer Circuits ». Physical Review A 70, 052328 (quant-ph/0406196). — Gottesman, D. (1998). « The Heisenberg Representation of Quantum Computers ». PhD thesis, Caltech (quant-ph/9807006) — le théorème de Gottesman–Knill. — Aaronson, S. (2007). « Are Quantum States Exponentially Long Vectors? ». arXiv quant-ph/0701104 — le cadre de la déquantification et les classes de simulateurs. — Gidney, C. (2021). « Stim: a fast stabilizer circuit simulator ». Quantum 7, 1297. — Nielsen, M. A., & Chuang, I. L. (2010). Quantum Computation and Quantum Information, Cambridge University Press — chapitre 10.5, le formalisme stabilisateur.

Retour au sommet