Trovare una strategia efficiente per ottenere la verita' da un mentitore e' compito molto arduo. Con riferimento al mondo fiabesco, Pinocchio e' il personaggio piu' legato alle bugie in virtu' del suo naso. Supponiamo ora che Geppetto voglia scoprire qualcosa da Pinocchio prescindendo pero' dal suo naso e potendo utilizzare solo domande la cui risposta sia si' o no. Pinocchio mentira' in alcune delle sue risposte, ma supponiamo che non voglia dire piu' di un numero l di bugie. Quante domande saranno necessarie a Geppetto per ottenere la verita'? Questo e' una rilettura del famoso ``problema di Ulam'' di cui, ad oggi, non si conosce una soluzione ottimale. Qui mostriamo come un algoritmo quantistico permetta di risolverlo in maniera molto efficiente.
Una strategia per Geppetto, italian didactic version
MACCONE, LORENZO
2006-01-01
Abstract
Trovare una strategia efficiente per ottenere la verita' da un mentitore e' compito molto arduo. Con riferimento al mondo fiabesco, Pinocchio e' il personaggio piu' legato alle bugie in virtu' del suo naso. Supponiamo ora che Geppetto voglia scoprire qualcosa da Pinocchio prescindendo pero' dal suo naso e potendo utilizzare solo domande la cui risposta sia si' o no. Pinocchio mentira' in alcune delle sue risposte, ma supponiamo che non voglia dire piu' di un numero l di bugie. Quante domande saranno necessarie a Geppetto per ottenere la verita'? Questo e' una rilettura del famoso ``problema di Ulam'' di cui, ad oggi, non si conosce una soluzione ottimale. Qui mostriamo come un algoritmo quantistico permetta di risolverlo in maniera molto efficiente.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
