Calcularea Cuantică

2023 Autor: Noah Black | [email protected]. Modificat ultima dată: 2023-08-25 04:39

Acesta este un fișier din arhivele Enciclopediei de Filozofie din Stanford.

Calcularea cuantică

Publicat pentru prima dată la 3 decembrie 2006; revizuire de fond lun 26 februarie 2007

Combinând fizica, matematica și informatica, calculul cuantic s-a dezvoltat în ultimele două decenii de la o idee vizionară la una dintre cele mai fascinante domenii ale mecanicii cuantice. Emoția recentă în acest domeniu viu și speculativ al cercetării a fost declanșată de Peter Shor (1994), care a arătat cum un algoritm cuantic ar putea „accelera” calculul clasic și poate determina numerele mari în primele mult mai rapid (cel puțin în termeni de numărul de pași de calcul implicați) decât orice algoritm clasic cunoscut. Algoritmul lui Shor a fost urmat în curând de câțiva alți algoritmi care au avut ca scop rezolvarea problemelor combinatorii și algebice, iar în ultimii ani, studiul teoretic al sistemelor cuantice care servesc ca dispozitive de calcul a obținut un progres extraordinar. Credința comună spune că punerea în aplicare a Shor 'Algoritmul pe un computer cuantic pe scară largă ar avea consecințe devastatoare pentru protocoalele de criptografie actuale, care se bazează pe premisa că toți algoritmii clasici cunoscuți din cele mai grave cazuri pentru factoring au nevoie de timp exponențial pe lungimea intrării lor (vezi, de exemplu, Preskill 2005). În consecință, experimentaliștii din întreaga lume sunt angajați în încercări imense de a face față dificultăților tehnologice care așteaptă realizarea unui computer cuantic atât de mare. Dar, indiferent dacă aceste probleme tehnologice pot fi depășite (Unruh 1995, Ekert și Jozsa 1996, Haroche și Raimond 1996), este de remarcat că nu există încă o dovadă a superiorității generale a computerelor cuantice față de omologii lor clasici.

Interesul filosofic pentru calculul cuantic este de trei ori: în primul rând, dintr-o perspectivă social-istorică, calculul cuantic este un domeniu în care experimentaliștii se găsesc în fața colegilor lor teoreticieni. Într-adevăr, misterele cuantice, cum ar fi înțelegerea și nonlocalitatea, au fost considerate istoric o chestiune filosofică, până când fizicienii au descoperit că aceste mistere ar putea fi valorificate pentru a concepe noi algoritmi eficienți. Dar, în timp ce tehnologia pentru izolarea a 5 sau chiar 7 cbiti (unitatea de bază a informației din computerul cuantic) este acum la îndemână (Schrader et al. 2004, Knill et al. 2000), există doar o mână de algoritmi cuantici, iar întrebarea dacă acestea pot rezolva problemele de calcul practic intractabile este încă deschisă. În continuare, dintr-o perspectivă mai filozofică,avansurile în calculul cuantic pot produce beneficii fundamentale. Se poate dovedi că capabilitățile tehnologice care ne permit să izolăm sistemele cuantice protejându-le de efectele deceneriei pentru o perioadă suficient de lungă pentru a le manipula ne vor permite, de asemenea, să progresăm în unele probleme fundamentale în fundamentele teoriei cuantice. în sine. Într-adevăr, dezvoltarea și implementarea algoritmilor cuantici eficienți ne pot ajuta să înțelegem mai bine granița dintre fizica clasică și cuantică, elucidând astfel o problemă importantă, și anume, problema de măsurare, care până în prezent rezistă la o soluție. În cele din urmă, ideea că concepte matematice abstracte, cum ar fi complexitatea și (în) tratabilitatea, pot fi traduse nu numai în fizică,dar, de asemenea, rescris de fizică poartă direct caracterul autonom al informaticii și statutul entităților sale teoretice - așa-numitele „tipuri de calcul”. Ca atare, este relevant și pentru dezbaterea filosofică de lungă durată privind relația dintre matematică și lumea fizică.

• 1. Scurt istoric al domeniului

  • 1.1 Teza fizică-îndrumarea bisericii
  • 1.2 „scurtături” fizice de calcul
  • 1.3 Repere

• 2. Bazele

  • 2.1 Qubit-ul
  • 2.2 Porți cuantice
  • 2.3 Circuite cuantice

• 3. Algoritmi cuantici

  • 3.1 Algoritmi pe bază de cuantum

    • 3.1.1 Oracolul Deutsch
    • 3.1.2 Oracolul din Deutsch-Josza
    • 3.1.3 Oracolul Simon
    • 3.1.4 Algoritmul lui Shor
    • 3.1.4 Algoritmul lui Grover
  • 3.2 Algoritmi adiabatici
  • 3.3 Algoritmi pe bază de măsurare
  • 3.4 Algoritmi topologici-cuantici de câmp (TQFT)
  • 3.5 Realizări

• 4. Implicații filosofice

  • 4.1 Ce este Quantum în calculul cuantic?
  • 4.2 Metafizica experimentală
  • 4.3 Există tipuri de calcul?
• Bibliografie
• Alte resurse de internet
• Intrări conexe

1. Scurt istoric al domeniului

1.1 Complexitate fizică de calcul

Modelul matematic pentru un computer „universal” a fost definit cu mult înainte de invenția calculatoarelor și se numește mașina Turing (Turing 1936). O mașină de Turing constă dintr-o bandă nelimitată, un cap care este capabil să citească din casetă și să scrie pe ea și poate ocupa un număr infinit de stări posibile și un tabel de instrucțiuni (o funcție de tranziție). Acest tabel, având în vedere starea inițială a capului și intrarea pe care o citește din banda respectivă, determină (a) simbolul pe care capul îl va scrie pe bandă, (b) starea internă pe care o va ocupa și (c) deplasarea capului pe bandă. În 1936, Turing a arătat că din moment ce se poate codifica tabelul de instrucțiuni al unei mașini Turing T și se poate exprima ca un număr binar # (T),există o mașină de Turing universală U care poate simula tabelul de instrucțiuni al oricărei mașini Turing pe orice intrare dată, cu cel puțin o încetinire polinomială (adică, numărul de pași de calcul solicitați de U pentru a executa programul inițial T pe intrarea inițială va fi delimitat polinomial în # (T)). Că modelul mașinii Turing (ceea ce noi numim astăzi „algoritm”) surprinde conceptul de calcul în integralitatea sa este esența tezei Church-Turing, conform căreia orice funcție eficient calculabilă poate fi calculată folosind o mașină Turing. Desigur, nu a fost găsit niciun contraexemplu pentru această teză (care este rezultatul ideilor convergente de Turing, Post, Kleene și Biserică). Dar întrucât identifică clasa de funcții computabile cu clasa acelor funcții care pot fi calculate folosind o mașină Turing,această teză implică atât o noțiune matematică precisă, cât și o noțiune informală și intuitivă, deci nu poate fi dovedită sau respinsă. Considerații de cardinalitate simple arată, însă, că nu toate funcțiile sunt computabile Turing (setul tuturor mașinilor Turing este contabil, în timp ce setul tuturor funcțiilor de la numerele naturale la numere naturale nu este), iar descoperirea acestui fapt a venit ca o surpriză completă în anii 1930 (Davis 1958).iar descoperirea acestui fapt a venit ca o surpriză completă în anii 1930 (Davis 1958).iar descoperirea acestui fapt a venit ca o surpriză completă în anii 1930 (Davis 1958).

Calculabilitatea sau întrebarea dacă o funcție poate fi calculată nu este singura întrebare care interesează oamenii de informatică. Costul calculării unei funcții are, de asemenea, o importanță deosebită, iar acest cost, cunoscut și sub denumirea de complexitate computațională, este măsurat în mod natural în resursele fizice (de exemplu, timp, spațiu, energie) investite pentru a rezolva problema de calcul. Oamenii de informatică clasifică problemele de calcul în funcție de modul în care funcționează costul lor în funcție de dimensiunea lor de intrare, n, (numărul de biți necesari pentru stocarea intrării) și, în special, dacă crește exponențial sau polinomial cu n. Problemele care pot fi tratate sunt cele care pot fi rezolvate cu costuri polinomiale,în timp ce problemele intractabile sunt cele care pot fi rezolvate doar cu un cost exponențial (soluțiile anterioare sunt de obicei considerate ca fiind eficiente, deși un algoritm de timp exponențial s-ar putea dovedi a fi mai eficient decât un algoritm cu timp polinomial pentru o serie de mărimi de intrare). Dacă relaxăm în continuare cerința ca o soluție la o problemă de calcul să fie întotdeauna corectă și permitem algoritmi probabilistici cu o probabilitate neglijabilă de eroare, putem reduce dramatic costurile de calcul. Algoritmii probabilistici sunt mașini de determinare nedeterministe a căror funcție de tranziție poate modifica aleatoriu configurația capului într-unul din mai multe moduri posibile. Cel mai cunoscut exemplu de algoritm de acest gen este algoritmul probabilistic care decide dacă un număr natural dat este prim într-un număr polinomial de pași (Rabin 1976).

Folosind această noțiune, putem perfecționa în continuare distincția dintre problemele tratabile și cele intractabile. Clasa P (pentru Polinom) este clasa care conține toate problemele de decizie de calcul care pot fi rezolvate de o mașină de Turing deterministă la un cost polinomial. Clasa NP (pentru polinomul nedeterminist) este clasa care conține toate acele probleme de decizie de calcul a căror soluție propusă („ghicită” de către mașina de Turing nedeterministă) poate fi verificată de o mașină Turing deterministă la cost polinomial. Cele mai cunoscute probleme din NP se numesc „ NP-complet . Termenul „complet” desemnează faptul că aceste probleme stau sau se potrivesc: fie ele sunt toate tractabile, fie una dintre ele nu este! Dacă am ști să rezolvăm eficient o problemă completă NP (adică, cu un cost polinomial), am putea rezolva orice problemă din NP doar cu încetinirea polinomială (Cook 1971). Astăzi știm despre sute de exemple de probleme complexe NP (Garey și Johnson 1979), toate reducătoare una la alta în încetinirea polinomială și, deoarece algoritmul cel mai cunoscut pentru oricare dintre aceste probleme este exponențial, conjectura pe scară largă este că nu există un algoritm polinomial care să le poată rezolva. Dar în timp ce în mod clar P ⊆ NP, dovedind sau respingând conjectura că P ≠ NP rămâne poate una dintre cele mai importante întrebări deschise în informatică și teoria complexității.

Deși teza originală a Bisericii Turing a implicat noțiunea matematică abstractă de computabilitate, fizicienii, precum și oamenii de informatică, deseori o interpretează ca spun ceva despre domeniul de aplicare și limitările mașinilor de calcul fizice. De exemplu, Wolfram (1985) susține că orice sistem fizic poate fi simulat (la orice grad de aproximare) de către o mașină Turing universală și că limitele de complexitate ale simulărilor de mașini Turing au o semnificație fizică. De exemplu, dacă calculul energiei minime a unui anumit sistem de n particule necesită cel puțin o creștere exponențială a numărului de pași în n, atunci relaxarea efectivă a acestui sistem la starea sa minimă de energie va avea și un timp exponențial. Aharonov (1998) consolidează această teză (în contextul în care își arată incompatibilitatea putativă cu mecanica cuantică) atunci când spune că o mașină Turing probabilistică poate simula orice dispozitiv fizic rezonabil la costuri polinomiale. Alte exemple pentru această teză pot fi găsite în Copeland (1996). Pentru ca teza fizică a Bisericii Turing să aibă sens, trebuie să raportăm parametrii spațiului și timpului fizicii la omologii lor de calcul: capacitatea memoriei și respectiv numărul de pași de calcul. Există diferite modalități de a face acest lucru, conducând la formulări diferite ale tezei (Pitowsky 1990). De exemplu, se poate codifica setul de instrucțiuni al unei mașini Turing universale și starea benzii sale infinite în dezvoltarea binară a coordonatelor de poziție ale unei singure particule. Prin urmare,se poate „realiza” fizic o mașină de Turing universală ca o bilă de biliard cu oglinzi hiperbolice (Moore 1990, Pitowsky 1996). Pentru cea mai intuitivă conexiune între mașinile Turing abstracte și dispozitivele fizice, vedeți lucrarea de pionierat a lui Gandy (1980), simplificată ulterior de Sieg și Byrnes (1999). Trebuie subliniat că nu există nicio relație între teza inițială a Bisericii Turing și versiunea sa fizică (Pitowsky și Shagrir 2003), iar în timp ce prima privește conceptul de calcul relevant pentru logică (deoarece este puternic legată de noțiunea dovada care necesită validare), aceasta nu implică în mod analitic că toate calculele ar trebui să fie supuse validării. Într-adevăr, există o lungă tradiție istorică a calculelor analogice care folosesc procese fizice continue (Dewdney 1984),iar ieșirea acestor calcule este validată fie prin „rulări” repetitive, fie prin validarea teoriei fizice care se presupune că guvernează comportamentul computerului analog.

