# CHAPTER 10

# QUANTUM VERSUS CLASSICAL COMPUTING

## INTRODUCTION^{*}

### Need for Computational Force Beyond the Brain

In Chapter 9 we examined the topic of NP-complete problems. These problems cannot be solved in a classical computer when there are large numbers of variables, since run times become excessive. Consideration was given to solving such problems in a logically reversible parallel computer, but such computers are limited in practice by the number of nanoprocessors that can be brought to bear on a problem. The number of nanoprocessors must be no less than the length of a truth table for those problems that can be expressed as a SAT problem. Estimates using current technology were about 2^{50} nanoprocessors. This corresponds to about 1 quadrillion (10^{15}), comparable to the quantity of synapses in a human brain, but not enough for the sorts of hard problems being considered.

The future may see *nanobrains*, defined as molecular-sized nanoprocessors. A revolutionary development like this could vastly increase available nanoprocessors to well beyond current estimates. If this occurs, there may be a practical solution to reasonably sized NP-complete problems. Nanobrains would be great, but lamentably, none are yet available.

The working particles in a quantum computer have sizes comparable to those of molecules and even smaller. Quantum computers come with a host of mysterious advantages and disadvantages along with hope for solving hard problems. In this chapter we attempt a simplified explanation ...