Re: Quantum computing and the future of cryptography

Ertugrul Söylemez <es@xxxxxxxx> writes:
I think, if an algorithm is found to solve an NP-complete problem, it
will prove P = NP, not BQP = NP, and if we find P = NP, then quantum
computers are the least of our worries.

I think it is not even known that BQP <= NP. A quantum computer may
be able to solve problems that are outside of NP. Scott Aaronson's
Scientific American article about quantum computing is informative and
accessible:

http://www.cs.virginia.edu/~robins/The_Limits_of_Quantum_Computers.pdf

Russell Impagliazzo wrote an interesting essay about the relationship
between P vs NP and cryptography (it's more subtle than it might look).
This is the famous "five worlds" paper:

http://www-cse.ucsd.edu/~russell/average.ps

H. Helgason summarized it in a slide show:

http://www3.hi.is/~hh/kennsla/rrr/hhh-presentation.pdf
.

Relevant Pages

  • Re: Quantum computable functions
    ... "Computational complexity of uniform quantum circuit families and quantum Turing machines" ... his universal QTM needs exponential slowdown for simulating QTMs. ... "Deutsch showed that quantum computers can't compute anything going beyond ordinary Turing computable functions -- but they can compute ...
    (comp.theory)
  • Re: Computers set for Quantum leap
    ... Computers set for quantum leap ...   Why quantum computing? ... Australia and Singapore - see quantum electronics as the foundation for IT ...
    (soc.culture.singapore)
  • Brain best explained by Quantum Processes
    ... Brain best explained by Quantum Processes ... Computers are causal systems. ... existence of strictly causal systems which display chaotic behavior. ...
    (sci.physics)
  • Computers set for Quantum leap
    ... Computers set for quantum leap ... "Entanglement" - the ability of subatomic particles to influence one another ... Australia and Singapore - see quantum electronics as the foundation for IT ...
    (soc.culture.singapore)
  • Re: A unique number for every "person" - can it be done?
    ... > Gerry, all due respect, but you really should have consulted the ... > computers, ones of the types described above can't solve any problems ... > Turing machine can simulate these quantum computers, ... > quantum computers refute Turing. ...
    (comp.programming)