1.2 „Scurtături” fizice ale calculului

Există procese fizice care contrazic teza fizică-Turing a Bisericii? În afară de calculul analogic, există cel puțin două contra-exemple la această teză care presupun să arate că noțiunea de recursivitate, sau Turing-computability, nu este o proprietate fizică naturală (Pour-el și Richards 1981, Pitowsky 1990, Hogarth 1994). Deși sistemele fizice implicate (o condiție inițială specifică pentru ecuația de undă în trei dimensiuni și o soluție exotică pentru ecuațiile de câmp, respectiv ale lui Einstein) sunt oarecum conjugate, ultimii ani au văzut apariția școlii înfloritoare de „hipercomputare” care aspiră să extindă exemple limitate de „hipercomputere” fizice și în acest sens, pentru a „calcula” fizic computerele non-Turing (pentru o revizuire a se vedea Copeland 2002; pentru o critică-Davis 2003). Hipercomputarea cuantică este rar discutată în literatura de specialitate (A se vedea, de exemplu, Calude și colab. 2003), dar cea mai concretă încercare de a valorifica teoria cuantică pentru a calcula non-calculabil este sugestia de a utiliza algoritmul adiabatic cuantic (vezi mai jos). A zecea problemă a lui Hilbert (Kieu 2002, 2004) - o problemă Turing-nedecidibilă echivalentă cu problema opririi. Totuși, critici recente au expus caracterul nefizic al presupusului hipercomputer cuantic adiabatic (vezi Smith 2005, Hodges 2005 și Hagar și Korolev 2006).2004) -o problemă Turing-nedecidibilă echivalentă cu problema de oprire. Totuși, critici recente au expus caracterul nefizic al presupusului hipercomputer cuantic adiabatic (vezi Smith 2005, Hodges 2005 și Hagar și Korolev 2006).2004) -o problemă Turing-nedecidibilă echivalentă cu problema de oprire. Totuși, critici recente au expus caracterul nefizic al presupusului hipercomputer cuantic adiabatic (vezi Smith 2005, Hodges 2005 și Hagar și Korolev 2006).

Renunțând la „hipercomputere”, chiar dacă ne limităm doar la funcțiile computabile Turing și ne concentrăm asupra complexității computationale, putem găsi în continuare multe modele fizice care să prezinte „scurtături” în resurse de calcul. Luați în considerare, de exemplu, modelul ADN de calcul care a fost revendicat (Adleman 1994, Lipton 1995) pentru a rezolva problemele complete ale NP în timpul polinomial. O inspecție mai atentă arată că costul calculului din acest model este încă exponențial, deoarece numărul de molecule din sistemul fizic crește exponențial cu dimensiunea problemei. Sau luați o soluție presupusă instantaneu la un alt NP-problema completă folosind o construcție de tije și bile (Vergis et.al. 1986) care, din păcate, ignoră întârzierile acumulate în tijele rigide, care au ca rezultat o încetinire generală exponențială. Un alt exemplu este simularea fizică a factorizării numerelor în prime care folosește doar resurse polinomiale în timp și spațiu, dar necesită o precizie în creștere exponențială. Astfel, se pare că toate aceste modele nu pot servi drept contra-exemple la teza fizică a Bisericii Turing (în ceea ce privește complexitatea), deoarece toate necesită o anumită resursă fizică exponențială. Rețineți, însă, că toate aceste modele se bazează pe fizica clasică, de unde și întrebarea inevitabilă:Poate trecerea la fizica cuantică ne permite să găsim „scurtături” în resursele de calcul? Căutarea computerului cuantic a început cu posibilitatea de a da un răspuns pozitiv la această întrebare.

1.3 Repere

Ideea unui dispozitiv de calcul bazat pe mecanica cuantică a fost explorată deja în anii ’70 de fizicieni și informaticieni. Încă din 1969, Steven Wiesner a sugerat procesarea cuantică a informațiilor ca o modalitate posibilă de a îndeplini mai bine sarcinile criptologice. Dar primele patru lucrări publicate cu privire la informații cuantice (Wiesner a publicat doar în 1983), aparțin lui Alexander Holevo (1973), RP Poplavskii (1975), Roman Ingarden (1976) și Yuri Manin (1980). Sunt cunoscute mai bine contribuțiile aduse la începutul anilor 1980 de către Charles H. Bennett la IBM Thomas J. Watson Research Center, Paul A. Benioff din Argonne Laboratorul Național din Illinois, David Deutsch de la Universitatea din Oxford și regretatul Richard P. Feynman a Institutului de Tehnologie din California. Ideea a apărut când oamenii de știință investigau limitele fizice fundamentale ale calculului. Dacă tehnologia continua să respecte „Legea lui Moore” (observația făcută în 1965 de Gordon Moore, co-fondator al Intel, că numărul tranzistorilor pe centimetru pătrat pe circuitele integrate s-a dublat la fiecare 18 luni de la inventarea circuitului integrat), apoi mărimea în continuă scădere a circuitelor ambalate pe cipuri de siliciu ar ajunge în cele din urmă la un punct în care elementele individuale nu ar fi mai mari decât câțiva atomi. Dar, deoarece legile fizice care guvernează comportamentul și proprietățile circuitului putativ la scara atomică sunt de natură mecanică cuantică, nu clasice, a apărut întrebarea firească dacă un nou tip de computer ar putea fi conceput pe baza principiilor fizicii cuantice. Dacă tehnologia continua să respecte „Legea lui Moore” (observația făcută în 1965 de Gordon Moore, co-fondator al Intel, că numărul tranzistorilor pe centimetru pătrat pe circuitele integrate s-a dublat la fiecare 18 luni de la inventarea circuitului integrat), apoi mărimea în continuă scădere a circuitelor ambalate pe cipuri de siliciu ar ajunge în cele din urmă la un punct în care elementele individuale nu ar fi mai mari decât câțiva atomi. Dar, deoarece legile fizice care guvernează comportamentul și proprietățile circuitului putativ la scara atomică sunt de natură mecanică cuantică, nu clasice, a apărut întrebarea firească dacă un nou tip de computer ar putea fi conceput pe baza principiilor fizicii cuantice. Dacă tehnologia continua să respecte „Legea lui Moore” (observația făcută în 1965 de Gordon Moore, co-fondator al Intel, că numărul tranzistorilor pe centimetru pătrat pe circuitele integrate s-a dublat la fiecare 18 luni de la inventarea circuitului integrat), apoi mărimea în continuă scădere a circuitelor ambalate pe cipuri de siliciu ar ajunge în cele din urmă la un punct în care elementele individuale nu ar fi mai mari decât câțiva atomi. Dar, deoarece legile fizice care guvernează comportamentul și proprietățile circuitului putativ la scara atomică sunt de natură mecanică cuantică, nu clasice, a apărut întrebarea firească dacă un nou tip de computer ar putea fi conceput pe baza principiilor fizicii cuantice.că numărul tranzistorilor pe centimetru pătrat pe circuitele integrate s-a dublat la fiecare 18 luni de la inventarea circuitului integrat), atunci mărimea în scădere continuă a circuitelor ambalate pe cipuri de siliciu ar ajunge în cele din urmă la un punct în care elementele individuale nu vor fi mai mari decât câteva atomi. Dar, deoarece legile fizice care guvernează comportamentul și proprietățile circuitului putativ la scara atomică sunt de natură mecanică cuantică, nu clasice, a apărut întrebarea firească dacă un nou tip de computer ar putea fi conceput pe baza principiilor fizicii cuantice.că numărul tranzistorilor pe centimetru pătrat pe circuitele integrate s-a dublat la fiecare 18 luni de la inventarea circuitului integrat), atunci mărimea în scădere continuă a circuitelor ambalate pe cipuri de siliciu ar ajunge în cele din urmă la un punct în care elementele individuale nu vor fi mai mari decât câteva atomi. Dar, deoarece legile fizice care guvernează comportamentul și proprietățile circuitului putativ la scara atomică sunt de natură mecanică cuantică, nu clasice, a apărut întrebarea firească dacă un nou tip de computer ar putea fi conceput pe baza principiilor fizicii cuantice.apoi mărimea în continuă scădere a circuitelor ambalate pe cipuri de siliciu ar ajunge în cele din urmă la un punct în care elementele individuale nu ar fi mai mari decât câțiva atomi. Dar, deoarece legile fizice care guvernează comportamentul și proprietățile circuitului putativ la scara atomică sunt de natură mecanică cuantică, nu clasice, a apărut întrebarea firească dacă un nou tip de computer ar putea fi conceput pe baza principiilor fizicii cuantice.apoi mărimea în continuă scădere a circuitelor ambalate pe cipuri de siliciu ar ajunge în cele din urmă la un punct în care elementele individuale nu ar fi mai mari decât câțiva atomi. Dar, deoarece legile fizice care guvernează comportamentul și proprietățile circuitului putativ la scara atomică sunt de natură mecanică cuantică, nu clasice, a apărut întrebarea firească dacă un nou tip de computer ar putea fi conceput pe baza principiilor fizicii cuantice.

Feynman a fost printre primii care au încercat să ofere un răspuns la această întrebare, producând un model abstract în 1982 care a arătat cum un sistem cuantic ar putea fi utilizat pentru a face calcule. El a explicat, de asemenea, cum o astfel de mașină ar putea acționa ca un simulator pentru fizica cuantică. De asemenea, Feynman a conceput că orice computer clasic care va fi exploatat pentru această sarcină va face acest lucru doar ineficient, suportând o încetinire exponențială a timpului de calcul. În 1985, David Deutsch a propus prima mașină de curare cuantică universală și a deschis calea către modelul circuitului cuantic. Domeniul tânăr și înfloritor a atras atenția filozofilor. În 1983, David Albert a arătat modul în care un automat mecanic cuantic se comportă în mod remarcabil diferit de un automat automat,iar în 1990, Itamar Pitowsky a ridicat întrebarea dacă principiul superpoziției va permite soluționarea calculatoarelor cuantice NP- probleme complete. El a subliniat, de asemenea, că, deși, în principiu, s-ar putea „stoarce” informațiile de complexitate exponențială în polinomial multe stări cuantice, problema reală constă în regăsirea eficientă a acestor informații.

Progresul în algoritmii cuantici a început în anii 1990, odată cu descoperirea oracolului Deutsch-Josza (1992) și a oracolului lui Simon (1994). Acesta din urmă a furnizat baza algoritmului Shor pentru factoring. Publicat în 1994, acest algoritm a marcat o „tranziție de fază” în dezvoltarea computerelor cuantice și a stârnit un interes extraordinar chiar și în afara comunității fizice. În acel an, prima realizare experimentală a porții CNOT cuantice cu ioni prinși a fost propusă de Cirac și Zoller (1995). În 1995, Peter Shor și Andrew Steane au propus (independent) prima schemă pentru corectarea cuantică a erorilor. În același an, prima realizare a unei porți logice cuantice s-a făcut în Boulder, Colorado, după propunerea lui Cirac și Zoller.

