Una strategia per Geppetto, italian didactic version

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.