Computazione quantistica, nuova tecnica per leggere lo spin elettronico

[Redazione di Hardware Upg]

Link alla notizia: http://www.businessmagazine.it/news/...ico_44351.html

Compiendo un piccolo passo in direzione del computer quantistico, i ricercatori della Princeton University mettono a punto una nuova tecnica per la lettura dello spin elettronico, scalabile su maggiori dimensioni per poter gestire milioni di qubit

Click sul link per visualizzare la notizia.

[Perseverance]

Attualmente mi sfuggono gli algoritmi non risolvibili dai PC, chi me li ricorda?

[SUPERALEX]

sono i problemi nn decidibili x esempio un algoritmo che ricevuto come input un altro algoritmo ti dica se quest'ultimo raggiungerà la terminazione sempre e comunque

[Floris]

Originariamente inviato da Perseverance

Attualmente mi sfuggono gli algoritmi non risolvibili dai PC, chi me li ricorda?

Halting problem, per fare l'esempio più famoso.
In ogni caso la computazione quantistica non risolverà alcun problema che i calcolatori odierni non siano in grado di calcolare. I calcolatori quantistici sono a loro volta Turing completi come i computer odierni. Semplicemente calcolano più velocemente sfruttando un parallelismo massimo. Per ora non si sa nemmeno se possano riuscire a risolvere in tempo polinomiale problemi in NP. Per cui sarebbero solo più veloci, molto più veloci ma dal punto di vista teorico non abbatterebbero alcuna barriera computazionale.
Ovviamente quanto detto al meglio delle mie conoscenze e dei progressi attuali!

Edit: Quando si parla di: "risolvere problemi che non possono essere affrontati con un computer tradizionale" credo si intenda problemi il cui costo computazionale è così elevato da non essere praticabile.

[II ARROWS]

Esatto, di solito si termina quella frase con "in tempi accettabili".
Un caso è purtroppo la decifrazione delle chiavi, un altro più terra terra è il navigatore... Che al giorno d'oggi presenta algoritmi piuttosto arrotondati ma che accettano l'imprecisione a favore di una soluzione che vada bene seppur non ottimale.

[Mith89]

Originariamente inviato da Floris

Quando si parla di: "risolvere problemi che non possono essere affrontati con un computer tradizionale" credo si intenda problemi il cui costo computazionale è così elevato da non essere praticabile.

da quello che ho capito io nell'articolo dicono proprio il contrario, cioè che non conta tanto la potenza e la velocità (ovvero ciò che conta nei costi computazionali), ma il modo con cui alcuni problemi potranno essere affrontati. Detto questo non ho la più pallida idea di cosa voglia dire affrontare dei problemi in modo diverso nel mondo dei computer

[lucusta]

un computer tradizionale ricerca la risposta esatta.
un computer quantico ti rende tutte le possibili risposte.

detto cosi' e' incomprensibile, ma se chiedi qual'e' la strada che richiede meno tempo da roma a pechino fermandosi per ogni locanda per la strada, un PC normale ci metterebbe secoli, tanto che il suo calcolo dovrebbe ricominciare ogni volta che apre o chiude una locanda o viene aperta o chiusa una strada, diventando impossibile.
un computer quantico, a seconda del numero dei suoi qbit, ti ridarra' tutti i possibili percorsi reali, non solo quello giusto, ma te li rendera' tutti, e tu potrai trovare la risposta giusta affrontando il problema in modo piu' dettagliato.
dipende appunto da quanti bit puoi elaborare all'unisono.
oggi i PC nostrani arrivano a 64 bit, quindi esistono 64^2 differenti istruzioni, ma se tu usassi un sistema a 1024 bit?

e' per questo che nell'articolo si dice che e' necessario avere un sistema decisamente piu' grande, tanto grande per poter risolvere problemi con molteplici variabili.

e' comunque la natura del problema che e' differente: le possibili risposte reali mi servono tutte e subito, perche' tra' un infinitesimo le condizioni sono cambiate e quindi le risposte sono diverse...

diciamo, per assurdo, che riusciresti a conoscere posizione e moto di una qualsiasi particella, in barba al principio di indeterminazione di heisenberg....
vabe', ho esagerato con quest'ultima affermazione.