În 1996, Lov Grover de la Bell Labs a inventat algoritmul de căutare cuantică, care produce o „accelerare” quadratică în comparație cu omologul său clasic. Un an mai târziu a fost propus primul model RMN pentru calculul cuantic, bazat pe tehnici de rezonanță magnetică nucleară. Această tehnică a fost realizată în 1998 cu un registru pe 2 cbite și a fost scalată până la 7 biți în Laboratorul Național Los Alamos în 2000.

Începând cu anul 2000, domeniul a înregistrat o creștere exponențială. Au apărut noi paradigme ale algoritmilor cuantici, cum ar fi algoritmi adiabatici, algoritmi bazați pe măsurare și algoritmi bazați pe teorie de câmpuri cuantice topologice, precum și noi modele fizice pentru realizarea unui computer cuantic la scară largă cu capcane cu ioni reci, optică cuantică (folosind fotoni și cavitate optică), sisteme de materii condensate și fizica stării solide (între timp, primul model RMN s-a dovedit a fi un punct mort în ceea ce privește scalarea; vezi DiVicenzo 2000). Întrebările de bază rămân totuși deschise și astăzi: (1) teoretic, algoritmii cuantici pot rezolva eficient probleme clasice intractabile? (2) operațional, putem realiza de fapt un computer cuantic la scară largă pentru a rula acești algoritmi?

2. Bazele

În această secțiune vom trece în revistă paradigma de bază pentru algoritmi cuantici, și anume modelul de circuit cuantic, care este compus din unitățile de bază cuantice de informații (qubit) și manipulările logice de bază ale acestora (porți cuantice).

2.1 Qubit-ul

Qubit-ul este analogul cuantic al bitului, unitatea clasică de informație fundamentală. Este un obiect matematic cu proprietăți specifice care poate fi realizat fizic în mai multe moduri diferite ca un sistem fizic real. La fel cum bitul clasic are o stare (fie 0, fie 1), un qubit are și o stare. Totuși, contrar bitului clasic,

și

1 nu

sunt decât două stări posibile ale qubit-ului și orice combinație liniară (superpoziție) este de asemenea posibilă din punct de vedere fizic. În general, astfel, starea fizică a unui qubit este superpoziția

ψ

= α

+ β

(unde α și β sunt numere complexe). Starea unui qubit poate fi descrisă ca un vector într-un spațiu Hilbert bidimensional, un spațiu vector complex (vezi intrarea asupra mecanicii cuantice). Stările speciale

și

sunt cunoscute sub numele de stări de bază de calcul și formează o bază ortonormală pentru acest spațiu vectorial. Conform teoriei cuantice, atunci când încercăm să măsurăm qubitul în această bază pentru a determina starea acesteia, obținem

cu probabilitate

α

² sau

cu probabilitate

β

². Deoarece

α

² +

β

² = 1 (adică, qubit-ul este un vector de unitate în starea Hilbert bidimensională menționată anterior), putem (ignorând factorul de fază general) să scriem efectiv starea sa ca

ψ

= cos (θ)

+ e ^{i φ} sin (θ)

unde numerele θ și φ definesc un punct din sfera tridimensională a unității, așa cum se arată aici. Această sferă este adesea numită sferă Bloch și oferă un mijloc util pentru a vizualiza starea unui singur qubit.

Sfera Bloch

Teoretic, un singur qubit poate stoca o cantitate infinită de informații, totuși, atunci când este măsurată, dă numai rezultatul clasic (0 sau 1) cu anumite probabilități specificate de starea cuantică. Cu alte cuvinte, măsurarea schimbă starea qubit-ului, „prăbușindu-l” din superpoziție într-unul dintre termenii săi. Punctul crucial este că, dacă nu se măsoară qubit-ul, informația „ascunsă” pe care o păstrează este conservată sub evoluția dinamică (și anume ecuația lui Schrödinger). Această caracteristică a mecanicii cuantice permite manipularea informațiilor stocate în cablurile nemăsurate cu porți cuantice și este una dintre sursele puterii putative a calculatoarelor cuantice.

Pentru a vedea de ce, să presupunem că avem la dispoziție două pături. Dacă acestea ar fi biți clasici, atunci ei ar putea fi în patru stări posibile (00, 01, 10, 11). Corespunzător, o pereche de qubits are patru stări de bază de calcul (

00

,

01

,

10

,

11

). Dar, în timp ce un singur registru clasic pe doi biți poate stoca aceste numere doar unul câteodată, o pereche de chit-uri poate exista și într-o superpoziție a acestor patru stări de bază, fiecare cu un coeficient complex propriu (al cărui pătrat mod, fiind interpretat ca probabilitate, este normalizat). Atâta timp cât sistemul cuantic evoluează unitar și nu este măsurat, toate cele patru stări posibile sunt simultan „stocate” într-un singur registru cuantic de două qubituri. Mai general, cantitatea de informații care poate fi stocată într-un sistem de n qubits nemăsurați crește exponențial în n. Totuși, sarcina dificilă este de a prelua aceste informații eficient.

2.2 Porți cuantice

Porțile de calcul clasice sunt porți logice booleane care efectuează manipulări ale informațiilor stocate în biți. În calculul cuantic aceste porți sunt reprezentate de matrici și pot fi vizualizate sub forma unor rotații ale stării cuantice pe sfera Bloch. Această vizualizare reprezintă faptul că porțile cuantice sunt operatori unitari, adică păstrează norma stării cuantice (dacă U este o matrice care descrie o singură poartă qubit, atunci U ^† U = I, unde U ^†este adiacenta lui U, obținută prin transpunerea și apoi complexul-conjugarea U). Ca și în cazul calculului clasic, unde există o poartă universală (a cărei combinație poate fi utilizată pentru a calcula orice funcție computabilă), și anume, poarta NAND care rezultă din efectuarea unei porți AND și apoi a unei porți NU, în calculul cuantic s-a arătat (Barenco și colab., 1995) că orice poartă logică cu qubit multiplu poate fi compusă dintr-o poartă cuantică CNOT (care funcționează pe o mai bună qubit prin răsturnarea sau păstrarea bitului țintă având în vedere starea bitului de control, o operație analogă. la XOR clasic, adică poarta OR exclusivă) și porți cu un singur qubit. O caracteristică a porților cuantice care le distinge de porțile clasice este că sunt reversibile: inversa unei matrici unitare este, de asemenea, o matrice unitară,și astfel o poartă cuantică poate fi întotdeauna inversată de o altă poartă cuantică.

Poarta CNOT

Porțile unitare manipulează informațiile stocate în registrul cuantic și, în acest sens, evoluția cuantică (unitară) obișnuită poate fi considerată ca un calcul (DiVicenzo 1995 a arătat cum un set mic de porți cu un singur qubit și o poartă cu două qubituri este universal, în sensul că un circuit combinat din acest set poate aproxima la o exactitate arbitrară orice transformare unitară a n qubit). Pentru a citi rezultatul acestui calcul, trebuie totuși măsurat registrul cuantic. Poarta de măsurare este o poartă neunitară care „prăbușește” suprapunerea cuantică din registru pe unul dintre termenii săi cu probabilitatea corespunzătoare. De obicei această măsurare se face în baza de calcul, dar din moment ce mecanica cuantică permite unul să exprime o stare arbitrară ca o combinație liniară de stări de bază,cu condiția ca statele să fie ortonormale (o condiție care asigură normalizarea), în principiu, se poate măsura registrul în orice bază ortonormă arbitrară. Totuși, acest lucru nu înseamnă că măsurătorile în diferite baze sunt echivalente în mod eficient. Într-adevăr, una dintre dificultățile de a construi algoritmi cuantici eficienți rezultă exact din faptul că măsurarea prăbușește starea, iar unele măsurători sunt mult mai complicate decât altele.iar unele măsurători sunt mult mai complicate decât altele.iar unele măsurători sunt mult mai complicate decât altele.

2.3 Circuite cuantice

Circuitele cuantice sunt similare cu circuitele computerizate clasice, deoarece constau din fire și porți logice. Firurile sunt utilizate pentru a transporta informația, în timp ce porțile o manipulează (rețineți că firele nu corespund firelor fizice; ele pot corespunde unei particule fizice, unui foton, care se deplasează dintr-o locație în alta în spațiu sau chiar în timp. -evoluţie). În mod convențional, intrarea circuitului cuantic se presupune a fi o stare de bază computațională, de obicei starea constând din toate

. Starea de ieșire a circuitului este apoi măsurată în baza de calcul sau în orice altă bază ortonormă arbitrară. Primii algoritmi cuantici (adică Deutsch-Jozsa, Simon, Shor și Grover) au fost construiți în această paradigmă. Există astăzi paradigme suplimentare pentru calculul cuantic, care diferă de modelul circuitului cuantic în multe moduri interesante. Până acum, cu toate acestea, toate s-au dovedit a fi echivalente din punct de vedere al calculului modelului de circuit (vezi mai jos), în sensul că orice problemă de calcul care poate fi rezolvată de modelul de circuit poate fi rezolvată de aceste noi modele cu doar o polinomie deasupra capului în resurse de calcul.

3. Algoritmi cuantici

Proiectarea algoritmului este o sarcină extrem de complicată, iar în calculul cuantic devine și mai complicat datorită încercărilor de a valorifica caracteristicile mecanice cuantice pentru a reduce complexitatea problemelor de calcul și pentru a „accelera” calculul. Înainte de a ataca această problemă, ar trebui să ne convingem mai întâi că computerele cuantice pot fi utilizate pentru a efectua calcule standard, clasice, fără nici o „accelerare”. Într-un anumit sens, acest lucru este evident, având în vedere credința în caracterul universal al mecanicii cuantice și observația că orice calcul cuantic care este diagonală în baza de calcul, adică, nu implică nicio interferență între qubits, este efectiv clasic. Cu toate acestea, demonstrația potrivit căreia circuitele cuantice pot fi utilizate pentru a simula circuitele clasice nu este simplă (reamintim că primele sunt reversibile, în timp ce celelalte folosesc porți care sunt in mod ireversibil). Într-adevăr, circuitele cuantice nu pot fi utilizate direct pentru a simula calculul clasic, dar acesta din urmă poate fi totuși simulat pe un computer cuantic folosind o poartă intermediară, respectiv poarta Toffoli. Această poartă are trei biți de intrare și trei biți de ieșire, dintre care doi sunt biți de control, neafectați de acțiunea porții. Al treilea bit este un bit țintă care este rătăcit dacă ambii biți de control sunt reglați la 1 și altfel este lăsat singur. Această poartă este reversibilă (inversa sa este ea însăși) și poate fi folosită pentru a simula toate elementele circuitului ireversibil clasic cu unul reversibil. Prin urmare,folosind versiunea cuantică a porții Toffoli (care, prin definiție, permite stările de bază computaționale în mod similar cu poarta Toffoli clasică), se poate simula, deși destul de obositor, porțile logice clasice ireversibile cu cele reversibile cuantice. Calculatoarele cuantice sunt astfel capabile să efectueze orice calcul pe care un computer clasic determinist îl poate face.

Ce zici de calculul nedeterminist? Nu este surprinzător, un computer cuantic poate simula și acest tip de calcul folosind o altă poartă cuantică faimoasă, și anume poarta Hadamard, care primește ca intrare starea

și produce starea (

+

) / √2. Măsurarea acestei stări de ieșire produce

sau

cu probabilitate 50/50, care poate fi utilizată pentru a simula o lansare corectă a monedelor.

Poarta Hadamard

Evident, dacă algoritmii cuantici ar putea fi folosiți doar pentru a simula algoritmi clasici, atunci avansarea tehnologică în stocarea și manipularea informațiilor, încapsulată în „legea lui Moore”, ar avea doar consecințe banale asupra teoriei complexității computationale, lăsând-o pe cea din urmă neafectată de lumea fizică. Dar, în timp ce unele probleme de calcul vor rezista întotdeauna la „accelerarea” cuantică (în aceste probleme, timpul de calcul depinde de intrare, iar această caracteristică va duce la o încălcare a unitarității, deci la un calcul clasic eficient chiar și pe un computer cuantic - vezi Myers 1997 și Linden și Popescu 1998), speranța este, totuși, că algoritmii cuantici pot să nu simuleze doar cei clasici, ci că îi vor depăși de fapt pe aceștia din urmă în unele cazuri,și, în acest sens, ajută la redefinirea noțiunilor abstracte de tractabilitate și intractabilitate și încalcă teza fizică a Bisericii Turing, cel puțin în ceea ce privește complexitatea de calcul.

