Introduction to quantum computing

Let’s start with the Wikipedia definition:

A quantum computer is any device for computation that makes direct use of distinctively quantum mechanical phenomena, such as superposition and entanglement, to perform operations on data. In a classical (or conventional) computer, information is stored as bits; in a quantum computer, it is stored as qubits (quantum bits). The basic principle of quantum computation is that the quantum properties can be used to represent and structure data, and that quantum mechanisms can be devised and built to perform operations with this data.

What is a superposition? What is entanglement? Can quantum computers compute NP problems in P? It’s hard get started in this strange field.

Scott AaronsonFirst the basics: Quantum Computing for High School Students by Scott Aaronson is an easy to read introduction to quantum computing in general.

You’ve heard quantum computers can break RSA? Theoretically you’re right. Using Shors Algorithm they can. I won’t explain this here, because Scott Aaronson again has written a beautiful and readable explanation.

Those two links should give you a good start. If not, just read on through Scotts blog.

What you should know about quantum computers: They are not a magic weapon to make computers faster. They can’t compute all NP problems in polynomial time. They are no silver bullet. Quantum computers can solve specific problems due to the quantum phenomenons. Some problems (like breaking RSA) can be reduced to these specific problems.

Currently scientists can build small quantum computers consisting of 7 qubits and have successfully factorized 15 into 5 and 3 in 2001. It’s an engineering problem to scale up the qubits to factorize bigger numbers.

My prediction: It’ll take some time, but eventually (probably decades) we will build quantum computers and scale them up to thousands of qubits. They won’t replace traditional CPUs though, but will work as a coprocessor like Cell.

The scary sidenote for a good discussion (recommended to combine with some drinks): What will happen with the world, once we break RSA? Public key encryption won’t work anymore. No online banking, no e-commerce, no cheap and secure communication anymore. Economy breaks down and world war III wipes out all humans?

Published in: on September 20, 2007 at 12:10 pm  Comments (2)  

The URI to TrackBack this entry is:

RSS feed for comments on this post.

2 CommentsLeave a comment

  1. Apparently, quantum computers look like beer kegs. There’s also an interesting video introducing the basics.

    You are absolutely right, quantum computers are not magically faster computers. I think of them as _alternative_ computers. A cleaver application of their special properties to specific problems could result in a _much_ faster calculation. Though the theory sounds like a raw, domain specific, computational device. Not a general purpose desktop replacement.

  2. Source:

    Scientists at Florida State University’s National High Magnetic Field Laboratory and the university’s Department of Chemistry and Biochemistry have introduced a new material that could be to computers of the future what silicon is to the computers of today.
    The material — a compound made from the elements potassium, niobium and oxygen, along with chromium ions — could provide a technological breakthrough that leads to the development of new quantum computing technologies. Quantum computers would harness the power of atoms and molecules to perform memory and processing tasks on a scale far beyond those of current computers.
    “The field of quantum information technology is in its infancy, and our work is another step forward in this fascinating field,” said Saritha Nellutla, a postdoctoral associate at the magnet lab and lead author of the paper published in Physical Review Letters.
    Semiconductor technology is close to reaching its performance limit. Over the years, processors have shrunk to their current size, with the components of a computer chip more than 1,000 times smaller than the thickness of a human hair. At those very small scales, quantum effects — behaviors in matter that occur at the atomic and subatomic levels — can start playing a role. By exploiting those behaviors, scientists hope to take computing to the next level.
    In current computers, the basic unit of information is the “bit,” which can have a value of 0 or 1. In so-called quantum computers, which currently exist only in theory, the basic unit is the “qubit” (short for quantum bit). A qubit can have not only a value of 0 or 1, but also all kinds of combinations of 0 and 1 — including 0 and 1 at the same time — meaning quantum computers could perform certain kinds of calculations much more effectively than current ones.
    How scientists realize the promise of the theoretical qubit is not clear. Various designs and paths have been proposed, and one very promising idea is to use tiny magnetic fields, called “spins.” Spins are associated with electrons and various atomic nuclei.
    Magnet lab scientists used high magnetic fields and microwave radiation to “operate” on the spins in the new material they developed to get an indication of how long the spin could be controlled. Based on their experiments, the material could enable 500 operations in 10 microseconds before losing its ability to retain information, making it a good candidate for a qubit.
    Putting this spin to work would usher in a technological revolution, because the spin state of an electron, in addition to its charge, could be used to carry, manipulate and store information.
    “This material is very promising,” said Naresh Dalal, a professor of chemistry and biochemistry at FSU and one of the paper’s authors. “But additional synthetic and magnetic characterization work is needed before it could be made suitable for use in a device.”
    Dalal also serves as an adviser to FSU chemistry graduate student Mekhala Pati, who created the material.
    Note: This story has been adapted from material provided by Florida State University.

    Fausto Intilla

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: