Re: Quantum Computers breaking ciphers

From: Guy Macon (http://www.guymacon.com)
Date: 10/09/04 

Date: Fri, 08 Oct 2004 20:19:08 -0700

Roger Schlafly <rogersc1@mindspring.com> says...
>
>
>"Guy Macon" <http://www.guymacon.com> wrote:
>>>Nobody can tell, as nobody has ever built a quantum computer.
>> Yes they have. IBM Research/Stanford University built a seven-atom
>> quantum computer and used itbto run Shor's Algorithm works and to
>> correctly identifying 3 and 5 as prime factors of 15.
>> It only took a few decades to go from the transistor to the supercomputer.
>
>When the transistor was invented, it was obvious that transistors
>could be chained to make computers. But no one can even make
>one qubit that can be chained with other qubits to do a computation.

How can you say that? Factoring fifteen is a computation.

>Here is a good account of the research you mention. It is a
>good physics thesis, but not a quantum computer. It is just an
>investigation of the spin states of some particular molecule.
>http://arxiv.org/abs/quant-ph/0205193

>From the web page you cited:

"we provided proof of principle of quantum computing in a series
of experiments which culminated in the implementation of the
simplest instance of Shor's quantum algorithm for prime
factorization (15=3x5), using a seven-spin molecule."

>From http://www.research.ibm.com/resources/news/20011219_quantum.shtml

"The simplest meaningful instance of Shor's Algorithm is finding
the factors of the number 15, which requires a seven-qubit quantum
computer. IBM chemists designed and made a new molecule that has
seven nuclear spins -- the nuclei of five fluorine and two carbon
atoms -- which can interact with each other as qubits, be programmed
by radio frequency pulses and be detected by nuclear magnetic resonance
(NMR) instruments similar to those commonly used in hospitals and
chemistry labs.

"The IBM scientists controlled a vial of a billion-billion (1018)
of these molecules so they executed Shor's algorithm and correctly
identified 3 and 5 as the factors of 15. "Although the answer may
appear to be trivial, the unprecedented control required over the
seven spins during the calculation made this the most complex
quantum computation performed to date," Amer said.

"Now we have the challenge of turning quantum computation into an
engineering reality," said Isaac Chuang, leader of the research
team and now an associate professor at MIT. "If we could perform
this calculation at much larger scales -- say the thousands of
qubits required to factor very large numbers -- fundamental changes
would be needed in cryptography implementations."

Relevant Pages

  • Re: How long would it take a computer to completely "solve" chess?
    ... The kind of tree search you need to do to determine the ... a quantum computer will turn it into an easy one. ... the types of problem for which there's an algorithm to solve it using ... because each other type of problem in PSPACE can be reduced to it. ...
    (sci.math)
  • Re: How long would it take a computer to completely "solve" chess?
    ... |Try calculating how many qubits it would take instead of calculating ... a big speed-up from using some clever algorithm on a classical ... The kind of tree search one needs to do generally requires ... a quantum computer can search N2 items in T time. ...
    (sci.math)
  • Re: Symmetric Encryption attacked by quantum computers?
    ... > I have read that if you are using a symmetric cipher with a 256 bit ... it would take a quantum computer about 2^128 steps to break. ... Grover's algorithm: ... doesn't automatically get fast computation from superposition -- one needs ...
    (sci.crypt)
  • Serially Factoring large prime numbers --- Shors algorithm modification
    ... I believe Shor's algorithm uses a quantum computer to factor large prime numbers product. ... When the X qubits settle down, you have obtained the first X bits of the solution. ... Feed the problem into the "X" qubit quantum computer along with the first X bits of the solution. ...
    (sci.math)
  • Re: Quantum Computing and protein folding
    ... >> Would a quantum computer be able to efficiently, and accurately, solve ... a protein polypeptide itself is a quantum mechanical system that seems ... > problem any fatser using brute force as an algorithm. ... Maybe someone will someday figure out how to make such an algorithm ...
    (comp.theory)
Loading