Algoritmo quantistico: differenze tra le versioni

Versione delle 19:53, 16 nov 2008

Versione attuale delle 03:51, 24 ago 2024

(32 versioni intermedie di 20 utenti non mostrate)

Riga 1:

{{S|informaticaprogrammazione}}

Un '''algoritmo quantistico''' è un [[algoritmo]] progettato per essere eseguito su un modello realistico di [[computazione quantistica]]. Il modello più comunemente usato è quello del [[circuito quantistico]].<ref name="nielchuan" /><ref>{{cita pubblicazione|url=https://arxiv.org/abs/0808.0369|autore=Michele Mosca|titolo=Quantum Algorithms|anno=2008|lingua=en}}</ref> Come un algoritmo classico è una sequenza finita di istruzioni, o una procedura passo passo per risolvere un problema, progettato per essere eseguito su un computer classico, così un algoritmo quantistico è una procedura passo passo progettata per essere eseguita su un [[quantum computer]]. Sebbene tutti gli algoritmi classici possono anche essere eseguiti su un computer quantistico,<ref>{{Cita libro|titolo= Quantum Computer Science|url= https://books.google.com/books?id=-wkJIuw0YRsC&q=quantum%2520computer%2520equivalent%2520classical%2520computer&pg=PA23|editore= Morgan & Claypool Publishers|data= 1º gennaio 2009|isbn = 978-1-59829-732-4|nome1= Marco|cognome1= Lanzagorta|nome2= Jeffrey K.|cognome2= Uhlmann}}</ref> il termine "algoritmo quantistico" viene solitamente usato per quegli algoritmi che sembrano intrinsecamente quantistici, o che usano caratteristiche peculiari della computazione quantistica come la [[Principio di sovrapposizione (meccanica quantistica)|sovrapposizione degli stati]] o l'[[entanglement quantistico]].

Un '''algoritmo quantistico''' è un [[algoritmo]] progettato per essere eseguito da un [[computer quantistico]]. Questi algoritmi sfruttando le proprietà dei computer quantistici sono in grado di risolvere in [[Teoria della complessità algoritmica|tempi polinomiali]] problemi che trattati con gli usuali computer vengono risolti con [[Teoria della complessità algoritmica|tempi esponenziali]]. L'esempio più famoso riguarda la [[fattorizzazione]] dei numeri grandi in [[Numero primo|numeri primi]]. Un algoritmo quantistico in grado di fattorizzare i numeri con una complessità polinomiale metterebbe in crisi la maggior parte degli attuali [[Crittografia|algoritmi di cifratura]]. Attualmente non esiste un [[computer quantistico]] funzionante con più di 7 [[qubit]] e che non sia grande come una casa e lento come un [[bradipo]]<ref>{{en}} [http://domino.watson.ibm.com/comm/pr.nsf/pages/news.20011219_quantum.html Comunicato Stampa IBM sul CQ a 7 qubit]</ref>. Il [[computer quantistico]] dell'IBM ha implementato l'[[algoritmo di fattorizzazione di Shor]] su numeri piccoli (nell'articolo riportato, 15). La prima rete a [[crittografia quantistica]], [[Qnet]], è stata sviluppata proprio in seguito al riuscito esperimento dell'[[IBM]].

I [[Problema indecidibile|problemi indecidibili]] con i computer classici rimangono indecidibili anche con i computer quantistici.<ref name="nielchuan">{{Cita libro|titolo=Quantum Computation and Quantum Information|cognome=Nielsen|nome=Michael A.|cognome2=Chuang|nome2=Isaac L.|editore=Cambridge University Press|anno=2010|isbn=978-1-107-00217-3|edizione=2|città=Cambridge|wkautore=Michael A. Nielsen|wkautore2=Isaac Chuang|url=https://books.google.com/books?id=-s4DEy7o-a0C}}</ref> Ciò che rende gli algoritmi quantistici degni di interesse è che potrebbero essere in grado di risolvere alcuni problemi più velocemente dei computer classici perché la sovrapposizione degli stati e l'entanglement quantistico che vengono sfruttati dagli algoritmi quantistici non possono essere simulati efficacemente sui computer classici ([[supremazia quantistica]]).

Gli algoritmi più conosciuti sono l'[[algoritmo di fattorizzazione di Shor]] e l'[[Algoritmo di ricerca di Grover|algoritmo di Grover]] per cercare in un database indifferenziato. L'algoritmo di Shor gira molto più velocemente del miglior algoritmo classico conosciuto per la fattorizzazione, il [[crivello dei campi di numeri generale]].<ref>{{Cita web|url=https://quantum-computing.ibm.com/docs/iqx/guide/shors-algorithm|titolo=Docs and Resources|sito=IBM Quantum Experience|lingua=en|accesso=27 gennaio 2021|dataarchivio=12 gennaio 2023|urlarchivio=https://web.archive.org/web/20230112064753/https://quantum-computing.ibm.com/docs/iqx/guide/shors-algorithm|urlmorto=sì}}</ref> L'algoritmo di Grover gira quadraticamente più veloce della [[ricerca sequenziale]].

==Principali algoritmi quantistici==

* [[Algoritmo di fattorizzazione di ShorBernstein-Vazirani]]

*[[Algoritmo di Deutsch-Jozsa]]

*[[Algoritmo di ricerca di Grover]]

*[[Problema di Simon]]

==Note==

* [[Algoritmo di fattorizzazione di Shor]]

*[[Algoritmo quantistico di stima della fase]]

== Note ==

<references/>

==Voci correlate==

* [[Informatica quantistica]]

{{portale|fisica}}

== Collegamenti esterni ==

[[Categoria:Algoritmi]]

* {{Collegamenti esterni}}

[[Categoria:Informatica {{portale|informatica|quantistica]]|matematica}}

[[Categoria:Algoritmi quantistici| ]]

[[en:Quantum algorithm]]

[[pl:Algorytm kwantowy]]