Une notion de circuits quantiques monotones

27

Dans la complexité de calcul, il existe une distinction importante entre les calculs monotones et généraux et un célèbre théorème de Razborov affirme que le 3-SAT et même MATCHING ne sont pas polynomiaux dans le modèle des circuits booléens monotones.

Ma question est simple: existe-t-il un analogique quantique pour les circuits monotones (ou plus d'un)? Existe-t-il un théorème quantique de Razborov?

Gil Kalai
la source
10
Voici mes deux cents: le saut des circuits classiques aux circuits quantiques peut être divisé en deux étapes en ajoutant des circuits réversibles classiques au milieu. Les circuits réversibles classiques sont ceux dans lesquels seules les portes réversibles sont autorisées. Par exemple, la porte de Toffoli est une porte universelle pour le calcul réversible. Je ne sais pas comment définir la notion de monotone pour ces circuits. Il me semble que la définition de circuits réversibles classiques monotones est une condition préalable à la définition de circuits quantiques monotones.
Robin Kothari
6
(1) Un circuit réversible (classique) implémente une bijection sur {0,1} ^ n, et clairement la seule bijection monotone est la cartographie d'identité. Je ne pense donc pas qu'il soit raisonnable de définir les «circuits réversibles monotones» de manière non triviale.
Tsuyoshi Ito
3
(2) Je ne suis pas sûr du cas quantique. Si nous pouvons définir des «canaux quantiques monotones», alors il sera naturel de définir des «circuits quantiques monotones» comme des circuits quantiques dont l'ensemble de portes est choisi parmi les canaux quantiques monotones, tout comme les circuits classiques monotones sont des circuits dont l'ensemble de portes est choisi parmi les fonctions monotones. .
Tsuyoshi Ito
2
@RobinKothari, TsuyoshiIto: L'importance de la réversibilité pour le calcul quantique vient précisément du cas particulier de l'évolution de Schrödinger d'un système fermé. Quand nous parlons des portes ET et OU, cependant, nous considérons un système physique abstrait qui est une caricature des portes logiques qui se trouvent dans les ordinateurs; et ces portes fonctionnent précisément parce qu'elles ne sont pas des systèmes fermés. Si nous nous permettons de parler des portes ET et OU en soi, je pense qu'il est tout à fait raisonnable de lever la convention de considérer également les systèmes fermés pour la question de calcul quantique.
Niel de Beaudrap
3
@Niel, Tsuyoshi: Je suppose que je pensais qu'un circuit quantique monotone serait toujours un circuit quantique au sens traditionnel (c'est-à-dire unitaire suivi d'une mesure). Mais suivant l'argument de Niel, je suppose qu'il est logique de supprimer cette contrainte. Donc, mon commentaire précédent ne s'applique pas vraiment alors.
Robin Kothari

Réponses:

17

Vous posez vraiment deux questions différentes et espérez qu'il y ait une seule réponse qui répond aux deux: (1) Quelles sont les notions naturelles des circuits monotones quantiques? (2) À quoi ressemblerait un résultat quantique de type Razborov sur réseau?

Il n'est pas évident de savoir comment atteindre les deux en même temps, donc je vais décrire ce qui me semble une notion raisonnable de circuits monotones quantiques (sans indiquer s'il existe ou non un résultat Razborov correspondant), et une notion complètement différente de à quoi ressemblerait une conjecture quantique «naturelle» de Razborov (sans indiquer si elle est vraisemblablement vraie).

Ce que nous voulons du quantum

Comme je le remarque dans les commentaires, je pense qu'il n'est pas nécessaire d'essayer de faire entrer la notion de circuits monotones dans un moule d'unité. Que ce soit dans le fait que l'évolution avec le temps n'a pas besoin de préserver la base standard, ou dans le fait qu'il existe de multiples bases de mesure dans lesquelles les résultats peuvent être enchevêtrés, je pense que la condition sine qua non du calcul quantique est le fait que le la base standard n'est pas la seule base. Même parmi les états du produit, il est dans certaines implémentations défini uniquement par un choix de cadre de référence.

