# 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.
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.

## 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}$.

## Referències

* ↑ Venegas-Andraca, Salvador E. «Quantum walks: a comprehensive review». Quantum Information Processing, 11, 5, 01-10-2012, pàg. 1015–1106. DOI: 10.1007/s11128-012-0432-5. ISSN: 1570-0755.
* ↑ «Quantum walk | Cirq» (en anglès). https://quantumai.google.+[Consulta: 13 juny 2023].
* ↑ Yan, Zhiguang; Zhang, Yu-Ran; Gong, Ming; Wu, Yulin; Zheng, Yarui «Strongly correlated quantum walks with a 12-qubit superconducting processor» (en anglès). Science, 364, 6442, 24-05-2019, pàg. 753–756. DOI: 10.1126/science.aaw1611. ISSN: 0036-8075.
* ↑ Kempe, Julia «"Quantum random walks – an introductory overview"». Contemporary Physics, 44, 4, 01-07-2003, pàg. 307–327. arXiv: quant-ph/0303081. Bibcode: 2003ConPh..44..307K. DOI: 10.1080/00107151031000110776. ISSN: 0010-7514.