Dajbych.net

Q# – Introduction to Quantum Computing

, 11 minutes to read

quantum logo

Microsoft has released a new .NET language called Q# along with the Microsoft Quantum Development Kit. It contains a full-state quantum simulator. Microsoft wants to pave the path to quantum computing in datacenters able to execute powerful quantum algorithms. A quantum computer is fundamentally different from a classical binary computer. A new era of computing may be closer than you think.

What you need

How to install and run

What it simulates

Classical computers are based on binary numbers. The bit can be realized by an electric charge in the capacitor or by a magnetized area in the ferromagnetic material. Spin-based quantum computers are based on qubits. The qubit can be realized as a physical particle spin. They were proposed by Richard Feynman at the Conference on Physics and Computation at MIT in 1981.

What is spin? What else can be considered a qubit?

In quantum computing, a spin refers to the intrinsic angular momentum of particles like electrons. This property can be used to represent a qubit.

A qubit can be represented by various physical systems, such as the spin of an electron, the polarization of a photon, or the energy levels of an atom. Unlike classical bits, qubits can exist in a superposition of states, meaning they can be both 0 and 1 simultaneously.

To visualize a qubit, imagine the Earth’s rotation. The Earth’s axial tilt (the angle between the equator and orbit) is approximately 23.5°. Similarly, a qubit can be represented as a vector on the Bloch sphere, where any point on the sphere represents a possible state of the qubit.

A qubit is a unit vector in a two-dimensional complex vector space. We can measure only one component of this vector at a time, which is why qubits cannot be cloned (a principle known as the no-cloning theorem). This means we cannot duplicate a qubit in the same way we use the memcpy function in C++ to copy classical bits.

We can define the qubit more precisely as a linear combination of two vectors: |ψ⟩ = α ∙ |0⟩ + β ∙ |1⟩, where α, β ∈ ℂ.

The qubit value can be read, but this process will polarize the qubit to the state of |0⟩ or |1⟩ with a probability distribution related to whichever state is nearest. This means that quantum computers are not universally faster than bit computers. Quantum computers are faster only for a small group of algorithms.

Quantum computers had little interest until 1994. In that year, Peter Shor published an algorithm for quantum computers for integer factorization. It can be used to break the RSA algorithm. It requires 4098 qubits and 5.2 trillion Toffoli gates to compute a 2048-bit RSA key. The time complexity of breaking RSA with an n-bit key on a quantum computer is O(n³).

A quantum computer is exponentially faster than a bit computer in discrete Fourier transform. It is very good at simulating physical systems. It can be widely useful in material science, chemistry, and quantum chromodynamics.

Demystification

Myth 1

The quantum computer is faster because it can represent an exponential number of states.

A binary computer can also double the number of states when its memory is extended by a single bit. The number of states grows exponentially with the amount of memory for both binary computers and quantum computers.

Myth 2

The quantum computer is faster because the qubit can represent 0 and 1 at the same time.

Two bits can also represent 0 and 1 at the same time. Does it mean that a quantum computer is faster because it needs half the memory and a quarter of the transistors of binary computers? An analog computer can also represent a superposition of 0 and 1 at the same time. Does it mean that analog computers are faster?

Myth 3

The quantum computer allows evaluating all possible solutions in parallel.

This is not true in general. Even a binary computer can evaluate all possible solutions in parallel when the problem is simple enough. A quantum computer is also limited by the amount of memory and the number of gates.

Myth 4

A qubit can hold an infinite number of states.

Even a glass of water can hold an infinite number of states, but the problem we have is that we cannot measure the amount of water precisely. Our measurement always has some deviation. It limits us to a finite (and quite small) number of states. If a glass of water could be measured as a qubit, we would know that the glass is either empty or full.

Myth 5

The quantum computer is faster because it can evaluate the states of all qubits at once.

Currently, a 3-qubit gate is the maximum. You can combine gates and put more of them in series. Both binary and quantum computers are limited by clock frequency (or by the speed at which the voltage travels in the lead). By the way, you can configure an FPGA circuit to evaluate some operations for the whole memory. You can start with 8-bit memory and an 8-bit adder. Potentially, you can end with a GPU – which can perform operations exponentially faster than a CPU.

Myth 6

D-Wave is the first quantum computer.

D-Wave is a quantum annealer, which is far from a universal gate quantum computer. It can execute only adiabatic quantum algorithms. While the D-Wave annealer is sometimes 10 times faster than a binary computer, it is also sometimes more than 100 times slower.

Myth 7

Entangled particles allow faster-than-light communication.

This is not true because the measurement is a destructive process.

What is good to know

Superposition

Superposition is the name of a physical principle. When one person speaks in a quiet environment, you hear them. When many people gather in a small place and speak very close to each other, you hear nothing but noise. But if those people start saying the same thing at the same time as a choir, you will hear the speech much louder than in the case of a single person. Two speakers are louder than one. This principle is called superposition. You can observe the same effects with lightbulbs. Two lightbulbs are brighter than one. An eight-cylinder engine has greater torque than a four-cylinder. But the principle cannot be applied to everything. Two CPU cores aren’t twice as fast as one core (in general). Systems where superposition works are called linear.