Ce que nous devons faire est de considérer les choses de manière à retirer la base standard de sa place privilégiée traditionnelle - ou, dans ce cas, autant que possible tout en conservant une notion significative de monotonie.

Un modèle simple de circuits monotones quantiques

Considérons un modèle de circuit qui est implicite dans le commentaire de Tsuyoshi Ito sur les "canaux quantiques monotones" (et qui est à peu près ce que l'on doit faire si l'on veut une notion de "circuit" qui ne se limite pas à l'évolution unitaire).

Soit l'espace des opérateurs hermitiens sur (de sorte qu'il contienne tous les opérateurs de densité sur un qubit). Comment définirions-nous une porte monotone quantique partir de deux qubits d'entrée vers un qubit de sortie , de telle sorte que ce ne soit pas effectivement un classique porte monotone? Je pense qu'il est simple de dire que la sortie ne doit pas être limitée àouou leurs mélanges; mais pour être "monotone", nous devrions exiger que comme et C 2 G : H aH bH c a , b c | 0 HC2G:HaHbHca,bc| 1 |00|1 ||11|1|1|Tra(ρab)|11| G(ρ a b )| 1G1|Trb(ρab)|1 augmentation de , la valeur de doit être non décroissant. Pour une porte qubit à deux entrées, cela signifie que doit être implémentable en principe comme1|G(ρab)|1G

  1. effectuer une mesure à deux qubits par rapport à une base orthonormée , où couvrir le sous-espace de Hamming poids 1, et| u , | v {|00,|μ,|ν,|11}|μ,|ν

  2. produisant en sortie un état correspondant au résultat mesuré, où pour chaque .ρ{ρ00,ρμ,ρν,ρ11}X { μ , ν }1|ρ00|11|ρλ|11|ρ11|1λ{μ,ν}

Les circuits ne sont que des compositions de ceux-ci de manière sensée. Nous pourrions également autoriser le fan-out, sous la forme de circuits qui intègrent unitairement et ; nous devrions à tout le moins autoriser ces mappages en entrée, pour permettre la copie de chaque bit d'entrée (nominalement classique).| 1 | 11 1 |0|000|1|111

Il semble raisonnable soit de considérer l'ensemble du continuum de telles portes, soit de se limiter à une collection finie de telles portes. Tout choix donne lieu à une "base de porte monotone quantique" différente pour les circuits; on peut considérer les propriétés des différentes bases monotones. Les états peuvent être choisis de manière totalement indépendante, sous réserve de la contrainte de monotonie; il serait sans aucun doute intéressant (et probablement pratique de relier l'erreur) de définiret, bien que je ne vois aucune raison d'exiger cela dans la théorie. De toute évidence, AND et OR sont des portes de ce type, oùet ρ 00 = | 0 ρ00,ρμ,ρν,ρ11ρ 11 = | 1 ρ00=|00|ρ μ = ρ ν = | 0 ρ11=|11|ρ μ = ρ ν = | 1 ρμ=ρν=|00|| u | v ρμ=ρν=|11|respectivement, quel que soit le choix de ou .|μ|ν

Pour toute constante k , on pourrait également considérer les bases de portes, y compris les portes k -entrée-une sortie. L'approche la plus simple dans ce cas serait probablement de permettre aux portes qui peuvent être implémentées comme ci-dessus, permettant toute décomposition des sous-espaces de chaque poids de Hamming , et d'exiger que pour chacunG:HkHVwH2k0wk0 w < k

max|ψVw1|G(|ψψ|)|1min|ψVw+11|G(|ψψ|)|1
0w<k . On ne sait pas combien de puissance de calcul supplémentaire cela vous donnerait (ni même dans le cas classique).

Je ne sais pas s'il y a quelque chose d'intéressant à dire sur de tels circuits au-delà du cas classique, mais cela me semble être la définition candidate la plus prometteuse d'un "circuit monotone quantique".

Une variante quantique du résultat de Razborov

