Quantum computing for everyone | Hacker News Reader

Quantum computing for everyone

michaelnielsen.org

55 pointsntoshev21 comments

I think the author didn't achieve his own goal: “Can you give me a simple, concrete explanation of how quantum computers work?”

The explanation, even though it doesn't involve any complicated math or technical stuff, is long, convoluted and full of excuses of why there can't be a simple explanation.

The excuses are part of the explanation ;) I don't know why people expect to have metaphors from the macro world that can be readily applied to quantum mechanics - the whole particle-wave duality for example seems just an attempt to explain experimental results / equations with two partially broken complementary metaphors - just because this is all we have at hand in the everyday world...

Question for someone who knows more about this:

Is this the right way to think about it? What we need to do to write a "program" to solve a problem is:

1) Find a set of gates to setup the atoms so that they have the right input.

2) Find a set of gates that uses this input to solve the problem.

I know very little about quantum computation so any help is appreciated...

Take a look at Shor's algorithm[1] for factoring integers on a quantum computer. It's definitely not for the faint of heart, but it should show you what goes into creating an algorithm for a quantum computer. People complain about concurrent programming, they have another thing coming if quantum computers become commonplace. I suspect it will be more like programming an FPGA than a CPU.

In any case, as I understand it, you will need to add a third step, which is to extract the correct solution from the system's state, which is also non-trivial.

[1] http://en.wikipedia.org/wiki/Shors_algorithm

In any case, as I understand it, you will need to add a third step, which is to extract the correct solution from the system's state, which is also non-trivial.

Good point, I didn't think about retrieving the answer.

Is that something can be done with gates or is there another method?

Edit:

People complain about concurrent programming, they have another thing coming if quantum computers become commonplace. I suspect it will be more like programming an FPGA than a CPU.

Seems like you might be right in the short term, but I wonder if it will be true in the long term. E.g. once you get methods for doing a bunch of standard stuff you can put them together. Not sure if that works for quantum computing but maybe some other way of abstracting out the details.

Good point, I didn't think about retrieving the answer. Is that something can be done with gates or is there another method?

My (simplistic) understanding is this: you need to think of the "registers" in a qc as not storing one value but essentially a probability distribution, so your operations are really convolutions of those distributions. "reading" from the register is a measurement, which collapses the wavefunction into a set of states which happen to share the value for the attribute you are measuring. The outcome of the measurement is random but governed by the probability distribution that the system has for that attribute at that point. You need to make the desired answer stand out in that distribution (i.e. more likely to come up), otherwise you won't have gained anything vs a classical computer.

Seems like you might be right in the short term, but I wonder if it will be true in the long term.

I'm having a hard time understanding this stuff at the micro level, whereas assembly language of a classical computer is trivial in comparison. I made the FPGA and concurrency analogy because you have to account for global state, not just the state of registers touched by one instruction. Except the "global state" in a qc is a different beast entirely. I guess I don't have a clue what these abstractions might look like so I'm going to accept that you may well be right.

For performing a quantum algorithm two sets of gates are needed, for instance single qubit rotations and a square root of swap gate. A hadamard gate is another example of a universal gate. Starting up your quantum computer, you will find it in its ground state, that is the state where all qubits are in their lowest energy state. From there you start to apply q gates to the qubits. These gates make the Hamiltonian of the system evolve in time. Depending on THE sequence of gate operations on qubits, you evolve from one state to the other, performing a certain algorithm. Read out of the final state depends on the implementation of the qubit. For atoms and diamond nv centers you can use a laser. For electron spins you can use a charge detector, for flux qubits you measure a magnetic field.

Related: I'm still not satisfied with the answer as to why quantum cryptography's eavesdropper detection -- not possible with a Turing machine -- can't be embedded in a model of computation that goes beyond Turing-completeness:

http://news.ycombinator.com/item?id=955079

I've been thinking about this and the best I can come up with is the same as smanek's answer. It's not a form of computation; I'd say it's a physical concept rather than a mathematical one. Retrieving information about a quantum system's state changes that that state. Moreover, it is impossible to have a complete set of information about the system's state.

Because it is possible with a Turing machine.

http://en.wikipedia.org/wiki/Quantum_Turing_machine

http://74.125.155.132/search?q=cache:CgFC04CcivAJ:folk.uio.n...

The idea (iirc, and poorly translated into more familiar vocabulary) is that when we're running a quantum Turing machine on a regular machine, the data on the tape can be "quantum encoded". There is a specific series of steps for "decoding" it, but it's a destructive operation: decoding the data screws up the data. Decoding it a second time gives you broken data, and you know that it's broken.

(You might wonder, why don't we just write a Turing machine that can decode the data without destroying it? Well, you're free to do so, but then it's no longer a quantum Turing machine running on a Turing machine - it's no longer the same as the physics, can't be implemented directly in quantum physics, and therefore would be both slow and potentially have a tape with more slots than atoms in our universe.)

If, as the poster claims, pretty much everything we care about in the real world can be simulated with classical computers, what exactly will a quantum computer do that is in any way useful to anyone other than a scientist working on quantum computing or some other research related to quantum mechanics itself?

Solving chess. That kind of problem.

Solve "big" problems much much much faster.

What are the obstacles for a hobbyist who wants to build a simple quantum computer?

For solid state qubits (spin/flux) you need:

* e-beam lithography: expensive machine

* high quality materials (GaAs 2DEG, or reproducible Josephson junctions): you need collaboration with other scientists

* a huge supply of He4: money

* a dilution or He3 fridge with He3 in it: more money

* a lot of low-noise amplifiers and electronics: collaboration and a lot more money

And a lot of time and persistence.

Sooo... when can I launch a quantum EC2 instance?

What was I thinking joking on an American website? Sorry guys.

The guy seems like a quantum fanboy who does not understand what he is talking about. Isn't data management separate theory from the hardware - ie: using smaller objects to make computers does not change the management of the data.

Quantum computing has nothing to do with making computers smaller.

Yes, but coming up with a non binary data management system (ie: one that uses a bit in four states) requires a whole new language of machine code before you can get the quark to talk. Making one bit of info is still thirty years away from a functioning device

The author of the post is Michael Nielsen, who coauthored the standard textbook on the subject. In fact, he says so in the first full paragraph:

I worked on quantum computing full time for 12 years, wrote 60 or so papers, and co-authored the standard text.

I was a grad student at Caltech when Michael was a postdoc there, and knew him from his reputation for general awesomeness long before I met him.

N.B. Michael is also a frequent reader of Hacker News, so be nice. :-) (In fact, he submitted this article himself over a year ago: http://news.ycombinator.com/item?id=289212)

Reply on news.ycombinator.com