Re: Are there situations that quantum computers cannot handle?

There has been been a great interest in quantum computing lately, and with good reason. They have the potential to solve certain types of problems very quickly. In fact, many questions about quantum computing have appeared on the MadSci network before. In particular, the answers to " What is a qbit when we talk about quantum computers, and how do they work? " and "What are the advantages of quantum computing?" contain several helpful links to find out more about quantum computers and their advantages and limitations.

To answer your specific inquiry concerning neural nets, unfortunately neural nets are incompatible with quantum computing. There is an excellent set of lecture notes on neural nets here. Roughly speaking, one of the features of neural nets is that they contain subunits with similar properties to actual neurons. Most importantly, they examine the set of inputs to the artificial neuron and based on those inputs construct an output for that neuron. For example, suppose I have a neuron with two inputs that are either 0 or 1 and one output that is also 0 or 1. If the sum of the inputs is 1 or 2, the output of the neuron is 1, if the sum is 0, the output is 0.

On of the key features of quantum computers (again I recommend checking out the links above) is that the algorithms are reversible. One consequence of this fact is that given the output of a quantum algorithm I should be able to figure out what the input was. For instance if I input 15 and the factoring algorithm gives me 5 and 3, I can reverse the algorithm by multiplying 5 and 3 to obtain 15.

Here's the problem: our example neuron is not reversible! Given an output of 1, I don't know what the values of the two inputs was. They could both be 1, or one 1 and the other 0. This means that a neuron is not reversible and so cannot be implemented by a quantum computer. In Boolean logic terms, an AND gate can be implemented using a neural net, but a quantum computer cannot construct an AND gate.