Caminada quàntica

Les caminades quàntiques són anàlegs quàntics de les caminades aleatòries clàssiques. En contrast amb la caminada aleatòria clàssica, on el caminant ocupa estats definits i l'aleatorietat sorgeix a causa de transicions estocàstiques entre estats, en les caminades quàntiques l'aleatorietat sorgeix per: (1) superposició quàntica d'estats, (2) evolució unitària reversible i no aleatòria, i (3) col·lapse de la funció d'ona a causa de mesures d'estat.

Distribució de probabilitat resultant de caminades aleatòries unidimensionals en temps discret. La marxa quàntica creada amb la moneda Hadamard es representa (vermell) en comparació amb una caminada clàssica (blau) després de 50 passos de temps.

Igual que amb les caminades aleatòries clàssiques, les caminades quàntiques admeten formulacions tant en temps discret com en temps continu.

Motivació

Les caminades quàntiques estan motivades per l'ús generalitzat de les caminades aleatòries clàssiques en el disseny d'algoritmes aleatoris, i formen part de diversos algorismes quàntics. Per a alguns problemes oraculars, les caminades quàntiques proporcionen una acceleració exponencial respecte a qualsevol algorisme clàssic. Les caminades quàntiques també donen acceleracions polinomials respecte als algorismes clàssics per a molts problemes pràctics, com ara el problema de distinció d'elements, el problema de cerca de triangles, i l'avaluació dels arbres NAND. El conegut algorisme de cerca de Grover també es pot veure com un algorisme de caminada quàntica.

Portes de lògica quàntica basades en caminades quàntiques per a àtoms freds. Implementació d'una porta d'un qubit i una porta de dos qubit.

Relació amb les caminades aleatòries clàssiques

Les caminades quàntiques presenten característiques molt diferents de les caminades aleatòries clàssiques. En particular, no convergeixen a distribucions limitadores i, a causa del poder de la interferència quàntica, es poden estendre significativament més ràpid o més lent que els seus equivalents clàssics.

Temps continu

Els camins quàntics en temps continu sorgeixen quan es substitueix el domini espacial continu de l'equació de Schrödinger per un conjunt discret. És a dir, en comptes de fer que una partícula quàntica es propagui en un continu, es restringeix el conjunt de possibles estats de posició al conjunt de vèrtexs. $V$ d'algun gràfic $G=(V,E)$ que pot ser finit o numerablement infinit. En condicions particulars, les caminades quàntiques en temps continu poden proporcionar un model per a la computació quàntica universal.

Temps discret

L'evolució d'una caminada quàntica en temps discret s'especifica pel producte de dos operadors unitaris: (1) un operador "coin flip" i (2) un operador de canvi condicional, que s'apliquen repetidament. L'exemple següent és instructiu aquí. Imagineu una partícula amb un grau de llibertat d'espín 1/2 propagant-se en una matriu lineal de llocs discrets. Si el nombre d'aquests llocs és infinitament comptable, identifiquem l'espai d'estats amb $\mathbb {Z}$.