Chapter 23: Quantum Computing
Peter M. Kogge · Society for Industrial and Applied Mathematics eBooks · 2022
Quantum computing involves performing computations using devices that are governed by the rules of quantum mechanics170 rather than classical Newtonian physics. The effect of such a difference runs deep. First, and definitely unconventional, a quantum device’s state need not be a single value at a time, but can simultaneously hold an infinite number of possible state values. Next, much like the magnets of the Ising computing model (Chapter E11), if initialized properly, two or more quantum devices may exhibit quantum entanglement where a quantum state of any one device cannot be described independently of the others in the group. Manipulating one device results in changes to the state of the others. Together this means that a “quantum memory” can simultaneously contain an enormous number of different possible values and that applying a single operation to the group is like applying the operation to the ensemble of all states maintained in the system, simultaneously. If this becomes practical then the crystal ball analogy for NP problems (Section 7.5.4) becomes practical in polynomial time, and thus we would have achieved what is called today quantum supremacy.