A construction for the Naimark dilation of POVMs

In quantum theory, general quantum measurements are described by the so-called positive-operator-valued measures (POVMs). In finite dimensions, they formally correspond to a set of positive semidefinite operators $E_i \ge 0$ that sum to identity, $\sum_{i} E_{i} = \mathbb{I}$. 

POVMs are useful because they allow us to calculate the probability of obtaining a particular outcome when measuring a quantum state. Namely, if we perform a measurement described by POVM $\{E_{i}\}_{i}$ on a quantum system in state $|\psi\rangle$, then the probability of getting outcome $i$ is given by $\mathrm{Pr}[i] = \mathrm{tr}\left( E_{i} |\psi\rangle\langle \psi|\right) = \langle \psi| E_{i} |\psi\rangle$.

The simplest example of a POVM is one where each $E_i$ is a projection onto a vector $|e_i\rangle$ that belongs to an orthonormal basis, that is, $E_{i} = |e_i\rangle\langle e_i|$. This is called a projective measurement. It turns out that having outcomes assigned to orthogonal operators is quite convenient for analyzing quantum experiments.

While not all POVMs are projective, a result called Naimark's dilation theorem (named after Mark Aronovich Naimark) that demonstrates how a POVM can be obtained from a projective measurement on a larger system. What this shows is that if we perform a projective measurement on a system but we have access to only part of it, then the result of that measurement on the accessible subsystem is properly described with a POVM.

 

Here we wish to describe one explicit procedure for computing the projective measurement given a non-projective POVM. Without loss of generality, we can consider POVMs where $E_i = \alpha_i |e_i\rangle\langle e_i |$, where $0 < \alpha < 1$. This is because if $E_i$ involved more terms, we can always fine-grain the POVM into one with more outcomes, find the projections for that POVM, then coarse-grain back to fewer outcomes by combining projections.

Suppose $E_i = \alpha_i |e_i\rangle\langle e_i |$ for $i = 1,2,..., n$. Then we can form the matrix by using the vector $|u_i\rangle := \sqrt{\alpha_i} |e_i\rangle$ as columns: 

$W = \begin{pmatrix} U \\ V \end{pmatrix} = \left( |w_1\rangle |w_2\rangle \cdots |w_n\rangle\right)$, where $U = \left( |u_1\rangle |u_2\rangle \cdots |u_n\rangle\right)$.

If $|e_i\rangle$ are $d$-dimensional vectors, then $U$ is a $d \times n$ matrix and $V$ is a $(n-d) \times n$ matrix so that $W$ is an $n \times n$ square matrix. If we can find $V$ such that $W$ is a unitary matrix, then the projections we want are given by the columns of $W$, that is, for the POVM element $E_i$, its corresponding orthogonal projection in the larger space is $P_i = |w_i\rangle\langle w_i|$.

The solution is not unique so any $V$ that makes $W$ unitary is valid. But how does one find such a matrix $V$? One simple way is to realize that if $W$ is unitary, then so is $W^\dagger$, so it means we want to construct a matrix $W$ with orthonormal rows and columns.

Now all we actually need is to use any matrix $V$ such that all the rows of $W$ are linearly independent. If one chooses the matrix elements of $V$ uniformly at random, this is almost surely the case, but one can also make a simple analytic choice as long as $W$ becomes full-rank, which can be checked, say by reducing to row echelon form.

Because $U$ is part of a larger unitary matrix, its rows are already orthogonal. To make the rows of $V$ orthogonal, then we can just apply the Gram-Schmidt process. Suppose after that, $V$ becomes $\widetilde{V}$ (in particular, the rows and columns are properly normalized) and we get $\widetilde{W} = \begin{pmatrix} U \\ \widetilde{V} \end{pmatrix}$. This is the desired unitary matrix: the orthogonal projections of the Naimark dilation can be constructed from the columns of $\widetilde{W}$.

To see how that all works, we provide a simple worked example. Consider the following three-outcome qubit POVM:

