Microsoft has released a new .NET language called Q# along with Microsoft Quantum Development Kit. It contains a full state quantum simulator. Microsoft want to pave the path to quantum computing in datacenters able to execute powerful quantum algorithms. A quantum computer is fundamentally different than a classical binary computer. A new era of computing may be closer than you may think.
What you need
- Processor with AVX (Advanced Vector Extension) support – since Intel Sandy Bridge (Q1 2011) or AMD Bulldozer (Q3 2011).
- Windows 7 (64 bit) SP1 or newer.
- English system culture. Compilator has an annoying bug which limits its usage to English systems only.
How to install and run
- Install Microsoft Visual Studio 2017 Community Edition.
- Install the Quantum Development Kit extension for Visual Studio 2017.
- Clone the Microsoft/Quantum repository to your hard drive.
- Open the QsharpLibraries.sln.
- Set the Samples\Introduction\TeleportationSample as a Startup project.
- Hit F5.
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 on Conference on Physics and Computation at MIT in 1981.
What is the spin? What else can also be considered as a qubit? The qubit can be represented by Earth’s rotation. We know that the Earth axial tilt (an angle between equator and orbit) is 23°. The qubit is a unary vector. We can read only one component of the vector. It implies that the qubit cannot be cloneable. With a qubit, we cannot do the same thing as memcpy function in C++.
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 qubit to state of |0⟩ or |1⟩ with 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 of interest until 1994. In that year Peter Shor published an algorithm for quantum computer 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 n-bit key on quantum computer is O(n³).
Quantum computer is exponentially faster than bit computer in discrete Fourier transform. It is very good in 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.
The binary computer can also double a number of states when its memory is extended by a single bit. The number of states grows exponentially with amount of memory for both binary computer and quantum computer.
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 quantum computer is faster because it needs half of memory and quarter of transistors than binary computers? The analog computer can also represent a superposition 0 and 1 at the same time. Does it mean that analog computers are faster?
Myth 3
The quantum computer allows to evaluate all possible solutions in parallel.
This is not true in general. Even the binary computer can evaluate all possible solutions in parallel when the problem is simple enough. Quantum computer is also limited by amount of memory and by 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 we cannot measure amount of water precisely. Our measurement always has some deviation. It fixes us to a finite (and quite small) number of states. If a glass of water can be measured as a qubit we would know that the glass is empty or full.
Myth 5
The quantum computer is faster because it can evaluate states of all qubits at once.
Currently, 3-qubit gate is a maximum. You can combine gates and put more of them in serial. Both binary and quantum computers are limited by a clock frequency (or by a speed at which the voltage travels in the lead). By the way, you can configure FPGA circuit to evaluate some operation for whole memory. You can start with 8-bit memory and 8-bit adder. Potentially you can end with GPU – which can perform operations exponentially faster than CPU.
Myth 6
D-Wave is the first quantum computer.
D-Ware is a quantum annealer, which is far away from universal gate quantum computer. It can execute only adiabatic quantum algorithms. While the D-Wave annealer is sometimes 10 times faster than the binary computer, it is also sometimes more than 100 times slower.
Myth 7
Entangled particles allow faster than speed of light communication.
This is not true because the measurement is a destructive process.
What is good to know
Superposition
The superposition is a name of physical principle. When one person speaks in a quiet environment you hear him. When many people gathered in a small place are speaking very close to each other you hear nothing but noise. But when those people would start saying the same thing at the same time as a choir, you will hear the speech much louder than in 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. The eight-cylinder engine has greater torque than a four-cylinder. But the principle cannot be applied to everything. Two CPU cores aren’t two times faster than 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
- entangled pair, or
- EPR pair (Einstein–Podolsky–Rosen), or
- Cooper pair, or
- Bell state.
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 keyword, the name and arguments follows, and ends with the return type. The argument name is first and the argument type is second. It is exactly like in F# and it follows a human thinking rather than machine processing needs.
The operation can be called from other .NET language. 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 using block. Operations are declared in a namespace. When we open some namespace, we can use operations from it. This is the same concept as C# using keyword for accessing all types from it. Operations H and CNOT are declared in 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 Bloch sphere around Z-axis. The X function is a Pauli X gate. It flips the vector around X-axis. It is equivalent to 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.