Tuesday, 15 May 2018

Quantum machine learning algorithm for supervised cluster assignment

Machine learning refers to various methods for deriving patterns from data that can be used to interpret new inputs. This is what is meant by computers that can "learn" without being explicitly programmed. Machine learning techniques are often associated with the development of artificial intelligence, but they are also prevalent in applications that involve large amounts of data, such as in image and speech recognition, and in risk assessment for business and finance.

Broadly speaking, there are three forms of machine learning: (i) supervised, in which a machine infers a function from a sample of input-output relations (called training data); (ii) unsupervised, in which a machine tries to uncover a hidden structure from assorted data;  and (iii) reinforced, in which a machine attempts to develop a strategy for winning a game given a set of rules and objectives.

Formally, machine learning techniques involve data represented as vectors in a high-dimensional space. As it turns out, quantum information has taught us that quantum computers are good at manipulating high-dimensional vectors for certain tasks. The general aim of quantum machine learning is to develop quantum algorithms that exhibit significant speedup over classical machine learning techniques.

In many cases, the quantum learning approach seems to amount to running a classical learning problem on a quantum computer, hoping to find a speedup. But in other cases such as neural networks or Bayesian decision theory, the approach is to translate stochastic methods into the language of quantum information, hoping to develop purely quantum methods with no real classical counterpart.

Tuesday, 27 February 2018

Nonlocality, steering, and entanglement

The nonlocality of quantum theory was first pointed out by Albert Einstein, Boris Podolsky, and Nathan Rosen, collectively known as EPR, in a 1935 paper that argued for the incompleteness of quantum mechanics.

The gist of their argument can be seen through an example due to David Bohm, who considered the state

$|\Psi\rangle = \dfrac{|00\rangle + |11\rangle }{\sqrt{2}} = \dfrac{|++\rangle + |--\rangle }{\sqrt{2}}, $

also known as an EPR pair, which here we expressed in both the standard basis $\{ |0\rangle, |1\rangle \}$ and Hadamard basis $\{ |+\rangle, |-\rangle \}$.

Suppose Alice gets the first qubit and Bob gets the second qubit. If Alice measures her qubit in the standard basis, she immediately projects Bob's qubit onto either the state $|0\rangle$ or $|1\rangle$. She produces a similar kind of projection of Bob's system if she measures in the Hadamard basis.

This seems problematic because it suggests that Alice can affect Bob's qubit even though their qubits no longer interact, in which case you would expect that nothing that Alice does on her qubit should influence Bob's.

Einstein, Podolsky, and Rosen thought (incorrectly as it turns out) that this nonlocal effect implies that the quantum state provides an incomplete description of Alice and Bob's physical systems. They attempt to support this intuition by arguing that one might be able to explain what Bob obtains if he measures his qubit through local hidden variables (LHV) that are missing from quantum theory.

Like EPR, Erwin Schrödinger was bothered by the idea of nonlocality. However, unlike EPR, Schrodinger believed that a quantum state provided a complete description of a local, isolated system.

Tuesday, 20 February 2018

Quantum security from an uncertainty game

The uncertainty principle of quantum theory limits how much Eve can predict about the outcomes of two incompatible measurements on Adam's state.

We will consider a guessing game that shows security against an eavesdropper Eve who can prepare quantum states but otherwise store and process classical information only. For example, Eve is allowed to make measurements on a qubit during its transmission but she does not possess any quantum memory for storing quantum states that she might entangle with the qubit.

In such a setting, Eve's actions effectively chooses the state of the qubit sent to Adam, since she would know as much as she can about the qubit if she had prepared it herself. This situation can be analyzed in terms of the following guessing game, to be played by Adam and Eve:

1. Eve prepares a qubit $| \psi \rangle$ and sends it to Adam.
2. Adam chooses a uniformly random bit $\theta$. If $\theta = 0$, Adam measures $| \psi \rangle$ in the standard basis $\{ |0\rangle, |1\rangle \}$. If $\theta = 1$, Adam measures $| \psi \rangle$ in the Hadamard basis $\{ |+\rangle, |-\rangle \}$, where $|\pm\rangle = (|0\rangle \pm |1\rangle )/ \sqrt{2}$.
3. Adam records a bit value $x$ as his measurement outcome. (By convention, $|+\rangle$ corresponds to bit value 0.)
4. Adam reveals the measurement basis $\theta$ to Eve.

