QEF03 – Basics of Quantum Computing

The approach which we’ll be following is based more on quantum computing than on quantum mechanics per se, so let’s have a look at how these quantum computers work.

Quantum computers are based on qubits which are in a superposed state, so one big difference between them and classical computers is that they’re inherently probabilistic – you have to run a simulation many times and then sample the output .

The basic mathematical tool we’ll be using is the Hilbert space. This can be viewed as a generalization of Euclidean space, with the difference that there are complex coefficients. Quantum probability involves negative probabilities (in the sense of projections) so we need complex numbers for example when we take the square root of a probability.

The dual state is the complex conjugate of the transpose of , also called the Hermitian conjugate, which is written as .

The inner product between two elements and is denoted , and is analogous to the dot product in a normal vector space, with the difference that the result can again be complex. The norm of is given by which is a non-negative real number.

The outer product is denoted , and is like multiplying a column vector by a row vector.

A unitary matrix is one whose inverse is its conjugate transpose. Unitary matrices preserve probabilities and play a big role in quantum computing, where logic gates are represented by unitary matrices that act on qubits. An example of a gate is the NOT gate which has the effect of flipping a qubit, so if the input is then the output will be . There’s the Hadamard gate which we’ve already seen. It takes a an input of say and puts it into a superposed state. There’s a rotation gate which simply rotates the qubit by an angle , so if the input is then the output will be a superposed state which has the probability of being measured in and of being measured in . The symbol for measurement is the gauge symbol.

Multiple qubits are denoted as a tensor product , so two qubits gives you a column vector with four elements.

A state in a Hilbert space is entangled if it does not factor as a tensor product of the form where and . For example , which has an equal probability of being observed in the state or , is not entangled because it can be written as a tensor product; however the state , which has an equal probability of being observed in the state or , cannot be similarly decomposed, so is entangled.

Gates can act on multiple qubits, as in the figure below which shows a quantum circuit with three qubits. The gate on the right is a NOT gate which flips the bottom qubit. The middle gate is a C-NOT gate which acts on two qubits. The third qubit acts as a control, and the second qubit is flipped depending on the state of the control. The Toffoli gate on the left is similar but acts on three qubits: it flips the state of the first qubit depending on the state of the two control qubits.

A quantum circuit to increment a counter

If we analyse the effect of this circuit, we find that , , and so on. The circuit therefore has the effect of incrementing a binary counter.

Another circuit that we’re going to be using quite a lot is the two-qubit figure one shown in the figure below. We have a unitary matrix acting on the first qubit which might for example rotate that qubit around in a particular direction, and the same thing for the lower qubit. Then the top qubit is going to be acting as a control on the second one. As we’ll see this circuit can be used in quantum cognition, where the top qubit can represent a context for a decision, or also in quantum finance where we’re going to be using this to model the debt relationship.

A useful circuit

Previous: QEF02 – Quantum Probability and Logic

Next: (coming soon)