Entanglement

Two objects can be related to each other. For example, a bike has one gear in the front and the second gear in the back connected by a chain. When one gear rotates, the second rotates as well because the chain transmits the force. The connection does not have to be necessary visible – like a gravity. An apple on the tree is connected to the Earth. When the stem snaps the apple will move towards the Earth and the Earth will move towards the apple until they hit each other.

Classical mechanic describes a light as a stream of photons. When a photon passes through two (beta barium borate) crystals (that send different polarization states on different trajectories), it splits into two photons which are interconnected. When you change the spin of the first, it effects the spin of the second. This phenomenon is called the quantum entanglement. In fact, we shouldn’t imagine two entangled particles as two separate objects, but as a single object which exists on two locations at the same time because the state between them is transmitted instantly. However, we cannot use that for communication. Two mutually entangled particles may be called differently (don’t ask me why). They are usually referred as

Qubits are physically realized as electron spins. A cooper pair of electrons are naturally formed in a superconductor. When it passes through two separate crystals (quantum dots), it becomes separated. One electron moves to the one lead and the other member of the pair to the second lead. Entangled particles in electronic circuits are generated by this principle. Microsoft has spent 12 years working on its own qubit technology based on Majorana fermions.

Quantum Teleportation

Quantum teleportation is a term for transferring a state of one qubit to another, without having to move a physical particle along with it.

We want to transfer a state of qubit ψ, which holds Alice, to Bob. To do so, we take two entangled qubits, α and β, and send α to Alice and β to Bob. Then Alice measures a superposition of ψ and α, so α′ = ψ + α. This measurement also affects β which will change to β’ in a way that β′ = β + ψ. Then Alice sends α′ to Bob through a classical communication channel. Bob will modify β′ to β′′ in a way that β′′ = β′ + α′.

We now suppose that β′′ = ψ. Let’s expand what Bob has. β′′ = β′ + α′ = β + ψ + ψ + α = ψ. The last equation needs an explanation. Two particles α and β are entangled which also means that α + β = 0. A superposition of two identical vectors is identical to original vectors because all vectors are unit vectors, therefore ψ + ψ = ψ.

What’s the point of the quantum teleportation when we still need to transfer α’ through an old-school communication channel? In the beginning, the state of α is random. Therefore α′ doesn’t disclose any useful information about ψ. This protocol can be used in the quantum cryptography to transfer one-time pad. If the source of entangled qubits (in this case photons) will be located on the satellite which will distribute them to two remote locations, we can establish a man-in-the-middle-resistant communication channel.

Q#

Q# language is a new .NET language inspired by C# and F#. If you learned those two languages, you will learn Q# very easily. It is basically C# with immutability, variable and function declaration, and tuples took over from F#.

Let’s look on the code below and explain some basic statements:

operation Teleport(msg : Qubit, there : Qubit) : () {
    body {
        using (register = Qubit[1]) {
            // Ask for an auxillary qubit that we can use to prepare
            // for teleportation.
            let here = register[0];
            
            // Create some entanglement that we can use to send our message.
            H(here);
            CNOT(here, there);
            
            // Move our message into the entangled pair.
            CNOT(msg, here);
            H(msg);

            // Measure out the entanglement.
            if (M(msg) == One)  { Z(there); }
            if (M(here) == One) { X(there); }

            // Reset our "here" qubit before releasing it.
            Reset(here);
        }
    }
}

C# has methods and properties, F# has functions and members, and Q# has functions and operations. The operation declaration starts with a keyword, followed by the name and arguments, and ends with the return type. The argument name is first and the argument type is second. It is exactly like in F# and follows human thinking rather than machine processing needs.

The operation can be called from other .NET languages. The functions are pure functions – they transform input values to output values without the possibility of affecting anything else.

The qubit allocation is tied with a using block. Operations are declared in a namespace. When we open a namespace, we can use operations from it. This is the same concept as the C# using keyword for accessing all types from it. Operations H and CNOT are declared in the Microsoft.Quantum.Primitive namespace.

The H function will produce a |0⟩ or |1⟩ with equal probability. It is like flipping a coin. The CNOT function flips the second qubit when the first qubit is |1⟩. The M function returns Zero or One, whichever is closest. The Z function is a Pauli Z gate. It rotates the vector in the Bloch sphere around the Z-axis. The X function is a Pauli X gate. It flips the vector around the X-axis. It is equivalent to a NOT gate for bit computers.

The Teleportation Sample doesn’t transfer any information to another location. It is an in-place test of the quantum teleportation algorithm implemented in Q#.

How to provide feedback

You can report problems on GitHub. At this point, Microsoft is not ready to accept pull requests. You can also vote for or submit suggestions on UserVoice.