3.1 Algoritmi pe bază de cuantum

Primii algoritmi cuantici au fost proiectați pentru a exploata adecvarea calculului cuantic la problemele de calcul care implică oracole. Oracolele sunt dispozitive care sunt folosite pentru a răspunde la întrebări cu un simplu sau nu. Întrebările pot fi la fel de elaborate pe cât le poate face, procedura care răspunde la întrebări poate fi lungă și se pot genera multe date auxiliare în timp ce se răspunde la întrebare. Totuși, tot ceea ce iese din oracol este doar da sau nu. Arhitectura oracol este foarte potrivită pentru calculatoarele cuantice. Motivul pentru aceasta este că, așa cum am subliniat mai sus, citirea unui sistem cuantic este probabilistică. Prin urmare, dacă se pune o întrebare, răspunsul la care este dat sub forma unei stări cuantice, va trebui să efectueze calculul pe un ansamblu de calculatoare cuantice pentru a ajunge oriunde. Pe de altă parte, dacă calculul poate fi proiectat astfel încât să obțină da sau nu într-o singură măsurătoare (și poate fi necesară o reducere a datelor pentru a realiza acest lucru), atunci un singur computer cuantic și o singură calculare cuantică pot fi sunt suficiente.

3.1.1 Oracolul Deutsch

Acest oracol (Deutsch 1989) răspunde la următoarea întrebare. Să presupunem că avem o funcție ƒ: {0,1} → {0,1}, care poate fi constantă sau echilibrată. În acest caz, funcția este constantă dacă ƒ (0) = ƒ (1) și este echilibrată dacă ƒ (0) ≠ ƒ (1). Clasic ar fi nevoie de două evaluări ale funcției pentru a spune dacă este una sau alta. Cuantum, putem răspunde la această întrebare într-o singură evaluare. Motivul acestei reduceri de complexitate este, din nou, principiul superpoziției. Pentru a vedea de ce să ia în considerare următorul algoritm cuantic. Se poate pregăti qubit-urile de intrare ale oracolului Deutsch ca superpoziție (

+

) / √2 (folosind poarta Hadamard pe

) și superpoziție (

-

) / √2 (folosind poarta Hadamard pe

). Oracolul este implementat cu un circuit cuantic care ia intrări precum

x, y

până

x, y ⊕ƒ (x)

unde ⊕ este adaosul modulului doi, ceea ce face exact o poartă XOR. Primul qubit al ieșirii acestui oracol este apoi introdus într-o poartă Hadamard, iar ieșirea finală a algoritmului este starea

±

ƒ (0) ⊕ƒ (1)

([

-

] / √2).

Deoarece ƒ (0) ⊕ƒ (1) este 0 dacă funcția este constantă și 1 dacă funcția este echilibrată, o singură măsurare a primului qubit al ieșirii este suficientă pentru a prelua răspunsul la întrebarea dacă funcția este constantă sau echilibrată. Cu alte cuvinte, putem distinge într-o rundă a algoritmului între cele două disjuncții cuantice fără a afla valorile de adevăr ale disjuncțiilor în sine.

3.1.2 Oracolul din Deutsch-Jozsa

Acest oracol (Deutsch și Jozsa 1992) generalizează oracolul Deutsch la o funcție ƒ: {0,1} ⁿ→ {0,1}. Ne punem aceeași întrebare: funcția este constantă sau echilibrată. Aici echilibrat înseamnă că funcția este 0 la jumătate din argumentele sale și 1 la cealaltă jumătate. Desigur, în acest caz, funcția nu poate fi nici constantă, nici echilibrată. În acest caz, oracolul nu funcționează: Poate spune da sau nu, dar răspunsul va fi lipsit de sens. Tot aici algoritmul permite evaluarea unei proprietăți globale a funcției într-o singură măsură, deoarece starea de ieșire este o superpoziție a stărilor echilibrate și constante astfel încât stările echilibrate se află toate într-un subspaț ortogonal față de stările constante și, prin urmare, pot fi diferențiate de acesta din urmă într-o singură măsurătoare. În schimb, cel mai bun algoritm clasic determinist ar necesita 2 ⁿ / 2 + 1 întrebări la oracol pentru a rezolva această problemă.

3.1.3 Oracolul Simon

Să presupunem că avem o funcție booleană ƒ: {0,1} ⁿ → {0,1} ⁿ. Funcția se presupune a fi de la 2 la 1, adică pentru fiecare valoare a lui ƒ există întotdeauna două x ₁ și x ₂ astfel încât ƒ (x ₁) = ƒ (x ₂). Funcția este, de asemenea, ar trebui să fie periodic, ceea ce înseamnă că există un vector binar un astfel încât ƒ (x ⊕ a) = ƒ (x), unde ⊕ desemnează plus modulo 2, adică 1 ⊕ 1 = 0. Simon oracle se întoarce perioada a într-un număr de măsurători liniare în n, care este exponențial mai rapid decât orice algoritm clasic (Simon 1994). Oracolul lui Simon se reduce la oracolul Deutsch XOR atunci când n = 2, și poate fi considerat într-adevăr ca o extensie a acestuia din urmă, în sensul că o proprietate globală a unei funcții, în acest caz perioada sa, poate fi evaluată într-un număr eficient de măsurători., având în vedere că starea de ieșire a algoritmului este descompusă în subspații ortogonale, doar unul dintre acestea conține soluția problemei, prin urmare, măsurători repetate în baza de calcul vor fi suficiente pentru a determina acest subspațiu. Cu alte cuvinte, oracolul lui Simon este încă un exemplu în care un algoritm cuantic poate evalua o disjuncție fără a determina valoarea de adevăr a disjuncțiilor. Pentru mai multe despre analiza logică a acestor primi algoritmi bazați pe circuitul cuantic, vezi Bub (2006b).

3.1.4 Algoritmul lui Shor

Cele trei oracole tocmai descrise, deși demonstrează superioritatea potențială a computerelor cuantice față de omologii lor clasici, se ocupă totuși de probleme de calcul aparent lipsite de importanță. Într-adevăr, este îndoielnic dacă domeniul de cercetare al calculului cuantic ar fi atras atâta atenție și ar fi evoluat la statutul său actual dacă meritul său ar putea fi demonstrat doar cu aceste probleme. Dar în 1994, după ce a realizat că oracolul lui Simon poate fi valorificat pentru a rezolva o problemă mult mai interesantă și crucială, și anume factoringul, care se află în centrul actualelor protocoale criptografice precum RSA (Rivest 1978), Peter Shor a transformat calculul cuantic în unul dintre cele mai interesante domenii de cercetare în mecanica cuantică.

Algoritmul lui Shor (1994) exploatează argumentul teoretic al numărului ingenios potrivit căruia doi factori primi p, q ai unui număr întreg pozitiv N = pq pot fi găsiți determinând perioada unei funcții ƒ (x) = y ^x mod N, pentru orice y <N care nu are factori comuni cu N alt decât 1 (Nielsen și Chuang 2000, App. 4). Perioada r din ƒ (x) depinde de y și N. Odată ce se cunoaște perioada, se poate face un factor N dacă r este egal și y ^{r / 2} ≠ −1 mod N, care va fi cazul împreună cu o probabilitate mai mare de 1/2 pentru orice y ales aleator (dacă nu, unul alege altul valoarea lui y și încearcă din nou). Factorii lui N sunt cei mai mari divizori comuni ai y ^{r / 2}± 1 și N, care pot fi găsite în timp polinomial folosind binecunoscutul algoritm euclidian. Cu alte cuvinte, rezultatul remarcabil al lui Shor se bazează pe descoperirea că problema factoringului se reduce la problema găsirii perioadei unei anumite funcții periodice ƒ: Z _n → Z _N, unde Z _n este grupul aditiv al numerelor întregi mod n (Notă că ƒ (x) = y ^x mod N astfel încât ƒ (x + r) = ƒ (x) dacă x + r ≤ n. Funcția este periodică dacă r împarte exact n, altfel este aproape periodică). Că această problemă poate fi rezolvată eficient printr-un computer cuantic se demonstrează cu oracolul lui Simon.

Rezultatul lui Shor este cel mai dramatic exemplu de până acum în ceea ce privește „accelerarea” cuantică a calculului, în ciuda faptului că factorul de factorizare se crede a fi doar în NP și nu în NP- complet. Pentru a verifica dacă n este prim, se efectuează un număr de pași care este un polinom în jurnalul ₂ n (codarea binară a unui număr natural n necesită log ₂n resurse). Dar nimeni nu știe să modifice numerele în prime în timp polinomial, nici măcar pe o mașină Turing probabilistică, iar cei mai buni algoritmi clasici pe care îi avem pentru această problemă sunt subexponențiali. Aceasta este încă o problemă deschisă în teoria complexității computaționale. Criptografia modernă și securitatea internetului se bazează pe aceste două fapte: Este ușor să găsiți rapid numere mari mari și este greu să factorizați numere mari compuse într-un timp rezonabil. Multe protocoale precum cheia publică și semnătura electronică se bazează pe aceste fapte (Giblin 1993). Descoperirea că calculatoarele cuantice pot rezolva factorizarea în timpul polinomial a avut, prin urmare, un efect dramatic. Implementarea algoritmului pe o mașină fizică va avea consecințe economice, dar și științifice.

3.1.5 Algoritmul lui Grover

Să presupunem că ai întâlnit pe cineva care i-a ținut numele secret, dar i-ai dezvăluit numărul de telefon. Puteți afla numele ei folosind numărul și un director de telefon? În cel mai rău caz, dacă există n intrări în director, resursele de calcul necesare vor fi liniare în n. Grover (1996) a arătat cum această sarcină, și anume căutarea unei baze de date nestructurate, ar putea fi realizată cu un algoritm cuantic cu complexitatea ordinului √ n. De acord, această „accelerare” este mai modestă decât Shor, deoarece căutarea unei baze de date nestructurate aparține clasei P, însă, contrar cazului lui Shor, în care complexitatea clasică a factoringului este încă necunoscută, aici superioritatea algoritmului cuantic, oricât de modestă, este cu siguranță probabilă. Că această „accelerare” cvadratică este, de asemenea, optimizarea cuantică optimă posibilă pentru această problemă a fost dovedită de Bennett, Bernstein, Brassard și Vazirani (1997).

Deși scopul algoritmului Grover este de obicei descris ca „căutarea unei baze de date”, poate fi mai exact să-l descriem ca „inversarea unei funcții”. Aproximativ vorbind, dacă avem o funcție y = f (x) care poate fi evaluată pe un computer cuantic, algoritmul lui Grover ne permite să calculăm x când este dat y. Inversarea unei funcții este legată de căutarea unei baze de date, deoarece am putea veni cu o funcție care produce o anumită valoare de y dacă x se potrivește cu o intrare dorită într-o bază de date și o altă valoare de y pentru alte valori de x. Aplicațiile acestui algoritm sunt de anvergură (de mai multe ori găsind numele misterului „data” de mai sus). De exemplu, poate fi utilizat pentru a determina eficient numărul de soluții la o problemă de căutare N-titem, deci pentru a efectua căutări exhaustive pe o clasă de soluții la un NP-completează problema și reduce substanțial resursele de calcul necesare pentru rezolvarea acesteia.

3.2 Algoritmi adiabatici