[lucusta]

scusami, riformulo la risposta per renderla piu' comprensibile, spostandola sui computer molecolari.

bene, in natura gia' esistono i computer molecolari, ed hanno gia' risposto ad una domanda: puo' esistere la vita?
ci hanno messo milioni d'anni, combinazioni e ricombinazioni di molecole, interazione tra di loro, biosistema, ecc... , ma alla fine la risposta, reale e tangibile, la hai tu stesso, perche' sei te stesso.

ora, aspettare qualche milione di anni per avere una risposta e', oggi giorno, impraticabile.

se avessi avuto un computer quantico di nmila qubit per inserire tutti i dati degli atomi e le loro caratteristiche fisiche e le interazioni che hanno, ed avessi posto la stessa domanda, nel calcolo quantico si sarebbero ottenute tutte le risposte, anche quelle ricombinazioni che non portavano a nulla, per dire che la vita puo' esistere, e probabilmente avrebbe dato decine di variazioni di queste, basate su carbonio, silicio, o arsenico....

[grogdunn]

Originariamente inviato da Perseverance

Attualmente mi sfuggono gli algoritmi non risolvibili dai PC, chi me li ricorda?

bhe come detto ci sono i problemi NP completi che all'aumentare della lunghezza dell'input il tempo di computazione aumenta in moto esponenziale.
se con 1 dato ci stà un secondo con 10 dati un programma "normale" dovrebbe stare 10 secondi (in prima approssimazione) se il problema è np completo ci vuole (sparando un numero) un anno!
su questa teoria si basa tutta la storia delle chiavi pubbliche/private e la sicurezza online... se vuoi azzeccare la chiave ci stai alcune migliaia di anni...

poi da quanto so questi qbit possono essere nello stato 1 e 0 contemporaneamente (o avere lo stato intermedio di indefinitezza? non ricordo...) quindi penso che aprano le porte a tutto un'altro modo di "computare"... insomma un bel (interessante) casino

[Yakkuz]

Sinceramente, non riesco a seguire il discorso

Tempistiche a parte, è proprio il concetto di algoritmo non risolvibile che mi sfugge...

[SUPERALEX]

nn risolvibile nel senso che nn termina...cosa che va contro la definizione di algoritmo

[lucusta]

yakkuz, e' irrisolvibile quando i dati iniziali di input cambiano durante lo svolgimento del calcolo, rendendo di fatto vano il calcolo stesso.
in quel caso ci vuole una risposta "realtime".

e' impraticabile quando per risolvere l'algoritmo, pur avendo gli input fissi, ci metti una vita, tale da vanificare lo scopo per cui serviva la risposta (ad esempio trovare chiavi codificate pubbliche e private).

nella realta', pero' le cose si complicano.
una computazione quantica ti computa tutte le possibili risposte reali, ma e' ....un solo clock! un solo calcolo per la sequenza di input che metti, quindi se devi effettuare un aggiuntivo calcolo lo devi comunque fare in un solo clock, e percio' ti servono piu' digit.
teoricamente potresti, anche con un computer normale, avere la stessa efficacia, solo che non si parla di un sistema a soli 64bit, ma a qualche milione; in questo modo un solo clock genera la risposta...

l'impostazione del programma da eseguire diventa percio' decisamente difficile, visto che ha una sola riga di comando.

un problema di calcolo quantistico lo trovi al minuto 25.48 di questo filmato:
http://www.youtube.com/watch?v=FkdGNi94OYw

[Floris]

Originariamente inviato da SUPERALEX

nn risolvibile nel senso che nn termina...cosa che va contro la definizione di algoritmo

