Anybody interested in possible operation/use of quantum computers?

Question

I went through a period of being interested in how quantum computers work and what they might be good for if they ever become practical. I know they are talked about for code-breaking. I was interested is using them for validating software by essentially trying all possible inputs (in parallel) and seeing if any error states are reached.

I know it's a bit of a blue-sky question, but I wonder if others are interested in quantum computers, how they might work, and what they would be useful for.

Added: Just for fun, let me throw out a mini-tutorial:

Suppose you've got N bits of memory to play with. Suppose you can load those bits (or some of them) with your input data. Then suppose there is a finite sequence of operations you can do on them (without using any additional memory) leaving the answer in them.

To do this with a quantum computer, it is only necessary that you make sure that the entire computation is reversible, by reserving some of the bits to record branches you took, so you can undo them. If you do that, then all the operations can be written as simple unitary matrix transformations on the N bits. (A unitary transform is a pure rotation in the N-dimensional coordinate system.) So performing the computation consists of applying a succession of pure rotations on the bit-vector.

If you do this, then if the N-bit vector is in a quantum computer, it can be initialized into a state where all 2^N (or fewer) possible inputs are superimposed at the same time in "parallel universes". Then if you do the computation, it is doing them all at the same time.

Now all you have to do to see if one of the inputs gives you a particular answer is to let it run to a particular state. If you halt it and examine the state, what it does is choose one of the universes at random and throw away all the rest. So what the Grover algorithm lets you do is, without halting it, accentuate the probability of the universes with the answer state. Then you run it forward, then backward, then forward, and so on for a number of iterations until the answer universe has very high probability. Then if you examine it, you have a high probability of seeing the answer you want.

Whew...

Answer 1

I'm mildly interested, as I am in all science, but honestly I haven't spent a moment investigating them very deeply or thought about how they could be applied to problems that I work on. There's still so much for me to learn about how we apply the von Neumann-esque architectures that we use today.

Maybe multiple cores and massive parallelization is a half-step towards those kinds of problems. But I'm only crawling in that direction.

I have no idea how I'd program them for anything useful.

Danny Hillis, of Connection Machine and Long Now fame, used a machine to write a sorting algorithm that was optimized using genetic techniques. I wonder if revisiting something like that would be a worthwhile problem? Or perhaps a stable, faster linear algebra solution?

Is yours a rhetorical question? Do you have access to such a machine, with near-term plans to try your idea?

Answer 2

A link: http://www.dwavesys.com/index.php?page=applications

Answer 3

During my Symbolic AI module at university I was asked to give a small presentation to the class on a certain subject, my subject being AI Applications. My subject in this presentation was Quantum Computing in AI.

If the information I write here is out-of-date/wrong/poor don't be too angry. I'm only a second-year CS student at a crappy university that is relying on his memory for most of these details.

The power of Quantum Computing appears to be its ability to work on things incredibly fast (due to its perceived states if I remember correctly). This will obviously completely change security, as white and black-hat hackers will jump on the opportunity to develop and stress-test the various methods of secure systems. If you're interested in Physics then this is the subject for you! If you want to read more about how Quantum Computers can be used in security by using Algorithms to factorise large numbers read this paper by Peter Shor.

Its power comes from the Qubit and a technique known as Quantum Interference. I could spend all day talking about it, but it'd be better for you to read about the double-slit experiment to see how quantum computing works.

The conventional computer compromises of logic gates, whilst quantum computers have their own. As many of these computers have been built (hard-wired) to solve certain problems there are a multitude of different QLG (Quantum Logic Gates) proposed for different problems. Functionally, Quantum Networks are formed using these gates in a method known as Gate Arrays. If you require more information on this then the Ekert paper is the way to go.

Please note that the traditional way to represent the super-positions is as unit contra-variant vectors (one per Qubit) in an 2^n-dimension Hilbert space (where n is the number of Qubits). The gates are defined as rotating these universes and inevitably transforming the Qubit. One such gate is the Hadamard Gate.

Quantum AI has a bright future, but not for a long time. Many academics see Quantum Computing as the distant future of Computing, similarly to how Charles Babbage viewed his machine.

Sorry if this answer got a bit out of hand.

Answer 4

Just to clarify, the link you have there talks about verification of finite state machines. That could be a great thing in the HW market, but from there to software verification the way is long.

In particular, software runs over at least stack automata if not over Turing machines.

In addition, software verification without manual abstraction (a-la model checking) would require you to solve the halting problem. At best, a quantum computer can bring you from NP to P, it doesn't bring you from RE to R. Even if you run any infinite item in parallel, you can't in general determine if programs end. Though it is possible that for certain programs that can work.

Either way, I'll wait till I see an OS that runs on normal computers first. I can only imagine Quantum Computing's GPF... "The universe performed an illegal action and will now implode" or something like that.

Answer 5

Are you kidding?

If half of what David Deutsch says is right this will be either the end of encryption or the end of encryption-breaking, and will make the central problems in chemistry, physics, and nano-tech knowing the question not finding the answer.