Au trecut mai mult de un deceniu de la descoperirea primului algoritm cuantic, dar până acum nu s-au făcut progrese cu privire la „Sfântul Graal” în rezolvarea unui NP-problema completă cu un model cu circuit cuantic. Așa cum am subliniat mai sus, algoritmul lui Shor se află singur în „accelerarea” sa exponențială, cu toate că nu există un algoritm clasic eficient pentru factoring, nu există nici o dovadă că un astfel de algoritm nu există sau nu poate exista. În anul 2000, un grup de fizicieni de la MIT și Universitatea Northeastern (Farhi și colab. 2000) au propus o paradigmă nouă pentru calculul cuantic care diferă de modelul circuitului în mai multe moduri interesante. Scopul lor a fost să încerce să rezolve cu acest algoritm o instanță de satisfacție - decizia dacă o propunere din calculul propozițional are o atribuire de adevăr satisfăcătoare - care este una dintre cele mai cunoscute probleme complete NP (Cook 1971).

Conform teoremei adiabatice (de exemplu, Messia 1961) și având în vedere anumite condiții specifice, un sistem cuantic rămâne în starea sa cea mai scăzută de energie, cunoscută sub denumirea de stare solă, de-a lungul unei transformări adiabatice în care sistemul este deformat lent și lin dintr-un hamiltonian inițial. la un Hamiltonian final (ca ilustrare, gândiți-vă să mutați un bebeluș care doarme într-un leagăn din camera de zi în dormitor. Dacă tranziția se face încet și suficient de lin, iar dacă copilul este adormit, atunci va fi rămâi adormit pe toată durata tranziției). Cea mai importantă condiție în această teoremă este decalajul energetic dintre starea solară și următoarea stare excitată (în analogia noastră, acest decalaj reflectă cât de sonor este copilul adormit). Fiind invers proporțional cu timpul de evoluție T, acest decalaj îl controlează pe acesta din urmă. Dacă acest decalaj există pe întreaga evoluție (adică nu există o trecere de nivel între stările energetice ale sistemului), teorema dictează că în limita adiabatică (atunci când T → ∞) sistemul va rămâne în starea sa de bază. În practică, desigur, T este întotdeauna finit, dar cu cât este mai lung, cu atât este mai puțin probabil ca sistemul să se abată de la starea sa de bază în timpul evoluției timpului.

Punctul principal al algoritmului adiabatic cuantic care se bazează pe teorema adiabatică constă în posibilitatea codificării unei instanțe specifice a unei anumite probleme de decizie într-un anumit hamiltonian (acest lucru se poate face prin valorificarea faptului că se știe că orice problemă de decizie poate fi derivat dintr-o problemă de optimizare prin încorporarea într-o legătură numerică ca parametru suplimentar). Unul pornește apoi sistemul într-o stare de sol a unui alt hamiltonian care este ușor de construit și evoluează lent sistemul în timp, deformându-l spre hamiltonianul dorit. În conformitate cu teorema cuantică adiabatică și având în vedere condiția de decalaj, rezultatul unui astfel de proces fizic este o altă stare de bază energetică care codifică soluția problemei de decizie dorită. Algoritmul adiabatic este astfel un algoritm mai degrabă „retras”:nu este nevoie decât să pornească sistemul în starea sa de sol, să îl deformeze adiabatic și să măsoare starea finală la sol pentru a prelua rezultatul dorit. Dar dacă acest algoritm dă sau nu „accelerarea” dorită, depinde în mod crucial de comportamentul decalajului de energie pe măsură ce numărul de grade de libertate în sistem crește. Dacă acest decalaj scade exponențial cu dimensiunea intrării, atunci timpul de evoluție al algoritmului va crește exponențial; dacă decalajul scade polinomial, problema deciziei astfel codată ar putea fi rezolvată eficient în timp polinomial. Deși fizicienii studiază lacunele spectrale de aproape un secol, nu au făcut-o niciodată cu calculul cuantic în minte. Modul în care se comportă acest decalaj în general rămâne până acum o întrebare empirică deschisă.și măsurați starea finală a solului pentru a prelua rezultatul dorit. Dar dacă acest algoritm dă sau nu „accelerarea” dorită, depinde în mod crucial de comportamentul decalajului de energie pe măsură ce numărul de grade de libertate în sistem crește. Dacă acest decalaj scade exponențial cu dimensiunea intrării, atunci timpul de evoluție al algoritmului va crește exponențial; dacă decalajul scade polinomial, problema deciziei astfel codată ar putea fi rezolvată eficient în timp polinomial. Deși fizicienii studiază lacunele spectrale de aproape un secol, nu au făcut-o niciodată cu calculul cuantic în minte. Modul în care se comportă acest decalaj în general rămâne până acum o întrebare empirică deschisă.și măsurați starea finală a solului pentru a prelua rezultatul dorit. Dar dacă acest algoritm dă sau nu „accelerarea” dorită, depinde în mod crucial de comportamentul decalajului de energie pe măsură ce numărul de grade de libertate în sistem crește. Dacă acest decalaj scade exponențial cu dimensiunea intrării, atunci timpul de evoluție al algoritmului va crește exponențial; dacă decalajul scade polinomial, problema deciziei astfel codată ar putea fi rezolvată eficient în timp polinomial. Deși fizicienii studiază lacunele spectrale de aproape un secol, nu au făcut-o niciodată cu calculul cuantic în minte. Modul în care se comportă acest decalaj în general rămâne până acum o întrebare empirică deschisă. Dar dacă acest algoritm dă sau nu „accelerarea” dorită, depinde în mod crucial de comportamentul decalajului de energie pe măsură ce numărul de grade de libertate în sistem crește. Dacă acest decalaj scade exponențial cu dimensiunea intrării, atunci timpul de evoluție al algoritmului va crește exponențial; dacă decalajul scade polinomial, problema deciziei astfel codată ar putea fi rezolvată eficient în timp polinomial. Deși fizicienii studiază lacunele spectrale de aproape un secol, nu au făcut-o niciodată cu calculul cuantic în minte. Modul în care se comportă acest decalaj în general rămâne până acum o întrebare empirică deschisă. Dar dacă acest algoritm dă sau nu „accelerarea” dorită, depinde în mod crucial de comportamentul decalajului de energie pe măsură ce numărul de grade de libertate în sistem crește. Dacă acest decalaj scade exponențial cu dimensiunea intrării, atunci timpul de evoluție al algoritmului va crește exponențial; dacă decalajul scade polinomial, problema deciziei astfel codată ar putea fi rezolvată eficient în timp polinomial. Deși fizicienii studiază lacunele spectrale de aproape un secol, nu au făcut-o niciodată cu calculul cuantic în minte. Modul în care se comportă acest decalaj în general rămâne până acum o întrebare empirică deschisă.dacă decalajul scade polinomial, problema deciziei astfel codată ar putea fi rezolvată eficient în timp polinomial. Deși fizicienii studiază lacunele spectrale de aproape un secol, nu au făcut-o niciodată cu calculul cuantic în minte. Modul în care se comportă acest decalaj în general rămâne până acum o întrebare empirică deschisă.dacă decalajul scade polinomial, problema deciziei astfel codată ar putea fi rezolvată eficient în timp polinomial. Deși fizicienii studiază lacunele spectrale de aproape un secol, nu au făcut-o niciodată cu calculul cuantic în minte. Modul în care se comportă acest decalaj în general rămâne până acum o întrebare empirică deschisă.

Algoritmul adiabatic cuantic păstrează multă promisiune (Farhi și colab., 2001) și, recent, s-a arătat (Aharonov și colab., 2004) a fi echivalent polinomial la modelul circuitului (adică fiecare model poate simula celălalt doar cu polinom, adică, modestă, cheltuieli generale de resurse, și anume, numărul de cabluri și pași de calcul), dar avertismentul care este uneori menționat este faptul că aplicarea sa la o problemă de calcul intractabilă poate necesita uneori rezolvarea unei alte, ca o sarcină intractabilă (această problemă generală a fost prima dată ridicat de un filozof! vezi Pitowsky 1990). Într-adevăr, Reichardt (2004) a arătat că există probleme simple pentru care algoritmul se va bloca într-un minim local, în care există exponențial multe valori proprii, toate exponențial apropiate de energia stării solului, deci aplicând teorema adiabatică,chiar și pentru aceste probleme simple, va dura timp exponențial și ne întoarcem la unul pătrat.

3.3 Algoritmi pe bază de măsurare

Algoritmii pe baza măsurătorilor diferă de modelul circuitului, prin faptul că, în loc să aplice evoluția unitară ca mecanism de bază pentru manipularea informațiilor, acești algoritmi folosesc doar măsuri neunitare ca pași de calcul. Aceste modele sunt deosebit de interesante dintr-o perspectivă fundamentală, deoarece nu au analogi clasici evidenti și pentru că oferă o perspectivă nouă asupra rolului înțelegerii în calculul cuantic (Jozsa 2005). De asemenea, pot avea consecințe interesante pentru considerente experimentale, ceea ce sugerează un alt tip de arhitectură computerizată care este mai tolerantă la erori (Nielsen și Dawson 2004).

Algoritmii bazați pe măsurare se încadrează în două categorii. Primul este calculul cuantic de teleportare (bazat pe o idee a lui Gottesman și Chuang 1999, și dezvoltat într-un model de calcul de Nielsen 2003 și Leung 2003). Al doilea este „computerul cuantic unic”, cunoscut și sub denumirea de modelul „cluster state” (Raussendorf și Briegel 2000). Caracteristica interesantă a acestor modele este aceea că sunt capabile să reprezinte dinamica cuantică arbitrară, inclusiv dinamica unitară, cu măsurători de bază neunitare. Măsurătorile sunt efectuate pe un grup de stări extrem de încurcate (cantitatea de încurcătură necesară este încă în litigiu) și sunt adaptative, adică fiecare măsurare se face într-o bază diferită, care este calculată clasic, având în vedere rezultatul măsurării anterioare (primul model folosește măsurători de 2 sau mai multe cbiti,în timp ce cel de-al doilea folosește doar măsurători cu un singur qubit; în primul model se folosește numai încurcarea bi-partită, în timp ce în cel de-al doilea are o înțelegere cu mai multe părți pe toate știfturile). Astfel de modele exotice pot părea redundante, mai ales atunci când s-a demonstrat că sunt polinomial echivalente cu modelul de circuit standard din punct de vedere al complexității computaționale (Raussendorf și colab., 2003). Totuși, meritul lor constă în lecțiile fundamentale pe care le conduc acasă: cu aceste modele separarea între partea clasică (adică, calculul următoarei baze de măsurare) și părțile cuantice (adică măsurarea și stările încurcate) ale calculul devine evident, prin urmare, poate fi mai ușor să identificăm resursele cuantice care sunt responsabile pentru „accelerarea” putativă.în primul model se folosește numai încurcarea bi-partită, în timp ce în cel de-al doilea are o înțelegere cu mai multe părți pe toate știfturile). Astfel de modele exotice pot părea redundante, mai ales atunci când s-a demonstrat că sunt polinomial echivalente cu modelul de circuit standard din punct de vedere al complexității computaționale (Raussendorf și colab., 2003). Totuși, meritul lor constă în lecțiile fundamentale pe care le conduc acasă: cu aceste modele separarea între partea clasică (adică, calculul următoarei baze de măsurare) și părțile cuantice (adică măsurarea și stările încurcate) ale calculul devine evident, prin urmare, poate fi mai ușor să identificăm resursele cuantice care sunt responsabile pentru „accelerarea” putativă.în primul model se folosește numai încurcarea bi-partită, în timp ce în cel de-al doilea are o înțelegere cu mai multe părți pe toate știfturile). Astfel de modele exotice pot părea redundante, mai ales când s-a demonstrat că sunt polinomial echivalente cu modelul de circuit standard din punct de vedere al complexității computaționale (Raussendorf și colab., 2003). Totuși, meritul lor constă în lecțiile fundamentale pe care le conduc acasă: cu aceste modele separarea între partea clasică (adică, calculul următoarei baze de măsurare) și părțile cuantice (adică măsurarea și stările încurcate) ale calculul devine evident, prin urmare, poate fi mai ușor să identificăm resursele cuantice care sunt responsabile pentru „accelerarea” putativă. Astfel de modele exotice pot părea redundante, mai ales când s-a demonstrat că sunt polinomial echivalente cu modelul de circuit standard din punct de vedere al complexității computaționale (Raussendorf și colab., 2003). Totuși, meritul lor constă în lecțiile fundamentale pe care le conduc acasă: cu aceste modele separarea între partea clasică (adică, calculul următoarei baze de măsurare) și părțile cuantice (adică măsurarea și stările încurcate) ale calculul devine evident, prin urmare, poate fi mai ușor să identificăm resursele cuantice care sunt responsabile pentru „accelerarea” putativă. Astfel de modele exotice pot părea redundante, mai ales atunci când s-a demonstrat că sunt polinomial echivalente cu modelul de circuit standard din punct de vedere al complexității computaționale (Raussendorf și colab., 2003). Totuși, meritul lor constă în lecțiile fundamentale pe care le conduc acasă: cu aceste modele separarea între partea clasică (adică, calculul următoarei baze de măsurare) și părțile cuantice (adică măsurarea și stările încurcate) ale calculul devine evident, prin urmare, poate fi mai ușor să identificăm resursele cuantice care sunt responsabile pentru „accelerarea” putativă.cu aceste modele, separarea dintre partea clasică (adică, calculul următoarei baze de măsurare) și părțile cuantice (adică, măsurarea și stările încurcate) ale calculului devine evidentă, prin urmare, poate fi mai ușor să identificăm cuantumul resurse care sunt responsabile pentru „accelerarea” putativă.cu aceste modele, separarea dintre partea clasică (adică, calculul următoarei baze de măsurare) și părțile cuantice (adică, măsurarea și stările încurcate) ale calculului devine evidentă, prin urmare, poate fi mai ușor să identificăm cuantumul resurse care sunt responsabile pentru „accelerarea” putativă.

