This thesis investigates three distinct facets of the theory of quantum information. The first two, quantum state estimation and quantum process estimation, are closely related and deal with the question of how to estimate the classical parameters in a quantum mechanical model. The third attempts to bring quantum theory as close as possible to classical theory through the formalism of quasi-probability. \n \nBuilding a large scale quantum information processor is a significant challenge. First, we require an accurate characterization of the dynamics experienced by the device to allow for the application of error correcting codes and other tools for implementing useful quantum algorithms. The necessary scaling of computational resources needed to characterize a quantum system as a function of the number of subsystems is by now a well studied problem (the scaling is generally exponential). However, irrespective of the computational resources necessary to just write-down a classical description of a quantum state, we can ask about the experimental resources necessary to obtain data (measurement complexity) and the computational resources necessary to generate such a characterization (estimation complexity). These problems are studied here and approached from two directions. \n \nThe first problem we address is that of quantum state estimation. We apply high-level decision theoretic principles (applied in classical problems such as, for example, universal data compression) to the estimation of a qubit state. We prove that quantum states are more difficult to estimate than their classical counterparts by finding optimal estimation strategies. These strategies, requiring the solution to a difficult optimization problem, are difficult to implement in practise. Fortunately, we find estimation algorithms which come close to optimal but require far fewer resources to compute. Finally, we provide a classical analog of this quantum mechanical problem which reproduces, and gives intuitive explanations for, many of its features, such as why adaptive tomography can quadratically reduce its difficulty. \n \nThe second method for practical characterization of quantum devices takes is applied to the problem of quantum process estimation. This differs from the above analysis in two ways: (1) we apply strong restrictions on knowledge of various estimation and control parameters (the former making the problem easier, the latter making it harder); and (2) we consider the problem of designing future experiments based on the outcomes of past experiments. We show in test cases that adaptive protocols can exponentially outperform their off-line counterparts. Moreover, we adapt machine learning algorithms to the problem which bring these experimental design methodologies to realm of experimental feasibility. \n \nIn the final chapter we move away from estimation problems to show formally that a classical representation of quantum theory is not tenable. This intuitive conclusion is formally borne out through the connection to quasi-probability -- where it is equivalent to the necessity of negative probability in all such representations of quantum theory. In particular, we generalize previous no-go theorems to arbitrary classical representations of quantum systems of arbitrary dimension. We also discuss recent progress in the program to identify quantum resources for subtheories of quantum theory and operational restrictions motivated by quantum computation.
This thesis investigates three distinct facets of the theory of quantum information. The first two, quantum state estimation and quantum process estimation, are closely related and deal with the question of how to estimate the classical parameters in a quantum mechanical model. The third attempts to bring quantum theory as close as possible to classical theory through the formalism of quasi-probability. \n \nBuilding a large scale quantum information processor is a significant challenge. First, we require an accurate characterization of the dynamics experienced by the device to allow for the application of error correcting codes and other tools for implementing useful quantum algorithms. The necessary scaling of computational resources needed to characterize a quantum system as a function of the number of subsystems is by now a well studied problem (the scaling is generally exponential). However, irrespective of the computational resources necessary to just write-down a classical description of a quantum state, we can ask about the experimental resources necessary to obtain data (measurement complexity) and the computational resources necessary to generate such a characterization (estimation complexity). These problems are studied here and approached from two directions. \n \nThe first problem we address is that of quantum state estimation. We apply high-level decision theoretic principles (applied in classical problems such as, for example, universal data compression) to the estimation of a qubit state. We prove that quantum states are more difficult to estimate than their classical counterparts by finding optimal estimation strategies. These strategies, requiring the solution to a difficult optimization problem, are difficult to implement in practise. Fortunately, we find estimation algorithms which come close to optimal but require far fewer resources to compute. Finally, we provide a classical analog of this quantum mechanical problem which reproduces, and gives intuitive explanations for, many of its features, such as why adaptive tomography can quadratically reduce its difficulty. \n \nThe second method for practical characterization of quantum devices takes is applied to the problem of quantum process estimation. This differs from the above analysis in two ways: (1) we apply strong restrictions on knowledge of various estimation and control parameters (the former making the problem easier, the latter making it harder); and (2) we consider the problem of designing future experiments based on the outcomes of past experiments. We show in test cases that adaptive protocols can exponentially outperform their off-line counterparts. Moreover, we adapt machine learning algorithms to the problem which bring these experimental design methodologies to realm of experimental feasibility. \n \nIn the final chapter we move away from estimation problems to show formally that a classical representation of quantum theory is not tenable. This intuitive conclusion is formally borne out through the connection to quasi-probability -- where it is equivalent to the necessity of negative probability in all such representations of quantum theory. In particular, we generalize previous no-go theorems to arbitrary classical representations of quantum systems of arbitrary dimension. We also discuss recent progress in the program to identify quantum resources for subtheories of quantum theory and operational restrictions motivated by quantum computation.
Quantum computing exists at the intersection of mathematics, physics, chemistry, and engineering; the main goal of quantum computing is the creation of devices and algorithms which use the properties of quantum mechanics to store, manipulate and measure information. There exist many families of algorithms, which, using non-classical logical operations, can outperform traditional, classical algorithms in terms of memory and processing requirements. In addition, quantum computing devices are fundamentally smaller than classical processors and memory elements; since the physical models governing their performance are applicable on all scales, as opposed to classical logic elements, whose underlying principles rely on the macroscopic nature of the device in question. \n \nQuantum algorithms, for the most part, are predicated on a theory of resources. It is often assumed that quantum computers can be placed in a precise fiducial state prior to computation, and that logical operations are perfect, inducing no error on the system which they affect. These assumptions greatly simplify algorithmic design, but are fundamentally unrealistic. In order to justify their use, it is necessary to develop a framework for using a large number of imperfect devices to simulate the action of a perfect device, with some acceptable probability of failure. This is the study of fault-tolerant quantum computing. In order to pursue this study effectively, it is necessary to understand the fundamental nature of generic quantum states and operations, as well as the means by which one can correct quantum errors. Additionally, it is important to attempt to minimize the use of computational resources in achieving error reduction and fault-tolerant computing. \n \nThis thesis is concerned with three projects related to the use of error-prone quantum systems to transmit and manipulate information. The first of these is concerned with the use of imperfectly-prepared states in error-correction routines. Using optimal quantum error correction, we are able to deduce a method of partially protecting encoded quantum information against preparation errors prior to encoding, using no additional qubits. The second of these projects details the search for entangled states which can be used to transmit classical information over quantum channels at a rate superior to classical states. The third of these projects concerns the transcoding of data from one quantum code into another using few ancillary resources. The descriptions of these projects are preceded by a brief introduction to representations of quantum states and channels, for completeness. \n \nThree techniques of general interest are presented in appendices. The first is an introduction to, and a minor advance in the development of optimal error correction codes. The second is a more efficient means of calculating the action of a quantum channel on a given state, given that the channel acts non-trivially only on a subsystem, rather than the entire system. Finally, we include documentation on a software package developed to aid the search for quantum transcoding operations.
Quantum states and measurements are two central physical objects in the theory of quantum mechanics. The preparation, control and measurement of quantum states lies at the heart of modern quantum information processing protocols ranging from secure communication to quantum computation and precision sensing. And yet, the reliable operation of these advanced protocols ultimately rests on a far more essential prerequisite - our ability to calibrate, certify and benchmark the quantum states we prepare and the quantum measurements we perform. Quantum information theory provides a natural framework for these tasks, meaningfully connecting the resources we expend for characterisation with the accuracy and precision we can expect in return. While decades of advances in quantum information have refined our understanding of quantum characterisation and sharpened our practical ability to calibrate with enhanced precision, important questions about the fundamental limits of quantum characterisation remain unanswered. Although incorporating entanglement at the measurement stage is known to enhance the estimation of unknown quantum states, the extent of this improvement remains poorly understood. This leaves open a fundamental question on the utility of complex entangling measurement strategies, impeding progress towards bridging the significant gap between practically achievable precision and the ultimate theoretical quantum limit. Complementary to quantum state estimation, which is relatively well-established in theory and practice, the characterisation of quantum measurements lacks a rigorous information-theoretic foundation, leading to a dearth of principled benchmarks and provably optimal strategies despite growing experimental interest. This thesis develops and applies information-theoretic tools to answer questions in quantum characterisation, with an eye to enabling practical improvements beyond current techniques in the field. First, we introduce a computable measure of entanglement enhancement for quantum state estimation and study its variation across general multi-parameter estimation problems for higher-dimensional quantum states. We show that the entanglement enhancement is maximised for full qudit state tomography but grows only linearly with system dimension even when allowing an asymptotically large number of entangling operations. Our proposed tight upper bound to entanglement enhancement therefore constitutes a strong limitation on the utility of such entangling measurements. Next, we formulate the dual problem of quantum detector estimation, developing a comprehensive framework for maximally precise calibration centred around a newly introduced quantity - the detector quantum Fisher information. This information-theoretic measure stipulates the ultimate precision attainable for measurement calibration and identifies the optimal input states that achieve this precision. Further, our framework enables the first provably optimal detector estimation experiment and reveals the scope for entanglement-based enhancements, thereby placing measurement characterisation on equal footing with state characterisation. Considered together, these results suggest two contrasting conclusions about quantum characterisation. On the one hand, they show that for quantum state estimation, increasingly powerful entangling measurements offer only diminishing returns at the ultimate precision limit. On the other hand, they highlight practical quantum advantages available for detector estimation by providing a framework that can improve calibration performance and guide future experimental design. More broadly, these results complete and advance the triad of state, process, and detector characterisation, positioning quantum information measures as not merely abstract bounds, but practical guides for deciding when complex quantum resources are genuinely worth deploying and where near-term quantum advantages are most likely to be realised.
Quantum mechanics is basically a mathematical recipe on how to construct physical models. Historically its origin and main domain of application has been in the microscopic regime, although it strictly seen constitutes a general mathematical framework not limited to this regime. Since it is a statistical theory, the meaning and role of probabilities in it need to be defined and understood in order to gain an understanding of the predictions and validity of quantum mechanics. The interpretational problems of quantum mechanics are also connected with the interpretation of the concept of probability. In this thesis the use of probability theory as extended logic, in particular in the way it was presented by E. T. Jaynes, will be central. With this interpretation of probabilities they become a subjective notion, always dependent on one's state of knowledge or the context in which they are assigned, which has consequences on how things are to be viewed, understood and tackled in quantum mechanics. For instance, the statistical operator or density operator, is usually defined in terms of probabilities and therefore also needs to be updated when the probabilities are updated by acquisition of additional data. Furthermore, it is a context dependent notion, meaning, e.g., that two observers will in general assign different statistical operators to the same phenomenon, which is demonstrated in the papers of the thesis. It is also presented an alternative and conceptually clear approach to the problematic notion of "probabilities of probabilities", which is related to such things as probability distributions on statistical operators. In connection to this, we consider concrete numerical applications of Bayesian quantum state assignment methods to a three-level quantum system, where prior knowledge and various kinds of measurement data are encoded into a statistical operator, which can then be used for deriving probabilities of other measurements. The thesis also offers examples of an alternative quantum state assignment technique, using maximum entropy methods, which in some cases are compared with the Bayesian quantum state assignment methods. Finally, the interesting and important problem whether the statistical operator, or more generally quantum mechanics, gives a complete description of "objective physical reality" is considered. A related concern is here the possibility of finding a "local hidden-variable theory" underlying the quantum mechanical description. There have been attempts to prove that such a theory cannot be constructed, where the most well-known impossibility proof claiming to show this was given by J. S. Bell. In connection to this, the thesis presents an idea for an interpretation or alternative approach to quantum mechanics based on the concept of space-time.
Every day we need to make many decisions: what we should have for dinner, what to vote for, or whether to kiss that special person for the first time. There are also many decisions that need to be made at a larger scale, for example, groups, governments, and corporations have to make decisions in order to use their resources wisely. Every decision asks us to consider many possibilities and to try to get the optimal outcome (or more often than not, to simply avoid disaster). Making these decisions is further complicated by the constraints that are put on us. Even though people have become quite good at making decisions, the increasing complexity of the world around us means that `going with our guts' is often an ill-advised optimization strategy. The field of mathematics allows us to formulate an abstract version of some of the more complex problems we encounter, and allows us to quantify what the objectives and constraints are. For some problems mathematics even gives us a simple closed-form solution, e.g. many of us have learned in school how find the extreme points on a parabola. However, for many problems there is no such simple closed-form solution, the best we can do is to use a method, or algorithm, to construct a solution. This puts us in the realm of computer science. Computer science considers how to solve problems systematically, and more importantly how many steps the decision-making process has to take. Most optimization problems can be solved by simply listing all possible combinations of decisions and then searching for the best option, but as the number of decisions increases, so does the number of combinations. In fact, for many situations the number of possible combinations increases exponentially, making the process of writing down all the options impractical. Instead we often look for a smarter, more efficient algorithm, one that scales better with the problem size. It is not always easy (or even possible) to find an efficient algorithm. Consider the problem of finding the lowest place in the Swiss Alps. We may walk down into what seems the deepest valley, only to learn later that a farmer three valleys over has dug a really deep well. One of the problems in such a scenario is that we may find a local minimum, but due to a lack of structure in the problem we have no clear way of finding a global minimum. Some problems do have more structure, an important class of these is the class of convex optimization problems. Convex optimization problems have the useful property that local minima are also global minima. For our example about the Alps this means that, as long as we keep going down, we will always reach the lowest point. However, as anyone who ever went snowboarding can tell you, how you go down matters a lot for how fast you will get there. Apart from considering the structure of the problem we are trying to solve we should also consider what steps we can take to solve it. We may want to use pen and paper, use our laptop, or use a supercomputer, all of which function differently. However, these methods are not inherently different, with enough time we could perform the same computation as a supercomputer with nothing more than a pen and a piece of paper. Although this would be significantly slower, the scaling with the problem size would stay the same since the basic steps we can use are the same, only slower. What basic steps we may perform is ultimately dictated by the laws of physics: we can only change the state of our piece of paper, or our computer, in ways that are allowed by physics. Specifically, our piece of paper and our computers both follow the laws of classical physics, the physics that we see around us every day. During the 20th century our understanding of physics has changed and we now know that classical physics does not give a full description of the natural world. One of the places where classical physics breaks down is at the scale of atoms and elementary particles, at this small scale the universe is governed by the laws of quantum physics. Quantum physics predicts behavior that is not possible in classical physics. Particles might be in a superposition of many different classical states, only becoming a specific one of those states at random when interacting with our classical world via a measurement. Miraculously, and contrary to classical randomness, this quantum randomness does not stem from our inherent lack of knowledge about the particle, the different parts of the superposition are all present until we measure and can interfere with each other. A natural question to ask is whether these phenomena can be used to our benefit when performing computations. A computer that works according to the rules of quantum physics is called a Quantum computer, such devices have a wider range of basic operations that they can perform than classical computers do. This thesis asks the following central question can quantum computers solve convex optimization problems faster? In order to answer this question we consider a few different types of problem that we may encounter in convex optimization. If we have some black-box procedure to evaluate how good a proposed solution to a convex optimization problem is, for example a way of estimating the height of a point in the Alps or a method of estimating our profits given a business strategy, then a classical computer would have to try a lot of small changes in order to find the change that improves our objective the most. However, we show that a quantum computer can find the optimal direction for improvement exponentially faster. We then consider specific categories of convex optimization problems, mainly linear programming and semidefinite programming. These problem categories include many natural problems and have been widely used both for theoretical and practical purposes. For example, linear programming can be used for finding the optimal strategies of zero-sum games, coming up with a diet plan, or planning resources. Semidefinite programming is a generalization of linear programming and can additionally be useful for designing optimal experiments, approximately solving hard problems, or optimize processes involving quantum mechanics. Our quantum algorithms for these problems use a natural connection between quantum physics and semidefinite programming: the solutions to a semidefinite programming problem correspond to the states of a quantum system. We show that quantum computers can solve semidefinite programming problems and linear programming problems quadratically faster than a classical computer can. In fact, our algorithms take less time to solve the problem than that it would take to read through the whole input. We also take a more negative view and discuss the limitations of quantum computers. We show that, even though quantum computers can find the optimal direction of improvement exponentially faster, there is no general exponential speedup for finding the optimal value. We also show that in many ways our methods for solving linear and semidefinite programming problems are optimal: faster methods would not be able to read enough of the input to still get a good solution. To conclude, we showed that in a few different settings the answer to our central question is yes. The results in this dissertation show that quantum computers can solve some convex optimization problems faster, but there are also limits to this. There are still many open questions regarding convex optimization on quantum computers and we regard this topic as an important direction of future research.
In this thesis I present a short review of ideas in quantum information theory. The first chapter contains introductory material, sketching the central ideas of probability and information theory. Quantum mechanics is presented at the level of advanced undergraduate knowledge, together with some useful tools for quantum mechanics of open systems. In the second chapter I outline how classical information is represented in quantum systems and what this means for agents trying to extract information from these systems. The final chapter presents a new resource: quantum information. This resource has some bewildering applications which have been discovered in the last ten years, and continually presents us with unexpected insights into quantum theory and the universe. The treatment is pedagogical and suitable for beginning graduates in the field.
The rapid advance of quantum information technology requires precise control and manipulation of quantum systems and of their properties; in particular, it is essential to certify that quantum processors truly work quantum mechanically, in order to validate experiments and their results. The problem of certification of quantum states and devices is a demanding one, thus many attempts have been put forward to find ways of efficiently test their basic functionalities, such as their entanglement properties. The main problems addressed in this thesis concern indeed finding optimal strategies for the estimation and characterization of quantum states and channels, with a special focus on entanglement correlations. In our first work we considered the certification of entanglement across a given partition of a multi-qubit system, when only partial information about the corresponding quantum state is available; we tackled the problem of finding the best measurement strategy introducing the statistics of lengths of measurement sequences, choosing multi-qubit Pauli-measurements as observables. Using a sample of random unknown states, we were able to identify the (on average) shortest, i.e. most efficient, measurement sequence to detect entanglement. The investigation was carried out with an algorithm based on the truncated moment sequences (tms) problem, which provides necessary and sufficient conditions for entanglement or separability of a quantum state of a finite dimensional system. This study results in a very efficient strategy especially for symmetric states, for which only a tiny fraction (10−6) of randomly chosen entangled states are undetected for systems with 6 qubits or more. We continued in our second work with the problem of separability of quantum channels to answer the question whether a given quantum device is able to create entanglement or not. The Choi matrix representation, provided by the Choi–Jamiołkowski isomorphism, casts the problem in terms of systems and ancillas, giving different classes of separability depending on the cut considered between them. Once again, the tms framework turned out to be well suited for this study, giving a unifying approach for the different separability problems; a solution is found in terms of the tms associated to the coordinates of the Choi state, in a fixed basis, and semidefinite programming is used to get a separability certificate. We explored examples of families of 2-qubit and single-qutrit channels, for which our algorithm can give an answer in cases where other criteria remain inconclusive. In a further work we shifted our attention to a different direction, highlighting a connection between the fields of quantum information, Bose-Einstein condensation (BEC) and analogue gravity, thus showing the relevance of quantum information notions in a broader context. We studied the entanglement properties of a BEC analogue of a black hole, which is described by a three-mode Gaussian state; we investigated bipartite and tripartite entanglement measures based on the covariance matrix description, both at zero and finite temperature, providing the best experimental configuration for entanglement detection. In a final stage of this thesis, we started looking at different measurement strategies for testing quantum devices whose functionality can be described by a single parameter; we used a Bayesian approach to estimate this parameter, exploiting the information collected through measurements to update a conditional probability distribution, without the need of estimating expected values of observables. The problem of finding the optimal experimental design can be in this case translated in the optimization of a utility function, which usually guides the update process adaptively at each step; we tried to outperform this approach looking ahead not only at the next step, but at a few ones, in order to obtain an answer of correct or wrong functioning as soon as possible. Moreover, we chose the input state for the quantum channel considered minimizing the error probability given by the Chernoff distance between the outputs of an ideal and a faulty channel; finally, we considered two different final decision criteria and compared their efficiency.