Considérez l' exposition par Tim Gowers des résultats d' Alon et Boppana (1987), Combinatorica 7 pp. 1–22 qui renforcent les résultats de Razborov (et expliquent certaines de ses techniques) pour la complexité monotone de CLIQUE. Gowers présente cela en termes de construction récursive d'une famille d'ensembles, en partant des "demi-espaces" du cube booléen pour chaque . Si nous supprimons la position privilégiée de la base standard dans les ensembles de base, par analogie avec le lemme local de Lovász quantique , nous pouvons considérer un sous-espace de 1 j n H n 2 n A jH n 2 A j = U j E j

Ej={x{0,1}n:xj=1}
1jnH2ncorrespondre à une proposition binaire (si un état appartient au sous-espace, ou lui est plutôt orthogonal) qui pourrait résulter de la mesure. Par exemple, nous pouvons considérer sous-espaces donné par Nous autorisons les analogues quantiques de la conjonction et de la disjonction des sous-espaces: nAjH2nAB = AB ; AB = A + B = { a + b
Aj=UjEj, for each 1jnwhere Ej:={|x:xEj};Uj:H2nH2n a unitary of bounded complexity.
CΠCCΠK(r)rΠC-ΠK(r)<
AB=AB;AB=A+B={a+b:aA,bB}.
Nous demandons ensuite combien de temps une construction récursive des conjonctions et des disjonctions d'espaces est nécessaire pour obtenir un espace , de sorte que le projecteur sur ne diffère que légèrement du projecteur sur l'espace couvert par les fonctions indicatrices de graphes ayant des cliques de taille ; par exemple, pour queCΠCCΠK(r)rΠCΠK(r)<1/poly(n). La partie monotone est impliquée dans les opérations logiques quantiques, et les propositions primitives concernant l'entrée sont également quantiques.

Dans le cas général, il y a un problème à traiter cela comme un problème de calcul: la disjonction ne correspond à aucune connaissance qui pourrait être obtenue avec certitude par des mesures sur un nombre fini de copies en utilisant des mesures en boîte noire pour et seul, sauf s'il s'agit d'images de projecteurs de navettage. Ce problème général peut toujours être traité comme un résultat intéressant sur la complexité géométrique-combinatoire, et pourrait donner lieu à des résultats liés aux Hamiltioniens locaux frustrés. Cependant, il pourrait être plus naturel d'exiger simplement que les sous-espacesABAjdécoulent des déplacements des projecteurs, auquel cas la disjonction n'est que le OU classique des résultats de mesure de ces projecteurs. Ensuite, nous pouvons exiger que les unitaires tous les mêmes, et cela devient un problème concernant un circuit unitaire (qui donne lieu aux "événements primitifs") avec un post-traitement classique monotone (qui effectue les opérations logiques sur ces événements).Uj

Notez également que si nous n'imposons aucune restriction supplémentaire aux espaces , il peut s'agir d'un sous-espace avec un chevauchement très élevé avec un espace étendu par des états de base standard , qui sont ces chaînes binaires dans lesquelles .AjEkxE¯kxk=0

  • Si cette possibilité vous rend délicat, vous pouvez toujours exiger que ait un angle de séparation d'au moins d'au moins (de sorte que nos sous-espaces primitifs sont, au pire, approximativement sans biais par rapport aux sous-espaces dans lesquels l'un des bits est mis à 1).AjEkπ21/poly(n)

  • Si nous n'imposons pas une telle restriction, il me semble qu'admettre des sous-espaces ayant un chevauchement élevé avec serait de toute façon un obstacle à l'approximation de CLIQUE (r); soit nous serions plus ou moins limités à considérer l' absence d'un bord particulier (plutôt que sa présence), soit nous serions obligés d'ignorer complètement l'un des bords. Donc, je ne pense pas qu'il soit terriblement important d'imposer des restrictions à , sauf peut-être que ce sont toutes les images d'un ensemble de projecteurs de navettage, si l'on veut considérer comment "évaluer monotiquement CLIQUE à partir de propositions quantiques simples. ". Au pire, cela reviendrait classiquement à autoriser des portes NON à l'entrée (et à ce que tous les fan-out se produisent après la négation).EkAj

Encore une fois, il n'est pas clair pour moi si le fait de remplacer les ensembles de base par des sous-espaces arbitraires de pose un problème plus intéressant que d'utiliser simplement les sous-espaces ; cependant, si nous nous limitons au cas des formules CNF (dans le cas du navettage ou du non-navettage), les résultats que nous obtenons correspondraient à une certaine notion de complexité d'un hamiltonien sans frustration dont la variété de l'état fondamental consistait en une base standard États représentant des cliques.H2nEj

Niel de Beaudrap
la source
ton croquis me fait réfléchir. existe-t-il un concept de monotonie pour les valeurs complexes? étudiera peut-être un peu plus les vrais circuits arithmétiques. cela pourrait-il être quelque chose de simple comme<? ou pour une porte complexe à deux entrées et comme entrées, sortie,et? |x||y|x1x2y|y|>|x1||y|>|x2|
vzn
Oups, j'ai fait une erreur ... J'ai prévu de donner la prime à Niel, mais j'ai cliqué au mauvais endroit. Je vous dois 200 réputations Niel :).
Gil Kalai
Existe-t-il un moyen de le transmettre à Niel?
Joe Fitzsimons
@Joe, vous pouvez mettre une nouvelle prime sur la question et l'attribuer à Niel.
Kaveh
@Kaveh: D'accord, ça va. Je ne peux pas l'attribuer pendant 24 heures, mais je l'attribuerai alors.
Joe Fitzsimons
7

Comme en témoignent les commentaires de Robin et Tsuyoshi, la notion de circuits monotones semble être facilement extensible aux circuits quantiques.

Afin d'avoir une définition significative du circuit monotone quantique, nous devons choisir un ordre sur les états quantiques par rapport auxquels la monotonie est définie. Classiquement, une option raisonnable (et qui conduit à la notion normale de circuits monotones) est le poids de Hamming, mais considérons un ordre donné par une fonction arbitraire .f

Puisque l'évolution d'un système quantique fermé est unitaire (que nous pouvons supposer donnée par ), alors pour chaque état tel que il existe un état alternatif tel que mais pour lequel , et donc l'évolution n'est pas monotone.U|ψf(U|ψ)>f(|ψ)|ϕf(|ϕ)>f(|ψ)f(U|ψ)>f(U|ϕ)U

Ainsi, les seuls circuits monotones par rapport à sont ceux qui pour tous . Ainsi, tout ensemble de portes monotone par rapport à est composé de portes qui commutent avec .f ( U | ψ ) = f ( | ψ ) | ψ f fff(U|ψ)=f(|ψ)|ψff

Évidemment, les ensembles de portes qui peuvent satisfaire cela dépendent de la définition de . Si est constant, alors tous les ensembles de portes sont monotones par rapport à lui. Cependant, si nous choisissons comme le poids de Hamming des états dans la base de calcul (une extension quelque peu naturelle du utilisé dans le cas classique), nous obtenons une structure intéressante. La restriction imposée exige que le poids de Hamming reste inchangé. Les opérations qui préservent ce montant sont soit des opérations diagonales, soit des SWAP partiels, soit des combinaisons de celles-ci. Cette structure apparaît assez souvent en physique (dans les modèles à liaison étroite, etc.) et est similaire au problème de diffusion du boson étudié par Aaronson et Arkhipovf f fffff, mais pas identique (c'est un problème de diffusion légèrement différent). De plus, il contient des circuits pour IQP et ne devrait donc pas être efficacement simulable de manière classique.

Joe Fitzsimons
la source
1
(1) Je ne pense pas que votre notion de «monotone quantique» soit une généralisation de la notion de monotonie pour les fonctions booléennes classiques. Par exemple, la porte ET est monotone car x_1 ≤ y_1 et x_2 ≤ y_2 impliquent ET (x_1, x_2) ≤ ET (y_1, y_2), où x_1, x_2, y_1, y_2 ∈ {0,1}. Notez que la comparaison se fait entre deux entrées ou entre deux sorties, pas entre l'entrée et la sortie.
Tsuyoshi Ito
(2) Au cas où, je n'ai pas dit que la notion de circuits monotones ne s'étend pas facilement aux circuits quantiques (je n'ai pas dit non plus). Je viens de dire que par rapport au cas des circuits réversibles, où la notion de circuits monotones n'a pas d'intérêt, le cas des circuits quantiques n'est pas clair.
Tsuyoshi Ito
1
@JoeFitzsimons: Je pense que le poids de Hamming figure assez bien dans l'exigence de monotonie, ou (plus précisément) que la propriété de ne pas diminuer lorsque vous "allumez" les bits de zéro à un est précisément l'idée que les informaticiens se soucient de quand ils se réfèrent à des circuits monotones. Vous pouvez envisager des variations dans lesquelles la fonction calculée est une fonction non décroissante de certaines chaînes de bits à valeur réelle, telles que votre proposition de réindexation; mais c'est aussi un écart important par rapport à ce qui intéresse les informaticiens, sauf pour les cas fortement motivés.
Niel de Beaudrap
1
L'ordre partiel habituel sur les chaînes de bits (la comparaison élément par élément) semble beaucoup plus naturel que de les comparer par leurs poids de Hamming, mais si vous pensez que le poids de Hamming est naturel, je ne contesterai pas. Quant au troisième paragraphe, j'ai toujours du mal à suivre votre argument, mais je suppose que je manque quelque chose de simple et j'ai juste besoin d'un peu de temps et d'un regard neuf.
Tsuyoshi Ito
1
@NieldeBeaudrap: Je suis d'accord. Je ne voulais pas suggérer que je pensais autrement.
Joe Fitzsimons
-6

vous posez essentiellement deux questions de difficulté très divergente, à la frontière de deux grands domaines, à savoir les circuits booléens et l'informatique QM, sur la possibilité de ce qu'on appelle parfois un "théorème de pont" en mathématiques:

  • analogique quantique de circuits monotones

  • analogique quantique de Razborovs thm

la réponse courte et franche est non ou pas pour l'instant .

car (1), une question moins difficile, mais encore rarement prise en compte, a fait apparaître la référence suivante qui pourrait être considérée comme un cas connexe dans la littérature.

Dureté d'approximation pour les problèmes quantiques par Gharibian et Kempe

ils considèrent certains problèmes "monotones" dans un contexte quantique, par exemple QMSA, "Quantum Monotone Minimum Satisfying Assignment, QMSA", c'est-à-dire un analogue SAT QM; (également un autre problème de poids minimal monotone quantique Word, QMW) et montrent quelques résultats de dureté d'approximation, c'est-à-dire des limites inférieures. ils ne considèrent pas les circuits quantiques monotones en soi, mais une idée pourrait être qu'un circuit quantique ou un algorithme qui résout la fonction monotone QMSA peut être considéré comme un analogue QM.

quant à (2) ce serait un résultat très avancé s'il existait qu'il ne semble pas "jusqu'ici". Le thm de Razborov est fondamentalement un résultat de type "goulot d'étranglement" de limite inférieure considéré comme une percée distincte et un résultat presque inégalé dans la théorie des circuits (monotone).

Donc, en gros, oui, bien sûr, il y a des goulots d'étranglement à la limite inférieure trouvés dans l'informatique QM, par exemple liés aux théorèmes du produit direct, pour une enquête, voir par exemple

Algorithmes quantiques, limites inférieures et compromis spatio-temporels par Spalek

cependant, sans doute un meilleur QM analogue calculant la borne inférieure mettrait une borne inférieure sur le nombre d' opérations de qubit ou peut-être basé sur des portes "complètes" comme les portes de Toffoli pour une fonction monotone. je ne connais pas de preuves de ce type.

une autre approche pourrait limiter l'analyse à des portes ET et OU quantiques spéciales avec des bits "ancilla" supplémentaires ajoutés pour rendre les portes réversibles.

vzn
la source
ps il est également intéressant de noter que razborovs thm implique ce que l'on appelle parfois des circuits / portes "d'approximateur" et que la dureté d'approximation est probablement / apparemment liée au concept de circuit d'approximateur / porte d'une manière qui n'a pas été cartographiée ....
vzn
6
plutôt que d'ajouter des commentaires, je m'inquiéterais des 7 downvotes ...
Alessandro Cosentino
2
??? coupable jusqu'à preuve du contraire? =)
vzn