Quantum computers inch closer?

[Jaap-Henk Hoepman]

On Mon, 02 Sep 2002 17:59:12 -0400 "John S. Denker" <jsd at monmouth.com> writes:
> The same applies even more strongly to quantum computing:
> It would be nice if you could take a classical circuit,
> automatically convert it to "the" corresponding quantum
> circuit, with the property that when presented with a
> superposition of questions it would produce "the" 
> corresponding superposition of answers.  But that cannot 
> be.  For starters, there will be some phase relationships 
> between the various components of the superposition of 
> answers, and the classical circuit provides no guidance 
> as to what the phase relationships should be.

In fact you can! For any efficient classical circuit f there exists an
efficient quantum circuit Uf that does exactly what you describe:
when given an equal superposition of inputs it will produce the equal
superposition of corresponding outputs.

Jaap-Henk

-- 
Jaap-Henk Hoepman             | Come sail your ships around me
Dept. of Computer Science     | And burn your bridges down
University of Nijmegen        |       Nick Cave - "Ship Song"
Email: jhh at cs.kun.nl         === WWW: www.cs.kun.nl/~jhh
Phone: +31 24 3652713 === Secr: +31 24 3653132 === Fax: +31 24 3653137
PGP ID: F280B29C | Print: C798 7420 F6A3 0B3D 1A0B BC53 1F12 C84E F280 B29C 


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com