3.4 Algoritmi topologici-cuantici de câmp (TQFT)

Un alt model exotic pentru calculul cuantic care atrage multă atenție în ultima perioadă, în special din partea Microsoft inc. (Freedman 1998), este modelul Teoriei topologice a câmpului cuantic. Spre deosebire de modelul de circuit simplu și standard, acest model se află în cele mai abstracte domenii ale fizicii teoretice. Sistemele fizice exotice pe care TQFT le descrie sunt stări topologice ale materiei. Că formalismul TQFT poate fi aplicat la probleme de calcul a fost arătat de Witten (1989), iar ideea a fost dezvoltată ulterior de către alții. De asemenea, aici s-a dovedit că modelul a fost simulat eficient pe un computer cuantic standard (Freedman, Kitaev, Wang 2000, Aharonov și colab. 2005), dar meritul său constă în toleranța sa ridicată la erori care rezultă din orice posibilă realizare a unui cuant la scară largă. computer (vezi mai jos). Topologia este utilă în special aici, deoarece multe proprietăți topologice globale sunt, prin definiție, invariante sub deformare și având în vedere că majoritatea erorilor sunt locale, informațiile codificate în proprietăți topologice sunt puternice împotriva lor.

3.5 Realizări

Calculatorul cuantic ar putea fi visul teoreticianului, dar în ceea ce privește experimentaliștii, realizarea lui este un coșmar. Problema este că, deși unele prototipuri ale celor mai simple elemente necesare construirii unui computer cuantic au fost deja implementate în laborator, este încă o întrebare deschisă cum să combini aceste elemente în sisteme scalabile. Algoritmul lui Shor poate rupe codul RSA, dar va rămâne o anecdotă dacă cel mai mare număr pe care îl poate factoriza este 15. În modelul bazat pe circuit, problema este realizarea unui sistem cuantic scalabil care să permită în același timp (1) reprezintă în mod robust informațiile cuantice, (2) realizează o familie universală de transformare unitară, (3) pregătesc o stare inițială fiduciară și (4) măsoară rezultatul rezultatului. Paradigme alternative pot schimba unele dintre aceste cerințe cu altele,dar aspectul va rămâne același, adică, ar trebui să obținem controlul sistemului cuantic, astfel încât sistemul să rămână „cuantic”, deși macroscopic sau chiar mesoscopic în dimensiunile sale.

Au fost concepute mai multe soluții ingenioase pentru primele două cerințe de mai sus, inclusiv coduri cuantice de corectare a erorilor (Shor 1995) și calcul tolerant la erori (Shor și DiVicenzo 1996, Aharonov și Ben-Or 1997) care reduc dramatic răspândirea erorilor în timpul unui „zgomotos” calculul cuantic Problema se află însă în ultimele două cerințe. Dacă se speră să se rezolve eficient probleme dificile cu un computer cuantic scalabil, atunci pregătirea stării de intrare și măsurarea stării de ieșire trebuie realizate astfel încât să nu crească complexitatea calculului. Cu alte cuvinte, dacă construcția operatorului teoretic care măsoară o stare cuantică care codifică o soluție la o problemă completă NP necesită un timp exponențial, sau chiar rezolvarea încăProblema completă NP, atunci nu a câștigat nimic reprezentând această soluție într-o stare cuantică.

4. Implicații filosofice

4.1 Ce este Quantum în calculul cuantic?

În pofida entuziasmului din jurul descoperirii algoritmului lui Shor și în afară de problema aproape insurmontabilă a realizării și implementării practic a unui computer cuantic la scară largă, rămâne deschisă o întrebare teoretică crucială și anume, ce resurse fizice sunt responsabile pentru puterea putativă a calculării cuantice? Altfel spus, care sunt caracteristicile esențiale ale mecanicii cuantice care permit rezolvarea problemelor sau simularea anumitor sisteme mult mai eficient decât pe un computer clasic? Remarcabil este și faptul că relevanța caracteristicilor de obicei considerate esențiale pentru superioritatea computerelor cuantice, de exemplu, înțelegerea și interferența (Josza 1997), a fost recent pusă sub semnul întrebării (Linden și Popescu 1999, Biham 2004). Mai mult, chiar dacă aceste caracteristici joacă un rol esențial în „viteza” cuantică putativă,încă nu este clar cum fac acest lucru (Fortnow 2003).

Teoretic, după cum pare, întrebarea „ce este cuantic în calculul cuantic?” are o consecință practică enormă. Una dintre jenele calculului cuantic este faptul că, până în prezent, a fost descoperit un singur algoritm, respectiv Shor, pentru care un computer cuantic este semnificativ mai rapid decât oricare clasic cunoscut. Este aproape sigur că unul dintre motivele acestei deficiențe de algoritmi cuantici este legat de lipsa de înțelegere a ceea ce face un calcul cuantic cuantic (a se vedea, de asemenea, Preskill 1998 și Shor 2004). Ca răspuns final la această întrebare, am dori să avem ceva similar cu celebrul teorem al lui Bell (1964), adică o afirmație succintă și crocantă a diferenței fundamentale dintre sistemele cuantice și cele clasice, încapsulată în caracterul necomutativ al observabililor. Calculatoare cuantice, din păcate,nu par să permită o asemenea simplă caracterizare. Observabilele - în modelul cuantic cuantic există doar două, pregătirea stării inițiale și observarea stării finale, în aceeași bază și a aceleiași variabile, la sfârșitul calculului - nu sunt la fel de importante aici ca în cazul lui Bell, deoarece orice măsurătoare se deplasează cu ea însăși. Noncomutativitatea în calculul cuantic se află mult mai adânc și încă nu se știe cum să o încasați în monedă utilă. Scepticii calculului cuantic (Levin 2003) valorifică fericit acest puzzle: Dacă nimeni nu știe de ce computerele cuantice sunt superioare celor clasice, cum putem fi siguri că sunt, într-adevăr, superiori?pregătirea stării inițiale și observarea stării finale, în aceeași bază și a aceleiași variabile, la sfârșitul calculului - nu sunt la fel de importante aici ca în cazul lui Bell, deoarece orice măsurare începe cu ea însăși. Noncomutativitatea în calculul cuantic se află mult mai adânc și încă nu se știe cum să o încasați în monedă utilă. Scepticii calculului cuantic (Levin 2003) valorifică fericit acest puzzle: Dacă nimeni nu știe de ce computerele cuantice sunt superioare celor clasice, cum putem fi siguri că sunt, într-adevăr, superiori?pregătirea stării inițiale și observarea stării finale, în aceeași bază și a aceleiași variabile, la sfârșitul calculului - nu sunt la fel de importante aici ca în cazul lui Bell, deoarece orice măsurare începe cu ea însăși. Noncomutativitatea în calculul cuantic se află mult mai adânc și încă nu se știe cum să o încasați în monedă utilă. Scepticii calculului cuantic (Levin 2003) valorifică fericit acest puzzle: Dacă nimeni nu știe de ce computerele cuantice sunt superioare celor clasice, cum putem fi siguri că sunt, într-adevăr, superiori?Scepticii calculului cuantic (Levin 2003) valorifică fericit acest puzzle: Dacă nimeni nu știe de ce computerele cuantice sunt superioare celor clasice, cum putem fi siguri că sunt, într-adevăr, superiori?Scepticii calculului cuantic (Levin 2003) valorifică fericit acest puzzle: Dacă nimeni nu știe de ce computerele cuantice sunt superioare celor clasice, cum putem fi siguri că sunt, într-adevăr, superiori?

Caracterul evaziv al resursei fizice responsabile de „accelerarea” cuantică poate fi demonstrat frumos cu următorul exemplu. Luați în considerare o soluție a unei probleme de decizie, să zicem satisfacția, cu un algoritm cuantic bazat pe modelul circuitului. Ceea ce ni se oferă aici ca input este o propunere în calculul propozițional și trebuie să decidem dacă are o atribuire de adevăr satisfăcătoare. Așa cum arată Pitowsky (2002), algoritmul cuantic pare să rezolve această problemă testând toate cele 2 ⁿ misiuni „deodată”, totuși acest „miracol” cuantic ne ajută foarte puțin, deoarece orice măsurare efectuată pe starea de ieșire o prăbușește și dacă există este o posibilă atribuire de adevăr care rezolvă această problemă de decizie, probabilitatea de a o prelua este 2 ^{- n}la fel ca în cazul unei mașini de Turing probabilistică clasică care ghicește soluția și apoi o verifică. Concluzia lui Pitowsky este că pentru a îmbunătăți calculul cu mecanica cuantică trebuie să construim superpoziții „inteligente” care să crească probabilitatea de a recupera cu succes rezultatul mult mai mult decât cel al unei presupuneri pure. Algoritmul lui Shor și clasa algoritmilor care evaluează o proprietate globală a unei funcții (această clasă este cunoscută drept clasa de algoritmi subgrup ascunsă) sunt (până în prezent) un exemplu unic atât de construcție a unei astfel de superpoziții „inteligente”, cât și de regăsire a soluția în timp polinomial. Algoritmul adiabatic cuantic ne poate oferi rezultate similare, în funcție de existența unui decalaj de energie care scade polinomial cu intrarea.

Această întrebare ridică, de asemenea, probleme importante despre cum se poate măsura complexitatea unui algoritm cuantic dat. Răspunsul diferă, desigur, în funcție de modelul respectiv. În modelul adiabatic, de exemplu, nu trebuie decât să estimăm comportamentul decalajului de energie și relația acestuia cu dimensiunea de intrare (codată în numărul de grade de libertate al hamiltonianului sistemului). În modelul bazat pe măsurători, se numără numărul de măsurători necesare pentru a dezvălui soluția care este ascunsă în starea clusterului de intrare (deoarece pregătirea stării de cluster este un proces polinomial, nu se adaugă la complexitatea calculului). Dar în modelul de circuit lucrurile nu sunt la fel de simple. Dupa toate acestea,ansamblul calculului bazat pe circuitul cuantic poate fi reprezentat simplu ca o transformare unitară unică de la starea de intrare la starea de ieșire.

