Quantum bit, or qubit for short, is described as mathematical objects with specific properties, though this can be realized as actual physical systems.
As a classical bit has a state - either 0 or 1, a qubit has a state.
It is also possible to form linear combinations of states, called superpositions:
where
The particular states
Remarkably, we cannot examine a qubit to determine its quantum state, i.e., the values of
Generally, a qubit's state is a unit vector in a two-dimensional complex vector space.
In contrast to our 'common sense', a qubit can exist in a continuum of states between
Example. a qubit in the state
An electron can exist in either 'ground' or 'excited' states, which we'll call
Since
where
Actually,
Figure 1.3. Bloch sphere representation of a qubit. Metionably, this contains only the case that the coefficient of Though paradoxically, there are infinite points on the unit sphere, information represented by a qubit cannot be infinite. Recall that measurement of a qubit will give only either 0 or 1. Furthermore, measurement changes the state of a qubit, collapsing it from its superposition of
Example. If the measurement of
1.2.1 Multiple qubitsSuppose we have 2 qubits. These two qubits form a qubit system, which has 4 computational basis states, denoted
Similar to the case for a single bit, the measurement result
Explain. Measuring the first qubit, we get 0 with probability
Combine them to get the previous probability distribution result.
Example. An important two-qubit state is the Bell state or known as EPR pair,
Note that this means if we measure the first and obtain 0 (with 1/2 probability), then the post-measurement state is
More generally, consider a system of
1.3 Quantum ComputationA quantum computer is built from a quantum circuit containing wires and elementary quantum gates to carry around and manipulate the quantum information. In this section, we describe several simple quantum gates, as well as examples illustrating their application.
1.3.1 Single qubit gatesThe only non-trivial member of single-bit logic gates is the NOT gate, whose operation is defined by its truth table, in which
Similarly, the quantum NOT gate acts linearly, i.e.,
Though, linear behavior is a general property of quantum mechanics and well-motivated empirically.
So, we may simply express the quantum NOT gate in matrix form,
and express the quantum state as
More generally, if we want any single-qubit gate (linear), one can always use a 2-by-2 matrix to express it. But, as constrained by normalization condition, actually, any single-qubit gate is isomorphic to a unitary 2-by-2 matrix
Two other important single qubit gates are
The
Visualization of the Hadamard gate. Rotate 90 degrees alone It turns out that any single-qubit gate can be decomposed into 3 rotations.
Theorem. Any 2-by-2 unitary matrix may be decomposed as
A proof is given later in section 4.2.
1.3.2 Multiple qubit gatesAn important theoretical result in classical gates is that any function on bits can be computed from the composition of NAND gates alone, which is thus known as a universal gate. By contrast, the XOR gate alone, even together with NOT is not universal.
The prototypical multi-qubit quantum logic gate is the controlled-NOT or CNOT gate for short. It takes two input qubits, known as control qubit and the target qubit, respectively.
Visualization of two-bit gates. Left are classical gates, and the right is the CNOT gate and its matrix representation. (In the order of The action of the CNOT gate is described as follows. If the control qubit is set to 0, the target qubit is left alone. If the control qubit is set to 1, then the target qubit is flipped. Or, another way to describe it is as a generalization of the classical XOR gate, as
While noticing that unitary quantum gates are always invertible, thus for classical NAND and XORgate, they cannot be understood as unitary gates.
Of course, there are many interesting quantum gates other than CNOT, but in the sense of prototype, we have the following theorem.
Theorem. Any multiple-qubit logic gate may be composed of CNOT and single-qubit gates. The proof is given in section 4.5, which is the quantum parallel of the universality of the NAND gate.
1.3.3 Measurements in bases other than the computational basisActually, quantum mechanics allows somewhat more versatility in the class of measurements. Instead of choosing
It turns out that it is possible to treat them as though they were computational basis states. Naturally, measuring result in '+' with probability
More generally, given any basis states
1.3.4 Quantum circuitsA wire in the quantum circuit does not necessarily correspond to a physical wire; it may correspond instead to the passage of time or perhaps to a physical particle such as a photon travels through space.
Above is a simple but useful task which swaps the states of the two qubits. Remember that we can perceive the CNOT operation as modulo 2 addition.
Swapping two qubits, and an equivalent schematic symbol notationThere are a few features allowed in classical circuits that are not usually present in quantum circuits.
No loops allowed. We say the circuit is acyclic.FANIN, i.e., joining wires together, is not allowed (Since the OR operator is not unitary)FANOUT, i.e., spreading copies of a bit, is not allowed. (It is not possible in quantum mechanics!)Also, we can define a controlled-
Suppose A measuring operator is denoted as a 'meter' and outputs a classical bit
Measuring a qubit.1.3.5 Qubit copying circuit?Consider the task of copying a qubit in the manner we copy classical bit using the CNOT gate.
Attempting to copy a qubit.We actually get different result from
In fact it is impossible to copy an unknown qubit.
To understand why this is not a copy, remember that measuring one qubit only obtains part of its state information. After measuring the first cubit, the second copy should not be interfered with and contain originally much more information. While, in this case, the second copy lost its information. Therefore this is not a copy.
1.3.6 Example: Bell statesBell statesBell states, as well as known as EPR states and EPR pairs is denoted as
1.3.7 Example: quantum teleportationAssume Alice and Bob are agents going to work in different areas and want to share some secret information encoded in qubits after their separation. Here is how this can be done by quantum teleportation. Before departure, they together generated an EPR pair, each taking one qubit of the EPR pair. Then, when Alice wants to send a secret information
Quantum circuit for teleporting a qubit. The top two lines are Alice's system.She first interacts
States at each timestamp is listed as (take
There's a lot to mention in this process.
One cannot send information faster than light. Since in this setting, we need a traditional transmission, and this prevents transmitting faster than light. Without the information Alice gives, Bob actually got no useful information.Actually, this does not copy but does teleport a qubit. Since Alice only remains measured traditional bits.1.4 Quantum AlgorithmsWhat class of computations can be performed using quantum circuits, and how does that class compare with those computations done by classical logical circuits? Is there any task that a quantum computer may perform better than a classical computer?
1.4.1 Classical computations on a quantum computerCan we simulate a classical logic circuit using a quantum circuit? Yes. Though, one must be careful when designing circuits since quantum logic gates are unitary, inherently reversible, whereas many classical logic gates such as the NAND gate are irreversible.
Example. Toffoli gate, or known as CCNOT gate, is a reversible gate that has 3 inputs and 3 outputs. Two control bits are unaffected by the action of the Toffoli gate. In the third bit, the target bit is flipped if both control bits are set to 1. The inverse is itself.The NAND gate thus can be used to simulated by setting
What if the classical computer is non-deterministic, that has the ability to generate random bits to be used in the computation. Obviously, it is easy for a quantum computer to do this. Only applying a Hadamard gate is enough.
1.4.2 Quantum parallelismQuantum parallelism is a fundamental feature of many quantum algorithms. It allows quantum computers to evaluate a function
Suppose
This procedure can easily be generalized to functions on an arbitrary number of bits, by using a general operation called Hadamard transform.
1.4.3 Deutsch's algorithmThis shows how quantum circuits can outperform classical ones by implementing Deutsch's algorithm.
Simply analysis shows that
So only one evaluation of
1.4.4 The Deutsch-Jozsa algorithmExample. Deutsch's problem. Alice, selects a number
In the classical case, Alice needs up to
and
Then, interferes terms,
which gives
Carefully we examine the result in
To sum up, measure
1.4.5 Quantum algorithms summarizedBroadly speaking, there are 3 classes of quantum algorithms that provide an advantage over known classical algorithms.
Algorithms based upon quantum versions of the Fourier transformQuantum search algorithms