Eve wins the game if she correctly guesses the value of $x$.

Saturday, 10 February 2018

Delegated quantum computation

Suppose Alice wants to perform a quantum computation. She can implement some basic quantum gates on the state $|0\rangle$ but she does not own a fully-functional quantum computer. Bob runs a company that sells time on their quantum computer and thus offers his services to Alice. But Alice does not trust Bob. In particular, she does not want Bob to learn her quantum state at any point during the calculation. Is there a way for Bob to help Alice securely? Yes, this is a problem that can be solved by delegated computation.

In the task of delegated computation, Alice has an input $|q\rangle$ and a classical description $\mathsf{C}$ of the quantum circuit and she wants to obtain the output $\mathsf{C}(|q\rangle)$. Alice and Bob exchange a few messages, at the end of which Bob obtains a result $|r\rangle$, which he sends to Alice. Ideally, we want the protocol to be correct, verifiable, and blind.

The protocol is said to be correct if Alice accepts Bob's result and $|r\rangle = \mathsf{C}(|q\rangle)$ when both parties are honest. The protocol is said to be verifiable if for any cheating Bob, Alice either aborts or  finds $|r\rangle = \mathsf{C}(|q\rangle)$. The protocol is said to blind if for any cheating Bob, at the end of the protocol, Bob learns nothing about $|q\rangle$ or $\mathsf{C}$.

Thursday, 1 February 2018

A simple protocol for quantum oblivious transfer

One of the goals in cryptography is to allow parties who do not trust each other to solve problems together. One important problem that can be solved using such a secure multiparty computation is called secure function evaluation (SFE).

In SFE, we have two parties Alice and Bob who each hold some private data. Alice wants to use Bob's data to compute some function on her side, while Bob wants to use Alice's data to compute some function his side. The goal is to allow Alice and Bob to compute their functions without having to reveal their secrets.

We can describe a SEF protocol as follows: Denote Alice's secret input by $x$ and Bob's secret input by $y$. Alice and Bob can send messages to each other. At the end of the protocol, Alice outputs $a$ and Bob outputs $b$. Alice wants to compute the function $A(x,y)$ while Bob wants to compute $B(x,y)$.

If the protocol is correct, then $a = A(x,y)$ and $b = B(x,y)$ for honest Alice and Bob. If the protocol is secure, then Alice cannot know anything about Bob's input $y$ except what she might deduce from $A(x,y)$. Similarly, Bob cannot know anything about Alice's input $x$ except what he might deduce from $B(x,y)$.

Let us consider an example of SFE called oblivious transfer (OT). In an OT protocol, Alice has two input bit strings $s_0$ and $s_1$, and Bob has input bit $t$. Alice does not need to compute anything but Bob wants to retrieve $s_t$. An OT protocol is secure if Alice does not find $t$ and also if Bob only gets one of Alice's strings.

Suppose Alice has a database with two records $s_0$ and $s_1$. Bob wants to retrieve one of the records but he does not want Alice to find out which one. Meanwhile, Alice is willing to grant Bob access to one record, but not to the entire database. This is a practical problem that can be solved with OT.

Sunday, 31 December 2017

Grover's algorithm for the unstructured search problem

After Peter Shor showed how quantum computers can factor numbers efficiently, interest surged in finding other problems which quantum methods solved faster than the best known classical techniques. In 1996 Lov Grover developed such a quantum algorithm for solving the unstructured search problem.

In a generic search problem, we are given a set $S$ of $N$ items. Some of the items in the set are marked. Our task is to find a marked item in the set $S$.

You can think of a search problem like looking up a name in a list. In most cases, the list will be arranged in a way that makes finding names easier. For example, a list of names is often sorted alphabetically. Here we are talking about a list with no discernible ordering. In this case, the best we could do is to check each entry for the desired name.

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.