Această caracteristică a modelului circuitului cuantic acceptă conjectura că puterea computerelor cuantice, dacă există, nu se află în dinamica cuantică (adică în ecuația Schrödinger), ci mai degrabă în starea cuantică sau în funcția de undă. Un alt argument în favoarea acestei conjecturi este faptul că subspațiul Hilbert „vizitat” în timpul unui proces de calcul cuantic este, în orice moment, un spațiu liniar acoperit de toți vectorii din spațiul total Hilbert care au fost creați prin procesul de calcul până la acel moment. Dar acest subspaț Hilbert este, așadar, un subspațiu acoperit de un număr polinomial de vectori și este, astfel, cel mult un subspaț polinomial al spațiului total Hilbert. O simulare clasică a evoluției cuantice pe un spațiu Hilbert cu un număr polinomial de dimensiuni (adicăUn spațiu Hilbert acoperit de un număr de vectori de bază, care este polinomial în numărul de cabluri implicate în calcul), poate fi efectuat într-un număr polinomial de calcule clasice. Dacă dinamica cuantică a fost unicul ingredient responsabil pentru eficiența calculului cuantic, acesta din urmă ar putea fi imitat într-un număr polinomial de pași cu un computer clasic (vezi, de exemplu, Vidal 2003).

Asta nu înseamnă că calculul cuantic nu este mai puternic decât calculul clasic. Punctul cheie, desigur, este că nu se încheie un calcul cuantic cu o superpoziție arbitrară, ci vizează un stat foarte special, „inteligent”, de a folosi termenul Pitowsky. Calculele cuantice nu pot fi întotdeauna mimate cu un computer clasic, deoarece caracterizarea subspațiului de calcul al anumitor stări cuantice este dificilă și se pare că aceste stări cuantice speciale, „inteligente”, nu pot fi reprezentate clasic ca vectori derivați printr-o calculare cuantică în o bază optimă sau cel puțin aceea nu poate face acest lucru în așa fel încât să permită unuia să calculeze rezultatul măsurării finale efectuate pe aceste stări.

În consecință, în modelul de circuit cuantic, ar trebui să numărăm numărul de etape de calcul în calcul nu prin numărarea numărului de transformări ale statului, ci prin numărarea numărului de transformări locale cu un sau două qubit care sunt necesare pentru crearea ' superpoziție inteligentă care asigură „accelerarea” dorită. (Rețineți că algoritmul lui Shor, de exemplu, implică trei pași majori în acest context: În primul rând, unul creează starea „inteligentă” încurcată cu un set de transformări unitare. Rezultatul calculului - o proprietate globală a unei funcții - este acum” ascuns 'în această stare; în al doilea rând, pentru a prelua acest rezultat, unul îl proiectează pe un subspațiu al spațiului Hilbert și, în final, se execută un alt set de transformări unitare pentru a face rezultatul măsurabil în baza de calcul originală. Toate aceste etape contează ca pași de calcul în ceea ce privește eficiența algoritmului. Vedeți și Bub 2006a.) Trucul este să efectuați aceste transformări locale de unu sau două qubituri în timp polinomial și este probabil să fie aici unde se poate găsi puterea fizică a calculului cuantic.

4.2 Metafizica experimentală?

Revoluția informațiilor cuantice a determinat mai mulți fizicieni și filozofi să pretindă că noile cunoștințe pot fi obținute din noua știință în creștere în probleme conceptuale în fundamentele mecanicii cuantice (Fuchs 2002, Bub 2005). Cu toate acestea, în timp ce una dintre cele mai cunoscute probleme fundamentale în mecanica cuantică, și anume problema măsurării cuantice, rămâne nesoluționată chiar și în teoria informațiilor cuantice (vezi Hagar 2003 și Hagar și Hemmo 2006 pentru o critică a abordării teoretice a informațiilor cuantice la fundamentele mecanicii cuantice și rolul problemei de măsurare cuantică în acest context), teoreticienii informațiilor cuantice o resping ca o chestiune filosofică (Fuchs 2002). Într-adevăr, în teoria informațiilor cuantice, conceptul de „măsurare” este luat ca un primitiv,o „casetă neagră” care rămâne neanalizată (a se vedea Dickson 2005 (Alte resurse de Internet) pentru o discuție despre această vedere în contextul computerului cuantic „unidirecțional”). Problema de măsurare în sine, în plus, este considerată o neînțelegere a teoriei cuantice. Dar progrese recente în realizarea unui computer cuantic la scară largă pot dovedi în cele din urmă teoreticieni informații cuantice greșite: În loc să susțină respingerea problemei de măsurare cuantică, aceste progrese pot duce surprinzător la soluția empirică. Dar progrese recente în realizarea unui computer cuantic la scară largă pot dovedi în cele din urmă teoreticieni informații cuantice greșite: În loc să susțină respingerea problemei de măsurare cuantică, aceste progrese pot duce surprinzător la soluția empirică. Dar progrese recente în realizarea unui computer cuantic la scară largă pot dovedi în cele din urmă teoreticieni informații cuantice greșite: În loc să susțină respingerea problemei de măsurare cuantică, aceste progrese pot duce surprinzător la soluția empirică.

Ideea speculativă este următoarea. După cum se dovedește, teoriile de colaps - o formă de alternative la teoria cuantică, care au ca scop rezolvarea problemei de măsurare, modifică ecuația lui Schrödinger și dau predicții diferite din teoria cuantică în anumite circumstanțe specifice. Aceste circumstanțe pot fi realizate, în plus, dacă efectele de decidență ar putea fi suprimate (Bassi și colab., 2005). Unul dintre cele mai dificile obstacole care așteaptă construcția unui computer cuantic la scară largă este rezistența sa împotriva efectelor de decernare (Unruh 1995). Astfel, se pare că capabilitățile tehnologice necesare pentru realizarea unui computer cuantic pe scară largă sunt exact acelea pe care distincția dintre „adevărat” și „fals” se prăbușește (Pearle 1998), adică, între teoriile prăbușirii și decoherența indusă de mediu.. În consecință, în timp ce calculul cuantic poate elucida distincția esențială între fizica cuantică și cea clasică, realizarea ei fizică ar arunca lumină și asupra uneia dintre problemele conceptuale de lungă durată din fundamentele teoriei și ar servi ca un alt exemplu de metafizică experimentală (termenul a fost creat de Abner Shimony pentru a desemna lanțul de evenimente care a dus de la argumentul EPR prin teorema lui Bell la experimentele lui Aspect).și ar servi ca un alt exemplu de metafizică experimentală (termenul a fost creat de Abner Shimony pentru a desemna lanțul de evenimente care a dus de la argumentul EPR prin teorema lui Bell la experimentele lui Aspect).și ar servi ca un alt exemplu de metafizică experimentală (termenul a fost creat de Abner Shimony pentru a desemna lanțul de evenimente care a dus de la argumentul EPR prin teorema lui Bell la experimentele lui Aspect).

4.3 Există tipuri de calcul?

O altă implicație filosofică a realizării unui computer cuantic la scară largă privește dezbaterea de lungă durată din filosofia minții cu privire la autonomia teoriilor computationale ale minții (Fodor 1974). În trecerea de la inteligența artificială puternică la slabă, susținătorii acestei opinii au încercat să impună constrângeri pe programele de calculator înainte ca aceștia să poată fi calificați ca teorii ale științei cognitive (Pylyshyn 1984). Aceste constrângeri includ, de exemplu, natura realizărilor fizice ale simbolurilor și relațiile dintre calculele simbolice abstracte și procesele cauzale fizice care le execută. Căutarea caracteristicii de calcul a acestor teorii, adică pentru ceea ce le face teorii computationale ale minții, a implicat izolarea unor caracteristici ale computerului ca atare. Cu alte cuvinte,susținătorii AI slabe căutau proprietăți de calcul sau tipuri, care să fie independente de mașină, cel puțin în sensul că nu ar fi asociate cu constituția fizică a computerului și nici cu modelul specific de mașină care se folosea. Aceste caracteristici au fost considerate instrumentale în dezbaterile din știința cognitivă, de exemplu, dezbaterea dintre funcționalism și conexionism (Fodor și Pylyshyn 1988).

Rețineți, însă, că, odată încălcată teza fizică-Turing a Bisericii, unele noțiuni de calcul încetează să fie autonome. Cu alte cuvinte, având în vedere că calculatoarele cuantice pot fi capabile să rezolve eficient problemele nepracticabile din punct de vedere clasic, prin urmare, re-descrie spațiul abstract al complexității computationale, concepte de calcul și chiar tipuri de calcul, cum ar fi „un algoritm eficient” sau „clasa NP”, devin dependente de mașină, iar recurgerea la „hardware” va deveni inevitabilă în orice analiză a acesteia.

Progresele în calculul cuantic pot astfel să contravină viziunii funcționaliste despre caracterul nefizic al tipurilor și proprietăților care sunt utilizate în informatică. De fapt, aceste tipuri și categorii pot deveni fizice ca urmare a acestei dezvoltări naturale în fizică (de exemplu, calculul cuantic, teoria haosului). În consecință, algoritmi cuantici eficienți pot servi, de asemenea, ca contraexemple pentru argumente a priori împotriva reducționismului (Pitowsky 1996).

Bibliografie

