The subject of this thesis, quantum estimation theory, is inspired by recent developments, both practical and theoretical, in the new field of quantum information and computation. The main task of quantum estimation theory, the subject of this thesis, is that given many identical copies of an unknown quantum system one wants to "guess" or estimate what the system is. This is done by performing an "optimal" measurement and analyzing the data obtained from it. A quantum state is represented by a density matrix. In some cases one does not need to know the whole density matrix, sometimes a partial characterization is enough. Chapter 2 of this thesis is about optimally estimating the spectrum, i.e. the eigenvalues, of a density matrix. This is useful, for example, for estimating the entanglement of a bipartite pure state. The results of chapter 2 tell us that one can optimally estimate bipartite entanglement with LOCC measurements on one of the two parties. Unitary operations transform density matrices to density matrices. They are the gates of quantum information processing. Suppose one has one such unitary operation but one does not know what it does. In order to characterize it one needs to know how it transforms any input state. In order to know how a particular state is transformed, one can prepare that state, feed it to the unitary many times, and measure the output. One state is, of course, not enough. It turns out that the unitary can be completely characterized with a finite set of states, this is known as quantum process tomography. Unfortunately, in many cases it is difficult to have available in the lab all the input states needed to perform quantum process tomography. It is here where entanglement comes to the rescue. One pair of maximally entangled qubits, where one of them is used as input for the unitary gate and the other is left untouched, is sufficient. All the information about the unknown gate is contained in the joint output state. This is the problem treated in chapter 3. Now the output state needs to be measured. Again, one could measure the two qubits separately (LOCC) or jointly (collective measurement). Is there anything to gain by performing joint measurements? The answer is yes, optimal collective measurements are at least 3 times more accurate than any LOCC measurement. Chapter 4 treats the problem of estimating commuting unitary gates. There it is shown that this extra information makes it unnecessary to use an entangled input state and to use collective measurements at the output. In chapters 3 and 4 it is assumed that only one copy of the unitary gate is available. If, however, more than one copy (say N ) are available at the same time one could use an N-fold entangled state as input. If no entanglement is used, classical statistics tells us that the error of the estimation is proportional to 1/√N. In the literature, it has been shown that by using an entangled state in the input one can achieve an error proportional to 1/N. However, this has been shown only for qubit gates. In chapter 5 important steps are taken in the direction of showing the same thing for a general unitary gate, but this remains an open problem.
In this dissertation, we present several matrix-related problems and results motivated by quantum information theory. Some background material of quantum information science will be discussed in chapter 1, while chapter 7 gives a summary of results and concluding remarks. In chapter 2, we look at
2n×2n unitary matrices, which describe operations on a closed
n-qubit system. We define a set of simple quantum gates, called controlled single qubit gates, and their associated operational cost. We then present a recurrence scheme to decompose a general
2n×2n unitary matrix to the product of no more than
2n−1(2n−1) single qubit gates with small number of controls. In chapter 3, we address the problem of finding a specific element
Φ among a given set of quantum channels
S that will produce the optimal value of a scalar function
D(ρ1,Φ(ρ2)), on two fixed quantum states
ρ1 and
ρ2. Some of the functions we considered for
D(⋅,⋅) are the trace distance, quantum fidelity and quantum relative entropy. We discuss the optimal solution when
S is the set of unitary quantum channels, the set of mixed unitary channels, the set of unital quantum channels, and the set of all quantum channels. In chapter 4, we focus on the spectral properties of qubit-qudit bipartite states with a maximally mixed qudit subsystem. More specifically, given positive numbers
a1≥…≥a2n≥0, we want to determine if there exist a
2n×2n density matrix
ρ having eigenvalues
a1,…,a2n and satisfying $\tr_1(\rho)=\frac{1}{n}I_n$. This problem is a special case of the more general quantum marginal problem. We give the minimal necessary and sufficient conditions on
a1,…,a2n for
n≤6 and state some observations on general values of
n. In chapter 5, we discuss the numerical method of alternating projections and illustrate its usefulness in: (a) constructing a quantum channel, if it exists, such that
Φ(ρ(1))=σ(1),…,Φ(ρ(k))=σ(k) for given
ρ(1),…,ρ(k)∈Dn and
σ(1),…,σ(k)∈Dm, (b) constructing a multipartite state
ρ having a prescribed set of reduced states
ρ1,…,ρr on
r of its subsystems, (c) constructing a multipartite state
ρ having prescribed reduced states and additional properties such as having prescribed eigenvalues, prescribed rank or low von Neuman entropy; and (d) determining if a square matrix
A can be written as a product of two positive semidefinite contractions. In chapter 6, we examine the shape of the Minkowski product of convex subsets
K1 and
K2 of $\IC$ given by
K1K2={ab:a∈K1,b∈K2}, which has applications in the study of the product numerical range and quantum error-correction. In \citep{Karol}, it was conjectured that
K1K2 is star-shaped when
K1 and
K2 are convex. We give counterexamples to show that this conjecture does not hold in general but we show that the set
K1K2 is star-shaped if
K1 is a line segment or a circular disk.
The first half of this thesis deals with the problem of parameter estimation in a quantum system. In quantum parameter estimation theory, the quantum Fisher information is usually considered as the ultimate precision limit, beyond which no further improvement is possible due to the inherent stochasticity of quantum measurements. On the other hand, in this thesis we will show that a better precision is achievable than predicted by a quantum Fisher information analysis. This is true if some regularity assumptions about the underlying quantum parametric model are relaxed. In such situations, the quantum Fisher information does not completely capture the best possible performance of quantum measurements, and a different approach must be followed. In the second part of the thesis, we will focus on some applications of orthogonal array theory to two notable quantum information problems: the problem of multipartite entanglement classification and the quantum marginal problem. Introduced by Rao in 1947, orthogonal arrays have been usefully applied to different fields, from cryptography and coding theory to the statistical design of experiments, software testing and quality control. Remarkably, orthogonal arrays have also found application in quantum information and, in particular, in the study of quantum entanglement. We will employ tools from orthogonal array theory to study a toy version of the multipartite entanglement classification problem. Finally, we will show how orthogonal arrays can be employed to build constructive solutions to low-dimensional quantum marginal problems.
The aim of this thesis is to investigate quantum entanglement and quantum nonlocality of bipartite finite-dimensional systems (bipartite qudits). Entanglement is one of the most fascinating non-classical features of quantum theory, and besides its impact on our view of the world, it can be exploited for applications such as quantum cryptography and quantum computing. (...) Although entanglement and nonlocality are ordinarily regarded as one and the same, under close consideration this cannot be taken for granted. The reason for this is that entanglement is defined by the mathematical structure of a quantum state in a composite Hilbert space, whereas nonlocality signifies that the statistical behaviour of a system cannot be described by a local realistic theory. For the latter it is essential that the correlation probabilities of such theories obey so-called Bell inequalities, which are violated for certain quantum states. The main focus of this thesis is on the comparison of both properties with the objective of understanding their relation. (...) Because of the fact that the correlation probabilities in general depend on the measurement settings it is necessary to optimise these in order to reveal nonlocality. This problem is solved for a particular Bell inequality (CGMLP) by means of a self-developed numerical search algorithm. The method is then applied to density matrices of a subspace spanned by the projectors of maximally entangled two-qudit states. This set of states (...) serves to visualise and analyse the state space geometrically.
This thesis focuses on the intersection of mathematical and computational optimization and quantum information. Main contributions are open-source software code: A hybrid approach mixing "traditional" nonconvex and convex methods can make difficult problems more accessible. A demonstration of how to efficiently implement such an algorithm, avoiding interfacial bottlenecks, is provided, finding optimal protocols to establish entanglement through a lossy channel. The central software package developed addresses polynomial optimization problems. Many problems naturally involve only a polynomial objective and constraint polynomials. Such problems can automatically be cast into semidefinite programs that provide a hierarchy of outer approximations. The resulting problems are often so large and scale so unfavorably with respect to the variable number and degree involved that the boundary of the doable is reached quickly. However, technical progress both in hardware and algorithms has pushed this boundary - but software frameworks for polynomial optimization have not followed in the same manner, often now making them the bottleneck that before was the solver. The package PolynomialOptimization.jl developed during this thesis aims to fill the gap and provide a very resource-efficient intermediate layer together with a wide number of algorithms to reduce the problem size, and naturally supporting complex numbers and semidefinite constraints ubiquitous in quantum information problems. Its application on an entanglement distribution problem is demonstrated, showing that even relaxations with semidefinite matrices of three- and four-digit size can be solved conveniently. Finally, a new way to calculate interior-point barriers for the cone of sums-of-squares matrices in a nearly time-optimal way is developed, whose efficient implementation has the potential of further reducing resource consumption.
Optimization is a fundamental area in mathematics and computer science, with many real-world applications. In this thesis we study the efficiency with which we can solve certain optimization problems from two different perspectives. Firstly, we study it from the perspective of matrix factorization ranks, which comes with connections to quantum information theory. Secondly, we study it from the perspective of quantum computing. This thesis is accordingly divided into two parts, where we take these perspectives. In the first part of this thesis we study several matrix factorization ranks and their connections to quantum information theory. In Chapter 5, we first give a unified approach to lower bounding matrix factorization ranks, using polynomial optimization techniques. In Chapter 6, we exploit the connection between one particular factorization rank, the completely positive semidefinite rank, and quantum correlations to provide an explicit family of matrices with a large completely positive semidefinite factorization rank. In Chapter 8, we use the same connection to study quantum versions of classical graph parameters from the perspective of polynomial optimization (albeit in noncommutative variables). In Chapter 7 we propose and study a new measure for the amount of entanglement needed to realize quantum correlations. We can approximate this new measure using our approach to matrix factorization ranks, i.e., through polynomial optimization in noncommutative variables. In the second part of this thesis we turn our attention to the question: Can we solve optimization problems faster on a quantum computer? First, in Chapter 10, we look at the problem of evaluating a Boolean function. We give a new semidefinite programming characterization of the minimum number of quantum queries to the input that are needed to determine the corresponding function value. In Chapter 11 we revisit the semidefinite programming problem that plays a crucial role in the rest of the thesis; we provide a quantum algorithm for solving semidefinite programs. Finally, in Chapter 12, we study the general problem of solving convex optimization problems in the oracle model. We provide both upper and lower bounds on the efficiency of various reductions in the quantum setting. In particular, we show that quantum computers are more efficient than classical computers for the task of answering separation queries when access to the convex problem is given through membership queries.