$E_1 = \frac{1}{4}|0\rangle\langle 0|, \quad E_2 = \frac{1}{2}|+\rangle\langle +| + \frac{1}{2}|1\rangle\langle 1|, \quad E_3 = \frac{1}{4}|0\rangle\langle 0| + \frac{1}{2}|-\rangle\langle -|$,

where $|0\rangle = \begin{pmatrix} 1 \\ 0 \end{pmatrix}, |1\rangle = \begin{pmatrix} 0 \\ 1 \end{pmatrix}, |\pm\rangle = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ \pm 1 \end{pmatrix}$.

First thing we do is split $E_2$ and $E_3$ into two parts for each term, so that when we construct the matrix $U$, it will have 5 columns: first corresponds to $E_1$, second and third to $E_2$ and fourth and fifth to $E_3$. So we have

$U = \begin{pmatrix} \tfrac{1}{2} & \tfrac{1}{\sqrt{2}} & 0 & \tfrac{1}{2} & \tfrac{1}{\sqrt{2}} \\ 0 & \tfrac{1}{\sqrt{2}} & \tfrac{1}{\sqrt{2}} & 0 & -\tfrac{1}{\sqrt{2}} \end{pmatrix}$.

It can be verified that one way to choose $V$ so that its rows are orthogonal to the rows of $U$ is

$V = \begin{pmatrix} \tfrac{1}{2} & 0 & 0 & -\tfrac{1}{2} & 0 \\ 0& -1 & \sqrt{2} & 0 & 1 \\ \sqrt{2} &-1 & 0 & \sqrt{2} & 1 \end{pmatrix}$.

Finally to have the rows (and columns) are properly normalized, we take

$\widetilde{W} = \frac{1}{\sqrt{6}} \begin{pmatrix} 1 & \sqrt{2} & 0 &1&\sqrt{2} \\ 0&\sqrt{2}&\sqrt{2}&0&-\sqrt{2}\\ \sqrt{3} & 0 &0 &-\sqrt{3} & 0 \\ 0& -1 & 2 & 0 & 1 \\ \sqrt{2} & -1 & 0 &\sqrt{2} & -1& \end{pmatrix} = \left(|w_1\rangle \, |w_2\rangle \, |w_3\rangle \, |w_4\rangle \, |w_5\rangle \right)$.

The projections $P_i$ corresponding to each POVM element $E_i$ are

$P_1 = |w_1\rangle\langle w_1|, \, P_2 = |w_2\rangle\langle w_2| + |w_3\rangle\langle w_3|, \, P_3 = |w_4\rangle\langle w_4| + |w_5\rangle\langle w_5|$.

To show that you get the same probabilities, observe that when the POVM $\{ E_i \}_{i}$ is measured on the state $|\psi \rangle = \begin{pmatrix} a \\ b \end{pmatrix}$, then the projections for its Naimark dilation are measured on the state $|\Psi\rangle = \begin{pmatrix} a \\ b \\ 0 \\ 0 \\ 0 \end{pmatrix}$.

 

On the security of quantum key distribution protocols

In an earlier post, we described the BB84 protocol, which allows two parties, say Alice and Bob, to share a secret bit string (called a key) using quantum states.

The protocol works because it uses a set of quantum states that cannot be fully distinguished from each other. Still, you may ask why would this be enough? If we run the protocol, how do we know that the keys the Alice and Bob get are indeed identical and private?

This means we must show that Alice's key is the same as Bob's key, and that any outside party, say Eve, cannot have too much knowledge about either key. That is exactly what we would need to do to prove the security of a quantum key distribution (QKD) protocol.

We say that a QKD protocol is secure if it produces a correct and secret key. A key is correct if Alice and Bob obtain precisely the same bit string. A key is secret if given a set of $N$ possible keys, the probability that Alice and Bob get any particular key is $\frac{1}{N}$. In other words, the key is uniformly distributed.

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.

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.

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$.

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}$.

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.