Re: Supremazia quantistica.

From: Giorgio Pastore <pastgio_at_units.it>
Date: Fri, 27 Sep 2019 22:08:21 +0200

Il 27/09/19 17:36, Elio Fabri ha scritto:
> JTS ha scritto:
>> Non lo so, ma aggiungo un'altra domanda sperando che qualcuno si
>> faccia avanti e risponda: il calcolo con il computer quantistico per
>> questo problema e' simile (almeno vagamente!) ad un processo di
>> scattering? Perche' se e' cosi' l'analogia sarebbe bella :-)
> Non riesco a capire in che senso quelo proposta da Giulia possa essere
> un problema da risolvere con un computer, classico o quantistico.

la ricerca di un elemento in un insieme è un problema infoatico
classico. Esistono vari algoritmi. Il più banale (e inefficiente, e'
O(N)0 prevede di confrontare con l'elemento cercato (la chiave) uno per
uno gli N elementi dell' insieme finché
- si trova l'elemento
- si esaurisce l' insieme senza trovarlo.
Un algoitmo più efficiente è la ricerca binaia che pero' pevede di avr
odinato l'insieme (se e' ordinabile). A quel punto la tecnica di icerca
in un dizionario (vai a metà, determina in quale dell due metà sia
l'elemento e riapplica la divisione ricorsivamente). Risultsto:
algoritmo O(log(N)). Un computer quantistico risolverebbe il problema in
O(1) operazioni: se l'elemento c'è lo trova subito.

Questo per rispondere alla perplessità di Elio. Se poi l'algoritmo
quantistico possa esser visto come un processo di scattering, non saprei
(per ignoranza, non per perplessità).

Giorgio
Received on Fri Sep 27 2019 - 22:08:21 CEST