Quantum information theory forms a bridge between the foundations of quantum mechanics and its promising practical potentials.The extensive theoretical research has been conducted during the last decades and the applications such as quantum key distribution and quantum computing promise to provide real technological breakthroughs.Many experimental groups worldwide are working on the practical implementation of the concepts from the quantum information theory.In the recent years a lot of attention has been paid to the certification of truly quantum behavior of some device, claimed to be quantum.This certification can be done by using some established interactive proof in which classical user just by commanding to a quantum device (prover) can make himself sure that the device works as advertised and moreover can actually use it for some particular task.When it comes to quantum computing one has to be sure that a machine uses quantum mechanics for the computational process.Two interesting interactive proofs are developed so far.One of them uses specific computation model, Measurement-based quantum computing, which is performed on a class of highly entangled states, graph states.The difficulty with the implementation of this interactive proof is a big number of provers required for the process.In this thesis we present some initial results of the attempts to construct interactive proof that would use smaller number of provers.Difficulties of the two-prover interactive proof and guidelines for the future research are presented as well as the new three-prover interactive proof for quantum device performing computation by doing single qubit unitary operations.After finishing my master program I have to thank to some people for having their part in making it as good as it has been.On the first part I would like to thank to my master thesis supervisors Antonio Acin and Matty Hoban.Thanks to prof.Acin for letting me do my thesis in his group in ICFO, for good will and useful discussions on the topic.There are not enough words to express gratitude to Matty Hoban.During these last months I had this great opportunity to learn so much from him.Thanks for this exciting project, for the enthusiasm, invested time, the patience, everything.I had a great reference for the future research.I am also grateful to the whole Quantum information theory group in ICFO, for the pleasant and very motivating atmosphere they have created.Particularly I would like to thank to my office-mate Paul Skrzypczyk for answering my questions "out of nowhere" and help with SDP and to Ariel Bendersky for the help with the last part of
Quantum information theory forms a bridge between the foundations of quantum mechanics and its promising practical potentials.The extensive theoretical research has been conducted during the last decades and the applications such as quantum key distribution and quantum computing promise to provide real technological breakthroughs.Many experimental groups worldwide are working on the practical implementation of the concepts from the quantum information theory.In the recent years a lot of attention has been paid to the certification of truly quantum behavior of some device, claimed to be quantum.This certification can be done by using some established interactive proof in which classical user just by commanding to a quantum device (prover) can make himself sure that the device works as advertised and moreover can actually use it for some particular task.When it comes to quantum computing one has to be sure that a machine uses quantum mechanics for the computational process.Two interesting interactive proofs are developed so far.One of them uses specific computation model, Measurement-based quantum computing, which is performed on a class of highly entangled states, graph states.The difficulty with the implementation of this interactive proof is a big number of provers required for the process.In this thesis we present some initial results of the attempts to construct interactive proof that would use smaller number of provers.Difficulties of the two-prover interactive proof and guidelines for the future research are presented as well as the new three-prover interactive proof for quantum device performing computation by doing single qubit unitary operations.After finishing my master program I have to thank to some people for having their part in making it as good as it has been.On the first part I would like to thank to my master thesis supervisors Antonio Acin and Matty Hoban.Thanks to prof.Acin for letting me do my thesis in his group in ICFO, for good will and useful discussions on the topic.There are not enough words to express gratitude to Matty Hoban.During these last months I had this great opportunity to learn so much from him.Thanks for this exciting project, for the enthusiasm, invested time, the patience, everything.I had a great reference for the future research.I am also grateful to the whole Quantum information theory group in ICFO, for the pleasant and very motivating atmosphere they have created.Particularly I would like to thank to my office-mate Paul Skrzypczyk for answering my questions "out of nowhere" and help with SDP and to Ariel Bendersky for the help with the last part of
The field of quantum computing investigates the extent to which one can design a quantum system that outperforms all known classical hardware at a certain task.But, to what extent can a human being, capable only (perhaps) of classical computation and of observing classical bit-string messages, verify that a quantum device in their possession is performing the task that they wish?This is a fundamental question about the nature of quantum mechanics, and the extent to which humans can harness it in a trustworthy manner.It is also a natural and important consideration when quantum devices may be used to perform sensitive cryptographic tasks which have no known efficient classical witness of correctness (Quantum Key Distribution, and Randomness Expansion are two examples of such tasks).It is remarkable that any quantum behavior at all can be tested by a verifier under such a constraint, without trusting any other quantum mechanical device in the process!But, intriguingly, when there are two or more quantum provers available in an interactive proof, there exist protocols to verify many interesting and useful quantum tasks in this setting.This thesis investigates multi-prover interactive proofs for verifying quantum behavior, and focuses on the stringent testing scenario in which the verifier in the interactive proof is completely classical as described above.It resolves the question of the maximum attainable expansion rate of a randomness expansion protocol by providing an adaptive randomness expansion protocol that achieves an arbitrary, or infinite rate of randomness expansion [29].Secondly it presents a new rigidity result for the parallel repeated magic square game [24], which provides some improvements on previous rigidity results that play a pivotal role in existing interactive proofs for entangled provers, QKD, and randomness expansion results.This new rigidity result may be useful for improving such interactive proofs in the future.The second half of this thesis investigates the problem of bounding the role of quantum The further I go the more I value what my parents' example has taught me, not about science, but about life.I love you Mom and Dad.My deep gratitude goes to my advisor, Peter Shor, for guidance in research throughout graduate school, and for supporting my own research endeavors.During a PhD a student's mind is full of many different considerations, both scientific and logistical.Peter's advice is an invaluable way to refocus on the heart of the research problem at hand and, with stunning consistency, to learn something amazing and new.During my PhD I have had the privilege of collaborating with many talented researchers and good friends.What would the exploration process be without people share ideas with, and fellow researchers with which to share the thrill of discovery?Many thanks to my collaborators (listed here in no particular order)!I can only hope to continue to have such great collaborations again in the future:
[eng] This thesis can be classified into the research field of quantum algorithms. A typical paper in this field usually focuses on what kind of things we can do with a quantum computer, whether they are useful or advantageous compared to classical computers, and how we can do it more efficiently. Since the ideal fault-tolerant large-scale quantum computer will not be available soon, many papers focus on noisy intermediate-scale quantum (NISQ) devices, how to characterize them through various benchmarking protocols, and how to make them useful through error mitigation or variational algorithms. Most probably, anyone who ends up opening this thesis is already an expert in certain topics, but they can still find some “out of the box" elements in one chapter or another. The results presented in the thesis might not be directly useful, but hopefully, these elements can provide insights and inspiration. The main body of this thesis is organized into six independent chapters. Each chapter is complete and self-consistent. All these chapters share a similarity: They provide some mathematical ideas of quantum computing in one aspect or another. Since part of the research is conducted in collaboration, the pronoun “we" is used throughout the work. In the first chapter, we focus on actions that transform quantum states into quantum states. We begin with a more theoretical approach. These actions naturally process a group structure. And we ask, under what conditions is this group finite? Given an arbitrary finite group, how can we construct these actions? How can these actions be useful to quantum computing? The set of these actions is named "Quantum representation of finite group," and answers to these questions are provided in the main text. Then, in the second chapter, we switch to a more practical scenario. The inspiration came from a problem that appeared in post-quantum cryptography, the dihedral coset problem, which uses quantum algorithms to recover a secret of the group hidden in quantum states. We simplified this problem and designed an interactive protocol for verifying the computational capacity of a quantum device. Holding a small quantum computer, the verifier prepares quantum state samples that encode a secret and sends them one by one to the prover via a one-way quantum channel. The prover then uses his quantum device to recover the secret with a certain probability. The device’s capacity is then reflected in the accuracy of the solution. This interactive protocol can be used locally on a single device as a benchmarking protocol. In the third chapter, we explore quantum entanglement. We present a new method for visualizing entanglement during a quantum evolution, such as the execution of a quantum algorithm. We name this method "Entanglement trajectory" and show that it can provide a "fingerprint" for each quantum process. We determine the boundaries of these trajectories with Random Matrix Theory and use different examples and entanglement measurements to show that this trajectory has an intrinsic quantum meaning and provides more information about the system. In the fourth chapter, we elaborate on the entanglement presented in a succession of numbers. First, we give a numerical and analytical description of the average entropy of succession, which can provide a standard for studying any successions. Then, we simulate the example of k-almost primes and its unions for different system sizes and explore their particular feature. In the fifth chapter, we will show three different methods of using a quantum annealer to solve Multivariate Quadratic (MQ) problems. In the sixth chapter, we present a data encoder in the fixed Hamming weight subspace, which is parameter-optimal and can be extended to a sparse and binary data encoder. We will give a small summary for each chapter. At the end of this thesis, we will provide an overall conclusion for our readers as “take-home messages".
During the last decade, scientists working in quantum theory have been engaging in promising new fields such as quantum computation and quantum information processing, and have also been reflecting on the possibilities of nonlinear behavior on the quantum level. These are challenging undertakings because (1) they will result in new solutions to important technical and practical problems that were unsolvable by the classical approaches (for example, quantum computers can calculate problems that are intractable if one uses classical computers); and (2) they open up new 'hard' problems of a fundamental nature that touch the foundation of quantum theory itself (for example, the contradiction between locality and nonlinearity and the interpretation of quantum computing as a universal process). In this book, one can distinguish two main streams of research to approach the just-mentioned problem field: (1) a theoretical structural part, which concentrates on the elaboration of a nonlinear quantum mechanics and the fundamentals of quantum computation; and (2) a theoretical experimental part, which focuses on the theoretical aspects of applications that arise from new technology and novel research perspectives such as quantum optics and quantum cryptography. Particular attention is also paid to the measurement problem, the classical limit and alternative interpretations (such as the hidden measurement approach).
Quantum computers promise to offer a considerable speed-up in solving certain problems, compared to the best classical algorithms. In many instances, the gap between quantum and classical running times is conjectured to be exponential. While this is great news for those applications where quantum computers would provide such an advantage, it also raises a significant challenge: how can classical computers verify the correctness of quantum computations? In attempting to answer this question, a number of protocols have been developed in which a classical client (referred to as verifier) can interact with one or more quantum servers (referred to as provers) in order to certify the correctness of a quantum computation performed by the server(s). These protocols are of one of two types: either there are multiple non-communicating provers, sharing entanglement, and the verifier is completely classical; or, there is a single prover and the classical verifier has a device for preparing or measuring quantum states. The latter type of protocols are, arguably, more relevant to near term quantum computers, since having multiple quantum computers that share a large amount of entanglement is, from a technological standpoint, extremely challenging. Before the realisation of practical single-prover protocols, a number of challenges need to be addressed: how robust are these protocols to noise on the verifier's device? Can the protocols be made fault-tolerant without significantly increasing the requirements of the verifier? How do we know that the verifier's device is operating correctly? Could this device be eliminated completely, thus having a protocol with a fully classical verifier and a single quantum prover? Our work attempts to provide answers to these questions. First, we consider a single-prover verification protocol developed by Fitzsimons and Kashefi and show that this protocol is indeed robust with respect to deviations on the quantum state prepared by the verifier. We show that this is true even if those deviations are the result of a correlation with the prover's system. We then use this result to give a verification protocol which is device- independent. The protocol consists of a verifier with a measurement device and a single prover. Device-independence means that the verifier need not trust the measurement device (nor the prover) which can be assumed to be fully malicious (though not communicating with the prover). A key element in realising this protocol is a robust technique of Reichardt, Unger and Vazirani for testing, using non-local correlations, that two untrusted devices share a large number of entangled states. This technique is referred to as rigidity of non-local correlations. Our second result is to prove a rigidity result for a type of quantum correlations known as steering correlations. To do this, we first show that steering correlations can be used in order to certify maximally entangled states, in a setting in which each test is independent of the previous one. We also show that the fidelity with which we characterise the state, in this specific test, is optimal. We then improve the previous result by removing the independence assumption. This then leads to our desired rigidity result. We make use of it, in a similar fashion to the device-independent case, in order to give a verification protocol that is one-sided device-independent. The importance of this application is to show how different trust assumptions affect the efficiency of the protocol. Next, we describe a protocol for fault-tolerantly verifying quantum computations, with minimal "quantum requirements" for the verifier. Specifically, the verifier only requires a device for measuring single-qubit states. Both this device, and the prover's operations are assumed to be prone to errors. We show that under standard assumptions about the error model, it is possible to achieve verification of quantum computation using fault-tolerant principles. As a proof of principle, and to better illustrate the inner workings of the protocol, we describe a toy implementation of the protocol in a quantum simulator, and present the results we obtained, when running it for a small computation. Finally, we explore the possibility of having a verification protocol, with a classical verifier and a single prover, such that the prover is blind with respect to the verifier's computation. We give evidence that this is not possible. In fact, our result is only concerned with blind quantum computation with a classical client, and uses complexity theoretic results to argue why it is improbable for such a protocol to exist. We then use these complexity theoretic techniques to show that a client, with the ability to prepare and send quantum states to a quantum server, would not be able to delegate arbitrary NP problems to that server. In other words, even a client with quantum capabilities cannot exploit those capabilities to delegate the computation of NP problems, while keeping the input, to that computation, private. This is again true, provided certain complexity theoretic conjectures are true.
In this thesis, we investigated a theory of quantum error correction (QEC) in nearterm quantum devices.Due to the recent development of quantum technologies, QEC with several tens of qubits is expected to be demonstrated in the next few years.On the other hand, since such a large quantum system cannot be tracked with current classical computers, several problems about practical QEC experiments emerge as quantum devices are scaled up.We provided solutions to the following two essential problems among them.First, we extended a simulatability of quantum error correcting code under coherent noise using matchgate circuits.This extension enables an efficient and accurate evaluation of an effective physical error probability suppressed with QEC under practical errors.Since this probability should be known before we design quantum devices for QEC, this result provides vital information for experiments.Second, we proposed a general framework to use machine learning as a part of decoding algorithm in QEC.QEC requires a fast and high-performance classical decoder for its implementation.Using machine learning for decoding is one of the most promising solutions to this.However, what part of a decoding algorithm should be delegated to machine learning in order to achieve the near-optimal performance has not been discussed.We constructed a general framework to discuss it, and showed fundamental relations between the decoding problem and the task of machine learning.Furthermore, we proposed a criterion for achieving high performance, and showed specific formulation of tasks of machine learning.Then, we confirmed that the performance of the proposed machine-learning-based decoder is superior to the known decoders in various situations.This thesis is written based on various supports and advice from many people.I would like to thank Prof. Masato Koashi, who has totally supervised my research during undergraduate and graduate school.His thoughtful advice and questions are helpful for me to obtain clear viewpoint of my research.I am frequently impressed by his outstanding perspective of quantum information science, and the discussions with him strongly encourage my interest in physics.I also would like to thank Assoc.Prof. Keisuke Fujii, who supervised both of the two main results of the thesis.My knowledge about quantum computation is supported by his deep understanding of it.I am very motivated by his strong enthusiasm for realizing quantum computer.Mr. Amarsanaa Davaasuren is a collaborator of the result about quantum error correction using machine learning discussed in Chapter 4 of this thesis.His many creative ideas about both machine learning and quantum information have amazed me.The result of Chapter 4 is largely supported by his collaboration.Assist.Prof. Takanori Sugiyama gave me lectures about the latest and essential problems in near-term quantum devices.In particular, his lectures were vital for us to find the research topic of an efficient simulation of quantum circuits of quantum error correction under practical noise models, which is discussed in Chapter 3 of this thesis.I have been financially supported by Advanced Leading Graduate Course for Photon Science (ALPS).During this program, I have had an opportunity to discuss with Prof. Akira Furusawa.His advice from the standpoint of an experimental researcher helps my practical understanding of experimental systems.His philosophy as a professional researcher shapes my attitude to research.I also would like to thank the members and alumni of Koashi's group.In particular, I thank Assoc.Prof. Haruka Tanji-Suzuki and Assist.Prof. Toshihiko Sasaki for advice about from fundamental physics to presentation skills.My skills as a researcher are trained through discussions with them.I also thank Dr. Yoshi