• Adleman, LM (1994), „Calcul molecular al soluțiilor la problemele combinatorii”, Science, 266: 1021–1024.
• Aharonov, D. (1998), „Quantum computing”, Revizuirea anuală a fizicii computaționale, VI, Singapore: World Scientific. [Amprentă disponibilă online].
• Aharonov, D. și Ben-Or, M. (1997), „Calcul tolerant la erori cu eroare constantă”, Proc. Simpozion ACM privind teoria calculului (STOC), 176-188.
• Albert, D. (1983), „Cu privire la automatele mecanice cuantice”, Phys. Lett., A 98: 249.
• Barenco, A. și colab. (1995), „Porți elementare pentru calculul cuantic”, Phys. Rev., A 52: 3457–3467.
• Bell, JS (1964), „Pe paradoxul lui Einstein Podolsky Rosen”, Fizică, 1: 195–200.
• Bennett, C. și colab. (1997), „Punctele tari și punctele slabe ale calculării cuantice”, SIAM Journal on Computing, 26 (5): 1510-1523.
• Biham, E., și colab. (2004), „Calcularea cuantică fără înțelegere”, Teoretica Calculatoare, 320: 15–33.
• Bub, J. (2005), „Mecanica cuantică este despre informații cuantice”, Foundations of Physics, 34: 541–560.
• Cirac, JI și Zoller, P. (1995), „Calcule cuantice cu ioni prinși la rece”, Phys. Rev. Lett., 74: 4091–4094.
• Copeland, J. (2002), „Hypercomputation”, Minți și mașini, 12: 461–502.
• Cook, SA (1971), „Complexitatea procedurilor care dovedesc teorema”, Proc. Al treilea simpozion ACM despre teoria calculului, 151-158.
• Davis, M. (1958), The undecidable, New York: Dover.
• Davis, M. (2003), „Mitul hipercomputării”, în C. Teuscher (ed.), Alan Turing, Viața și moștenirea unui mare gânditor, New York: Springer, pp. 195-212.
• Deutsch, D. (1985), „Teoria cuantică, principiul Bisericii Turing și computerul cuantic universal”, Proc. Roy. Soc. Lond., A 400: 97–117.
• Deutsch, D. și Jozsa, R. (1992), „Soluția rapidă a problemelor prin computerul cuantic”, Proc. Roy. Soc. Lond, A 439: 553–558.
• Dewdney AK (1984), „Pe computerul spaghetti și alte gadgeturi analogice pentru rezolvarea problemelor”, Scientific American, 250 (6): 19–26.
• DiVicenzo, D. (1995), „Porțile cu două biți sunt universale pentru calculul cuantic”, Phys. Rev., A 51: 1015–1022.
• Ekert, A. și Jozsa, R. (1996), „Calculul cuantic și algoritmul de factorizare al lui Shor”, Rev. Mod. Phys., 68 (3): 733–753.
• Farhi, E. și colab. (2001), „Un algoritm de evoluție adiabatică cuantică aplicat instanțelor aleatorii ale unei probleme complete NP”, Science, 292 (5516): 472-475.
• Feynman, R. (1982), „Simularea fizicii cu calculatoarele”, International Journal of Theoretical Physics, 21: 467–488.
• Fodor, J. (1974), „Științe speciale”, Synthese, 2: 97–115.
• Fodor, J. și Pylyshyn, Z. (1988), „Connectionism și arhitectură cognitivă, o analiză critică”, Cognition, 28: 3–71.
• Fortnow, L. (2003), „The complexist's view of the quantist computing quantum”, Theoretical Computer Science, 292: 597–610.
• Freedman, M. (1998), „P / NP and the quantum field computer”, Proc. Natl. Acad. Sci., 95: 98–101.
• Gandy, R. (1980), „Teza și principiile Bisericii pentru mecanisme”, în J. Barwise și colab. (eds.), Simpozionul Kleene, Amsterdam: Olanda de Nord, pp. 123-148.
• Garey, MR și Johnson, DS (1979), Calculatoare și intractabilitate: Un ghid către teoria completitudinii NP, New York: WH Freeman.
• Giblin, P. (1993), Primes and Programming, Cambridge, Cambridge University Press.
• Gottesman, D. și Chuang, I. (1999), „Demonstrarea viabilității calculului cuantic universal folosind teleportare și operații cu un singur qubit”, Nature, 402: 390-393.
• Grover, L. (1996), „Un algoritm mecanic cuantic rapid pentru căutarea în baze de date”, Proc. 28 simp ACM. Teoria informaticii, 212-219.
• Hagar, A. (2003), „Un filosof privește teoria informațiilor cuantice”, Philosophy of Science, 70: 752–775.
• Hagar, A. și Hemmo, M. (2006), „Explicarea celor neobservate: De ce mecanica cuantică nu se referă doar la informații”, Foundations of Physics, 36 (9): 1295-1324
• Hagar, A. și Korolev, A. (2006), „Hypercomputability Quantum?”, Minți și Mașini, 16 (1): 87–93.
• Haroche, S. și Raimond, JM (1996), „Calcularea cuantică: Vis sau coșmar?”, Physics Today, 8: 51–52.
• Hogarth, M. (1994), „Calculatoare non-Turing și computabilitate non-Turing”, PSA, 94 (1): 126–138.
• Holevo, AS (1973), „Limite pentru cantitatea de informații transmise de un canal cuantic de comunicare”, Problemy Peredachi Informatsii, 9 (3): 3–11. Traducere din engleză în Probleme of Transmission Information, 9: 177-183, 1973.
• Ingarden, RS (1976), „Teoria informațiilor cuantice”, Rep. Matematica. Phys., 10: 43–72.
• Jozsa, R. (1997), „Încordarea și calculul cuantic”, cap. 27 în S. Hugget et al. (eds.), Universul Geometric, Oxford: Oxford University Press. [Amprentă disponibilă online].
• Kieu, TD (2002), „Hypercomputability Quantum”, Minți și Mașini, 12: 541–561.
• Kieu, TD (2004), „O reformulare a celei de-a zecea problemă a lui Hilbert prin mecanica cuantică”, Proc. Royal Soc., A 460: 1535–1545.
• Knill, E. și colab., (2000), „Un reper algoritmic pentru prelucrarea cuantică a informațiilor”, Nature, 404: 368–370.
• Levin, L. (2003), „Timpul polinomial și modele extravagante”, Probleme de transmitere a informațiilor, 39 (1): 92–103.
• Linden, N. și Popescu, S. (1999), „Dinamica bună versus cinematica rea: este nevoie de înțelegere pentru calculul cuantic?”, Fiz. Rev. Lett., 87 (4): 047901. [Amprentă disponibilă online].
• Lipton, R. (1995), „Utilizarea ADN-ului pentru rezolvarea problemelor complete NP”, Science, 268: 542–545.
• Manin, Y. (1980), Calculatoare și necomputabile, Moscova: Sovetskoye Radio.
• Messiah, A. (1961), Mecanica cuantică (volumul II), New York: Interscience Publishers.
• Moore, C. (1990), „Imprevizibilitatea și nedecidabilitatea în sistemele dinamice”, Phys. Rev. Lett., 64: 2354–2357.
• Myers, J. (1997), „Un computer cuantic universal poate fi complet cuantic?”, Phys. Rev. Lett., 78 (9): 1823–1824.
• Nielsen, M. (2003), „Calculul cuantic prin măsurare și memoria cuantică”, Phys. Lett., A 308: 96–100.
• Nielsen, MA și Chuang IL (2000), Quantum Computation and Quantum Information, Cambridge: Cambridge University Press.
• Pitowsky, I. (1990), 'Teza Bisericii fizice și complexitatea fizică de calcul, Iyyun, 39: 81–99.
• Pitowsky. I. (1996), „Demonul lui Laplace consultă un oracol: complexitatea computațională a predicțiilor”, Studii în istoria și filosofia fizicii moderne, 27: 161-180.
• Pitowsky, I. (2002), „Viteza cuantificată a calculelor”, Filosofia științei, 69: S168-S177.
• Pitowsky, I. și Shagrir, O. (2003), „Hipercomputarea fizică și teza Bisericii-Turing”, Minds and Machines, 13: 87–101.
• Poplavskii, RP (1975), „Modele termodinamice ale procesării informațiilor”, (în rusă). Uspekhi Fizicheskikh Nauk, 115 (3): 465–501.
• Pour-el, M. și Richards, I. (1981), Ecuația de undă cu date inițiale computabile, astfel încât soluția sa unică nu este calculabilă”, Advanced in Mathematics, 39: 215-239.
• Preskill, J. (1998), „Quantum computing: Pro and Con”, Proc. Roy. Soc. Lond., A 454: 469–486.
• Pylyshyn, Z. (1984), Calcul și cogniție: Către o fundație pentru știința cognitivă, Cambridge: MIT Press.
• Rabin, M. (1976), „Algoritmi probabilistici”, în J. Traub (ed.) Algoritmi și complexitate: noi direcții și rezultate recente, New York: Academic Press, pp. 21–39.
• Reichardt, BW (2004), „Algoritmul de optimizare adiabatică cuantică și minimele locale”, Proceedings of the 36th Symposium on Theory of Computing (STOC), 502–510.
• Rivset R. și colab. (1978), „O metodă pentru obținerea semnăturilor digitale și a criptosistemelor cu cheie publică”, Comunicări ale ACM, 21 (2): 120–126.
• Schrader și colab. (2004), „Registrul cuantic al atomilor neutri”, Phys. Rev. Lett., 93: 150501.
• Sieg W. și Byrnes J. (1999), „Un model abstract pentru calcule paralele”, The Monist, 82: 150–164.
• Simon, DR (1994), „Cu privire la puterea calculului cuantic”, Proceedings of the 35th Symposium anual IEEE on Foundations of Computer Science, pp. 116–123; reeditată, Jurnalul SIAM privind calculul, 26 (5) (1997): 1474–1483.
• Shor, P. (1994) „Algoritmi pentru calculul cuantic: logaritmi discrete și factoring”, Proceedings of the 35th Symposium anual IEEE on Foundations of Computer Science, pp. 124-134.
• Shor, P. (1995), „Schema pentru reducerea decoreiței în memoria cuantică a calculatorului”, Phys. Rev., A 52: 2493–2496.
• Shor, P. (1996), „Calculul cuantic cu toleranță la erori”, Proceedings of the 37th Symposium anual IEEE on Foundations of Computer Science, pp. 56–65.
• Shor, P. (2004), „Progresul în calculul cuantic”, Quantum Information Processing, 3: 5–13. [Amprentă disponibilă online].
• Shor, P. și DiVincenzo, D. (1996) „Corecția erorilor tolerante la erori cu coduri cuantice eficiente”, Phys. Rev. Lett., 77: 3260–3263.
• Steane AM (1996), „Interferențe multiple de particule și corectarea cuantică a erorilor”, Proc. Roy. Soc. Lond., A 452: 2551–2577.
• Turing, A. (1936), „Pe numere computabile, cu o aplicație la Entscheidungsproblem”, reeditată în M. Davis (ed.), The Undecidable, New York: Raven Press, 1965, 116–154.
• Unruh, WG (1995), „Menținerea coerenței în calculatoarele cuantice”, Phys. Rev., A 51: 992–997.
• Vergis, A. și colab. (1986), „Complexitatea calculului analogic”, Matematică și calculatoare în simulare, 28: 91–113.
• Vidal, G. (2003), „Simulare clasică eficientă a calculelor cuantice ușor încurcate”, Phys. Rev. Lett., 91: 147902.
• Wiesner, S. (1983), „Conjugate coding”, Sigact news, 18: 78–88.
• Witten, E. (1989), „Teoria cuantică a câmpurilor și polinomul Jones”, com. Math. Phys., 121: 351-399.
• Wolfram, S. (1985), „Undecidabilitatea și intractabilitatea în fizica teoretică”, Phys. Rev. Lett., 54: 735.

Alte resurse de internet

Documente online

• Aharonov, D. și colab. (2004), „Calculul cuantic adiabatic este echivalent cu calculul cuantic standard”, [Amprentă disponibilă online].
• Aharonov, D. și colab. (2005), „Un algoritm cuantic polinomial pentru aproximarea polinomului Jones”, [Amprentă disponibilă online].
• Bassi, A. și colab. (2005), „Spre superpoziții cuantice ale unei oglinzi: analiză de colaps stochastic”, [Amprentă disponibilă online].
• Bub, J. (2006a), „Informații cuantice și calcul”, [Amprentă disponibilă online].
• Bub, J. (2006b), „Calculul cuantic dintr-o perspectivă logică cuantică”, [Amprentă disponibilă online].
• Calude și colab. (2003), „Transcending the limit of Turing computability”, [Preprint disponibil online].
• DiVicenzo, D. (2000), „Implementarea fizică a calculului cuantic”, [Amprentă disponibilă online].
• Farhi, E., și colab. (2000), „Calculul cuantic prin evoluția adiabatică”, [Amprentă disponibilă online].
• Freedman, M. și colab. (2000), „Simularea teoriilor câmpului topologic de către calculatoarele cuantice”, [Amprentă disponibilă online].
• Fuchs, C. (2002), „Mecanica cuantică ca informații cuantice (și doar puțin mai mult)”, [Amprentă disponibilă online].
• Hodges, A. (2005), „Calculul cuantic poate rezolva probleme de nerezolvat clasic?”, [Amprentă disponibilă online].
• Jozsa, R. (2005), „O introducere în calculul cuantic bazat pe măsurare”, [Amprentă disponibilă online].
• Leung, D. (2003), „Calculul cuantic prin măsurători”, [Amprentă disponibilă online].
• Nielsen, M. și Dawson, C. (2004), „Calculul cuantic cu toleranță la erori cu stările cluster”, [Amprentă disponibilă online].
• Pearle, P. (1998), „Colaps adevărat și fals”, [Amprentă disponibilă online].
• Popescu, S. și Linden, N. (1998), „Problema de oprire pentru computerele cuantice”, [Amprentă disponibilă online].
• Preskill, J. (2005), Note de prelegere pentru calculul cuantic. [Disponibil online].
• Raussendorf, R. și Briegel, H. (2000), „Calcularea cuantică numai prin măsurători”, [Amprentă disponibilă online].
• Raussendorf, R. și colab. (2003), „Calculul cuantic bazat pe măsurare cu stări de cluster”, [Amprentă disponibilă online].
• Smith, WD (2005), Trei contraexemple care resping planul lui Kieu pentru „Hypercomputation Quantum Adiabatic”; și unele sarcini mecanice cuantice necomputabile, ', [Amprentă disponibilă online].

Site-uri web de interes

• Centrul pentru calculul cuantic, Oxford și Cambridge, Marea Britanie
• Proiectul computerului cuantic, MIT
• Centrul de tehnologie cuantică a computerului, Australia
• Institutul de Calculare Cuantică, Canada
• Grupul de informații cuantice Anton Zeilinger, Universitatea din Viena
• Calculul cuantic al lui Samuel Braunstein: un tutorial, Universitatea din York
• Cursul de calcul cuantic al lui Umesh Vazirani, Universitatea din California / Berkeley
• Cursul lui Isaac Chuang privind teoria infromării cuantice, MIT