Link alla notizia: http://www.businessmagazine.it/news/computazione-quantistica-nuova-tecnica-per-leggere-lo-spin-elettronico_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.

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

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

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.

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.

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 :fagiano:

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.

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

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 :D

Sinceramente, non riesco a seguire il discorso :sofico:

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

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

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

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!

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

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

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:D

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

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.

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.

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.

ci sono sempre campi non ancora inventati o scoperti:D

ci sono sempre campi non ancora inventati o scoperti:D

e con strumenti del genere saremmo + attrezzati per la ricerca .. una sorta di Cern x i computer :) Quindi andiamo nel campo dell' ignoto ? Magari anche , ma ci sarà pure qualcosa di già praticabile.

Per ridere dico che a me basta accendere il pc e non finire risucchiato in un buco nero :)

e con strumenti del genere saremmo + attrezzati per la ricerca .. una sorta di Cern x i computer :) Quindi andiamo nel campo dell' ignoto ? Magari anche , ma ci sarà pure qualcosa di già praticabile.

Per ridere dico che a me basta accendere il pc e non finire risucchiato in un buco nero :)
Al momento il risultato migliore ottenuto con un computer quantistico è stato fattorizzare 15 in 5 e 3 con l'algoritmo di Schor con una probabilità del 50%!

Al momento il risultato migliore ottenuto con un computer quantistico è stato fattorizzare 15 in 5 e 3 con l'algoritmo di Schor con una probabilità del 50%!
Errata corrige: sei rimasto indietro, sono riusciti a fattorizzare il numero 21 :D
http://www.nature.com/nphoton/journal/vaop/ncurrent/full/nphoton.2012.259.html

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.

in realta' non saprei dirtelo.
in effetti per me, sarebbero solo computer piu' veloci (e forse piu' efficenti), ma non di piu'.

nel mio campo di lavoro gli spin li andiamo a guardare solo per capire che atomo abbiamo e quelli che ha intorno, non gli chiediamo nulla!
ma a pensarci bene, tutto il mio lavoro (chimica) si basa su teorie ed illazioni, quindi se domani mi vengono a dire che e' tutta un'altra cosa, che non ci sono atomi ma smarties di cioccolata piccolissimi, non ci sono legami ma fili di liquirizia, mi metterei a fare il falegname.

come hanno scritto gli altri oggi i computer quantistici riescono a risolvere problemi elementari, ma e' pur vero che per fattorizzare 15 hanno usato 5 qubit, 7 qubit per 21.
quando riusciranno a creare un computer quantistico da qualche milione di qubit, a quel punto credo che potrebbero avere un'utilita' pratica.

per quanto riguarda l'AI... no, una macchina di turing puo' imitare, ma non puo' essere.
l'intelligenza e' cosa diversa dalla computazione (e' una cosa quasi divina), nel senso che se il nostro cervello dovesse comportarsi come un PC per le semplici scelte di ogni giorno, dovremmo avere una testa come una mongolfiera per metterlo dentro.

c'e' quindi un quid in piu' che una macchina (di turing) ancora non puo' avere, nemmeno con un calcolo probabilistico... forse le reti neurali, che imitano il funzionamento del cervello potrebbero generare una cosa simile, ma... se un nostro neurone potrebbe essere paragonato ad uno SOC ARM... ecco, noi ne abbiamo qualche miliardo in rete... ad oggi credo che tutti quelli prodotti fino a questo momento, se messi in rete e organizzati in tal maniera, non avrebbero l'intelligenza di un pollo.

per ora pero' e' divertente provarci.

in realta' non saprei dirtelo.
per quanto riguarda l'AI... no, una macchina di turing puo' imitare, ma non puo' essere.
l'intelligenza e' cosa diversa dalla computazione (e' una cosa quasi divina), nel senso che se il nostro cervello dovesse comportarsi come un PC per le semplici scelte di ogni giorno, dovremmo avere una testa come una mongolfiera per metterlo dentro.

c'e' quindi un quid in piu' che una macchina (di turing) ancora non puo' avere, nemmeno con un calcolo probabilistico... forse le reti neurali, che imitano il funzionamento del cervello potrebbero generare una cosa simile, ma... se un nostro neurone potrebbe essere paragonato ad uno SOC ARM... ecco, noi ne abbiamo qualche miliardo in rete... ad oggi credo che tutti quelli prodotti fino a questo momento, se messi in rete e organizzati in tal maniera, non avrebbero l'intelligenza di un pollo.

per ora pero' e' divertente provarci.

Vero , intelligenza forse come termine può essere inserito per descrivere una supermacchina .. ma non avranno mai la COSCIENZA . Per ora quella si ottiene in un modo solo : non assemblando silicio ma assemblando certi atomi in quantità e modo tale che compongano il cervello,il cuore etc.

Chiaro che una supermacchina agisce intelligentemente , meglio e più velocemente di noi ma c'è sempre sta misteriosa differenza tra oggetto vivo e oggetto non vivo.

Attualmente mi sfuggono gli algoritmi non risolvibili dai PC, chi me li ricorda?
Il problema del traffico.

(no, serio: ricerca del minimo di una funzione con uno scatafascio di varibili. Attualmente questi problemi si risolvono con algoritmi "euristici" - cioè... vanno a naso)

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 :fagiano:
Magari, per risolvere il problema del traffico, potrebbero provare tutte le combinazioni e scegliere la migliore.

(non funzionano proprio così, ma è la cosa che forse più si avvicina detta in lingua comprensibile senza scrivere un trattato)