Qu'est-ce que c'est exactement "Random Circuit Sampling"?

12

Beaucoup de gens ont suggéré d'utiliser "Random Circuit Sampling" pour démontrer la suprématie quantique. Mais quelle est la définition précise du problème "Random Circuit Sampling"? J'ai vu des déclarations comme «la tâche consiste à prendre un circuit quantique aléatoire (efficace) d'une forme spécifique et à générer des échantillons à partir de sa distribution de sortie». Mais il n'est pas clair pour moi ce que les termes "circuit quantique aléatoire (efficace)" signifient précisément. Connaissons-nous également la complexité informatique classique de ce problème?

grok
la source
Je ne vois pas James Wootton mentionner la complexité du problème RCS, donc c'est # P-difficile, voir cet article: arxiv.org/pdf/1803.04402.pdf
YOUSEFY

Réponses:

13

Il existe un ensemble continu d'états possibles pour qubits, chacun pouvant être exprimé comme une superposition des états de base.2 nn2n

La plupart de ces états sont fortement enchevêtrés et nécessiteraient des circuits très complexes à créer (en supposant l'ensemble de portes standard de rotations à qubit unique et de deux ou trois portes à enchevêtrement de qubit).

|0

n

nn

nn

Les détails sur la façon exacte de créer le circuit aléatoire et les éléments à rechercher dans les résultats pour déclarer le succès dépendent de la proposition (comme celle de Google). Il n'est pas encore clair non plus combien de qubits sont nécessaires avant que les supercalculateurs actuels ne puissent pas reproduire le résultat.

James Wootton
la source