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.