Non si capisce bene dall'articolo perchè non utilizzano termini formali.
Non risolvibile nel senso di non computabile significa che non esiste alcun algoritmo che risolva il problema. Il primo esempio è l'halting problem (o problema dell'arresto) formulato da Turing nello stesso articolo in cui gettava le basi della teoria della computabilità. Puoi guardarti la dimostrazione che non è troppo complicata. In sostanza dice che non esiste un algoritmo che per ogni programma ti sappia dire se questo termina oppure no.
Plausibilmente nell'articolo si intende non risolvibile nel senso di non efficientemente computabile intendendo con questo la classe dei problemi NP-hard non in P, ovvero quei problemi per cui non esiste un algoritmo deterministico con complessità polinomiale. Infatti finora la computazione quantistica non si è dimostrata capace di andare oltre la Turing completezza (ovvero i problemi non computabili per i computer odierni lo sono anche per i computer quantistici) e d'altronde se ciò si rivelasse errato, l'intera teoria della computabilità andrebbe riscritta!

[iLink]

Non posso crederci...
Nessuno si è ancora fatto la domanda...

"CI GIRERA' CRYSIS?"

XD

Cavolate a parte, su Sky ho visto un interessante documentario che spiega come l'aumentare della potenza di calcolo a nostra disposizione grazie ai calcolatori quantistici potrebbe portarci ad avere nel futuro una potenza "infinita", con un infinità di conseguenze...

[misterfrederx]

Più che girarci Crysis, devi preoccuparti se il protagonista del gioco non prende la cam se la giri contro e ti chiesa "cosa sono io??". I computer quantistici sono la strada verso l'AI *___* figataa

[SUPERALEX]

Originariamente inviato da Floris

Non si capisce bene dall'articolo perchè non utilizzano termini formali.
Non risolvibile nel senso di non computabile significa che non esiste alcun algoritmo che risolva il problema. Il primo esempio è l'halting problem (o problema dell'arresto) formulato da Turing nello stesso articolo in cui gettava le basi della teoria della computabilità. Puoi guardarti la dimostrazione che non è troppo complicata. In sostanza dice che non esiste un algoritmo che per ogni programma ti sappia dire se questo termina oppure no.
Plausibilmente nell'articolo si intende non risolvibile nel senso di non efficientemente computabile intendendo con questo la classe dei problemi NP-hard non in P, ovvero quei problemi per cui non esiste un algoritmo deterministico con complessità polinomiale. Infatti finora la computazione quantistica non si è dimostrata capace di andare oltre la Turing completezza (ovvero i problemi non computabili per i computer odierni lo sono anche per i computer quantistici) e d'altronde se ciò si rivelasse errato, l'intera teoria della computabilità andrebbe riscritta!

lo so purtroppo informatica teorica me la son dovuta sorbire

[maxmax80]

i ricercatori della Princeton University devono fare il loro lavoro,
ma mi auguro che tutto questo rimanga sono una inutile ed utopica sperimentazione da banco..
sarà, ma per me è meglio evitare di avvicinarsi alla genesi di quelle intelligenze artificiali protagoniste di tanti film di fantascienza..

[elevul]

Ho capito poco dell'articolo, ma non vedo l'ora che la computazione quantistica prenda piede. Si sente pesantemente il bisogno di un salto prestazionale adesso.

[elevul]

Originariamente inviato da maxmax80

i ricercatori della Princeton University devono fare il loro lavoro,
ma mi auguro che tutto questo rimanga sono una inutile ed utopica sperimentazione da banco..
sarà, ma per me è meglio evitare di avvicinarsi alla genesi di quelle intelligenze artificiali protagoniste di tanti film di fantascienza..

IMHO le AI saranno la cosa che ci salverà in futuro.

[TheAle]

Originariamente inviato da lucusta

un computer tradizionale ricerca la risposta esatta.
un computer quantico ti rende tutte le possibili risposte.

ciao , secondo te a che pro porta questa possibilità? Che tipo di problemi diversi potranno risolvere questi pc?

Io la vedo che questi pc quantistici andranno solo molto più veloci ma sugli stessi calcoli dei pc attuali permettendo di risolvere in tempi accettabili problemi oggi non risolvibili (tipo sapere i numeri primi di un prodotto di numeri primi) in tempi accettabili.

Io non sono un fisico eh leggo a volte libri di divulgazione scientifica .. non immagino che altri campi di utilizzo avrebbe questo tipo di pc se non lo stesso di quelli odierni (ma solo + veloci) .. e x questo chiedo.