Le test d'états stabilisateurs nécessite Θ(n-k) échantillons avec une mémoire quantique limitée

Les chercheurs analysent la complexité en nombre d'échantillons du test et de l'apprentissage des états stabilisateurs à n qubits lorsqu'un algorithme est limité au maintien de seulement k qubits de mémoire quantique cohérente entre les mesures. L'étude démontre que cette contrainte de mémoire élimine la séparation entre le test et l'apprentissage qui existe avec une mémoire non restreinte.

• Le test d'états stabilisateurs nécessite Θ(n-k) échantillons dans le cadre de la mémoire à k qubits.
• L'apprentissage d'états stabilisateurs dans le cadre non adaptatif nécessite Θ(n²/k) échantillons.
• Une borne inférieure exponentielle est prouvée pour le test de pureté même lorsque la mémoire reste cohérente tout au long du protocole.
• Avec k=cn qubits de mémoire (0<c<1), le test stabilisateur devient aussi difficile que l'apprentissage, nécessitant tous deux Θ(n) copies.

Les résultats identifient la mémoire quantique cohérente comme la ressource critique permettant la séparation habituelle entre la complexité du test et celle de l'apprentissage des états stabilisateurs.