Monday, 28 August 2017

Quantum speed-up in Simon's problem

It has been said that quantum computers will allow us to perform certain computations faster than the regular PCs of today. While this sounds like a remarkable technological advance, it is necessary to clarify what is meant by this:

1. A recipe for solving a computational problem is called an algorithm.  In order to compare the speed of classical and quantum algorithms, we need a way of counting computational steps for classical and quantum algorithms that is fair to compare.

2. How many steps an algorithm needs depends on whether it receives an easy or hard instance of the problem.  Typically we are interested in algorithms that work the best on average. Another issue is that for the algorithms that we do know, we don't usually know if they are the best that we can do (you can sometimes prove a classical algorithm is optimal by using lower-bound arguments). So here  we are really comparing quantum methods with best as-of-yet classical methods. Put differently, it maybe the case (though many believe it unlikely) that classical and quantum computers have the same computational power; we just have not found the best classical algorithms that match the performance of quantum ones.

Here I will describe a problem for which quantum computers have a distinct advantage over classical ones. It is an example of what is called a black-box problem in computer science.

Thursday, 22 September 2016

The BB84 protocol for quantum key distribution

The most successful application of quantum theory to cryptography is quantum key distribution (QKD). The goal of QKD is to generate an identical string of bits that is privately shared between two parties, which we shall call Alice and Bob.

The particular QKD scheme that we will describe was proposed by Charles Bennett and Gilles Brassard in 1984, and is often referred to as BB84.

The protocol has two main parts, a quantum and classical phase. In the quantum phase, Alice sends single photons to Bob over some public quantum channel. In the classical phase, Alice and Bob need to talk to each other over an authenticated classical channel, that is, it can be public but they need to verify that they are talking to the correct person.

Friday, 15 July 2016

The CHSH game and quantum entanglement

A simple setting for demonstrating the usefulness of entanglement involves a two-player game known as the CHSH game. The game is a variant of an experimental setup (by Clauser, Horne, Shimony and Holt) that is often used to illustrate Bell's theorem.

We shall call the two players 2 players Alice and Bob. We will also have Charlie as a referee that decides if Alice and Bob wins the game. They can decide on any strategy before the game commences but they cannot communicate with each other once the game starts.

To begin, Charlie picks two uniformly random bits $x$ and $y$, and gives $x$ to Alice and $y$ to Bob. Alice answers the referee with bit $a$, while Bob replies with bit $b$. After getting $a$ and $b$, Charlie checks whether

$a \oplus b = xy \mod{2}$,

that is, that the XOR of the output bits $a$ and $b$ is equal to the AND of input bits $x$ and $y$. If so, then Alice and Bob win the game.

Sunday, 22 March 2015

The uncertainty principle and wave-particle duality are equivalent

In the 17th century, physicists debated over the true nature of light. When he observed that light is split into different colors by a prism of glass, Isaac Newton hypothesized that light is composed of particles he called corpuscles, which undergo refraction when they accelerate into a denser medium.

At around the same time, Christian Huygens proposed that light is made up of waves. In his treatise published in 1690, he described how light propagated by means of spherical waves, and explained how reflection and refraction occurs.

In 1704, Newton published Opticks, expounding on his corpuscular theory of light. The debate raged over whether light was a particle or a wave for almost a century, and was not settled until Thomas Young's interference experiments with double slits, which could only be explained if light was a wave.

The story did not end there. In 1901, Max Planck was able to explain the energy curve of blackbody radiation by supposing that light was emitted in small packets of energy. Planck thought of this light particles, or quanta, as a convenient mathematical device and did not believe them to be real. However, when the photoelectric effect was discovered in 1905, Albert Einstein showed that it could be explained in terms of wave packets of light we now call photons. In 1927, Louis de Broglie constructed a pilot wave theory that attempted to explain how particle and wave aspects of light can coexist.

Friday, 13 March 2015

The monogamy of entanglement

Quantum information theory has taught us that entanglement is a useful resource for communication and information processing. As with any other resource, we would like to describe the properties of entanglement quantitatively, to help us determine the various ways in which it can be manipulated. One particular question that might come to mind is this: to what extent can entanglement be shared among different objects?

The answer to this question leads us to an important fundamental property of entanglement called monogamy: if two objects are maximally entangled to each other, then neither object is entangled to a third one. More generally, it says that the stronger the entanglement between two objects is, the weaker their entanglements are with other objects.

Friday, 4 July 2014

An arbitrary quantum cannot be cloned

One of the early important results in the study of quantum information is the no-cloning theorem, which tells us that there is no quantum operation that allows us to create multiple copies of an arbitrary quantum state.

This property is very different from what we expect from classical information, which you may reproduce as many times as you wish. For example, you can send a PDF file by email to many recipients while keeping a copy to yourself. The important point is that whatever the contents may be, you can make a duplicate of it.

Now consider a cloning machine M for qubits that can produce identical copies of the states |u) and |d):

M |u) |0) = M |u) |u),
M |d) |0) = M |d) |d) ,

where |0) denotes any fixed initial state for M. This is necessary in pretty much the same way you would need a blank piece of paper before you can photocopy a printed document.

Friday, 13 June 2014

How to teleport a qubit

One of the fascinating things we can do with quantum entanglement is a scheme called quantum teleportation. In the original proposal by Charlie Bennett, Gilles Brassar, Claude Crepeau, Richard Jozsa, Asher Peres and Bill Wootters, it describes a way to transmit an arbitrary quantum state between two parties who may be far apart, using only a Bell state shared between the two parties, a few qubit operations that each party can perform independently, and two bits of information that can be communicated by one party to the other.

Suppose Alice and Bob are in separate locations but they share a pair of electrons that are in the entangled state

|E) = (|u,u) + |d,d)) / sqrt(2)

where as usual |u) denotes the state of an electron having its spin pointing in the up-direction, |d) denotes that with spin in the down-direction, and |u,u) refer to the state of the first and second electrons, respectively. Let's say that Bob has the first electron on his side and Alice has the second electron on her side.

Alice also possesses a third electron in the state

|q) = a |u) + b |d)

and she wants Bob to obtain this state. If Alice does not know what the value of a and b precisely, she can not clone the state and send a copy to Bob. However, since Alice and Bob have shared entanglement, it is possible to transfer the state of this electron into Bob's electron using teleportation, which is shown in the figure below.