Quantum Computing Notes

Quantum computing exploits quantum behaviors, such as superposition and entanglement, to perform computations; it is thanks to these behaviors that NP-hard problems can be solved in a reasonable time (NP-hard problems are combinatorial in nature, their solution involves the determination of optimal combinations). It must be stressed that quantum computing is just another weapon in our computational arsenal, a weapon particularly suited to solve certain types of problems, .i.e., it is not suited to solve all computational problems; this power is accessible as a service through frameworks, such as OpenCL, in the same maner as GPUs, DSPs, FPGAs.

The fundamental unit of quantum information is the quantum bit, a.k.a. qubit, a boolean entity much like the bit of classical computing; also, while classical bits are processed with classical logic gates, e.g., NOT, AND, OR, qubits are processed with quantum logic gates, e.g., X, H, Z. Quantum circuits are comprised of quantum logic gates and quantum programming is the art of combining quantum logic gates to solve problems.

Classical bits can be in the 0 or 1 state, qubits, thanks to superposition, can be in both states simultaneously. The quantum state of a qubit collapses probabilistically to 0 or 1 when measured (observed): it is this fuzzy behavior that makes the qubit powerful. The control of the probabilistic tendency of a qubit to collapse to 0 or 1 is at the heart of quantum computing, this control is what quantum logic gates are all about—knowledge of probability theory is a must.

To put this type of computation in perspective, let’s imagine a 3D landscape with plains, hills, valleys and mountains; each point on the surface of this landscape has an elevation relative to some reference; mathematically, a point P(x, y) of this landscape lies at the elevation E_P. Without loss of generality, x, y and E_P can be normalized, i.e., scaled such that their minimum value is 0.0 and maximum 1.0. The x and y coordinates represent two distinct quantified states while E_P the probability of behaving in a certain way…

1. Given a state what is the best behavior
2. Given a behavior what is the best state

Our task is finding those P whose E falls within a given range. Peaks and valleys on our landscape represent local maxima and minima elevations, these points are interesting features for they indicate states of maximum, minimum expressions of the behaviour we are interested in.

Extend the 3D analogy to N dimensions with M behaviors, e.g., an autopilot configuration with N-M input states and M output behaviors.