This is a set of lecture notes suitable for a Master's course on quantum computation and information from the perspective of theoretical computer science. The first version was written in 2011, with many extensions and improvements in subsequent years. The first 10 chapters cover the circuit model and the main quantum algorithms (Deutsch-Jozsa, Simon, Shor, Hidden Subgroup Problem, Grover, quantum walks, Hamiltonian simulation and HHL). They are followed by 3 chapters about complexity, 4 chapters about distributed ("Alice and Bob") settings, and a final chapter about quantum error correction. Appendices A and B give a brief introduction to the required linear algebra and some other mathematical and computer science background. All chapters come with exercises, with some hints provided in Appendix C.

相关内容

iOS 8 提供的应用间和应用跟系统的功能交互特性。
• Today (iOS and OS X): widgets for the Today view of Notification Center
• Share (iOS and OS X): post content to web services or share content with others
• Actions (iOS and OS X): app extensions to view or manipulate inside another app
• Photo Editing (iOS): edit a photo or video in Apple's Photos app with extensions from a third-party apps
• Finder Sync (OS X): remote file storage in the Finder with support for Finder content annotation
• Storage Provider (iOS): an interface between files inside an app and other apps on a user's device
• Custom Keyboard (iOS): system-wide alternative keyboards

Source: iOS 8 Extensions: Apple’s Plan for a Powerful App Ecosystem

Variational Quantum Eigensolvers (VQEs) have recently attracted considerable attention. Yet, in practice, they still suffer from the efforts for estimating cost function gradients for large parameter sets or resource-demanding reinforcement strategies. Here, we therefore consider recent advances in weight-agnostic learning and propose a strategy that addresses the trade-off between finding appropriate circuit architectures and parameter tuning. We investigate the use of NEAT-inspired algorithms which evaluate circuits via genetic competition and thus circumvent issues due to exceeding numbers of parameters. Our methods are tested both via simulation and on real quantum hardware and are used to solve the transverse Ising Hamiltonian and the Sherrington-Kirkpatrick spin model.

Discrimination between objects, in particular quantum states, is one of the most fundamental tasks in (quantum) information theory. Recent years have seen significant progress towards extending the framework to point-to-point quantum channels. However, with technological progress the focus of the field is shifting to more complex structures: Quantum networks. In contrast to channels, networks allow for intermediate access points where information can be received, processed and reintroduced into the network. In this work we study the discrimination of quantum networks and its fundamental limitations. In particular when multiple uses of the network are at hand, the rooster of available strategies becomes increasingly complex. The simplest quantum network that capturers the structure of the problem is given by a quantum superchannel. We discuss the available classes of strategies when considering $n$ copies of a superchannel and give fundamental bounds on the asymptotically achievable rates in an asymmetric discrimination setting. Furthermore, we discuss achievability, symmetric network discrimination, the strong converse exponent, generalization to arbitrary quantum networks and finally an application to an active version of the quantum illumination problem.

The motivation for this thesis was to recast quantum self-testing [MY98,MY04] in operational terms. The result is a category-theoretic framework for discussing the following general question: How do different implementations of the same input-output process compare to each other? In the proposed framework, an input-output process is modelled by a causally structured channel in some fixed theory, and its implementations are modelled by causally structured dilations formalising hidden side-computations. These dilations compare through a pre-order formalising relative strength of side-computations. Chapter 1 reviews a mathematical model for physical theories as semicartesian symmetric monoidal categories. Many concrete examples are discussed, in particular quantum and classical information theory. The key feature is that the model facilitates the notion of dilations. Chapter 2 is devoted to the study of dilations. It introduces a handful of simple yet potent axioms about dilations, one of which (resembling the Purification Postulate [CDP10]) entails a duality theorem encompassing a large number of classic no-go results for quantum theory. Chapter 3 considers metric structure on physical theories, introducing in particular a new metric for quantum channels, the purified diamond distance, which generalises the purified distance [TCR10,Tom12] and relates to the Bures distance [KSW08a]. Chapter 4 presents a category-theoretic formalism for causality in terms of '(constructible) causal channels' and 'contractions'. It simplifies aspects of the formalisms [CDP09,KU17] and relates to traces in monoidal categories [JSV96]. The formalism allows for the definition of 'causal dilations' and the establishment of a non-trivial theory of such dilations. Chapter 5 realises quantum self-testing from the perspective of chapter 4, thus pointing towards the first known operational foundation for self-testing.

We consider the problem of communicating a general bivariate function of two classical sources observed at the encoders of a classical-quantum multiple access channel. Building on the techniques developed for the case of a classical channel, we propose and analyze a coding scheme based on coset codes. The proposed technique enables the decoder recover the desired function without recovering the sources themselves. We derive a new set of sufficient conditions that are weaker than the current known for identified examples. This work is based on a new ensemble of coset codes that are proven to achieve the capacity of a classical-quantum point-to-point channel.

We introduce a graphical language for coherent control of general quantum channels inspired by practical quantum optical setups involving polarising beam splitters (PBS). As standard completely positive trace preserving maps are known not to be appropriate to represent coherently controlled quantum channels, we propose to instead use purified channels, an extension of Stinespring's dilation. We characterise the observational equivalence of purified channels in various coherent-control contexts, paving the way towards a faithful representation of quantum channels under coherent control.

Intuitionistic belief has been axiomatized by Artemov and Protopopescu as an extension of intuitionistic propositional logic by means of the distributivity scheme K, and of co-reflection $A\rightarrow\Box A$. This way, belief is interpreted as a result of verification, and it fits an extended Brouwer-Heyting-Kolmogorov interpretation for intuitionistic propositional logic with an epistemic modality. In the present paper, structural properties of a natural deduction system $\mathsf{IEL}^{-}$ for intuitionistic belief are investigated also in the light of categorical semantics. The focus is on the analyticity of the calculus, so that the normalization theorem and the subformula property are proven firstly. From these, decidability and consistency of the logic follow as corollaries. Finally, disjunction properties, $\Box$-primality, and admissibility of reflection rule are established by using purely proof-theoretic methods.

Quantum channel estimation and discrimination are fundamentally related information processing tasks of interest in quantum information science. In this paper, we analyze these tasks by employing the right logarithmic derivative Fisher information and the geometric R\'enyi relative entropy, respectively, and we also identify connections between these distinguishability measures. A key result of our paper is that a chain-rule property holds for the right logarithmic derivative Fisher information and the geometric R\'enyi relative entropy for the interval $\alpha\in(0,1)$ of the R\'enyi parameter $\alpha$. In channel estimation, these results imply a condition for the unattainability of Heisenberg scaling, while in channel discrimination, they lead to improved bounds on error rates in the Chernoff and Hoeffding error exponent settings. More generally, we introduce the amortized quantum Fisher information as a conceptual framework for analyzing general sequential protocols that estimate a parameter encoded in a quantum channel, and we use this framework, beyond the aforementioned application, to show that Heisenberg scaling is not possible when a parameter is encoded in a classical-quantum channel. We then identify a number of other conceptual and technical connections between the tasks of estimation and discrimination and the distinguishability measures involved in analyzing each. As part of this work, we present a detailed overview of the geometric R\'enyi relative entropy of quantum states and channels, as well as its properties, which may be of independent interest.

Traditionally, expert epidemiologists devise policies for disease control through a mixture of intuition and brute force. Namely, they use their know-how to narrow down the set of logically conceivable policies to a small family described by a few parameters, following which they conduct a grid search to identify the optimal policy within the set. This scheme is not scalable, in the sense that, when used to optimize over policies which depend on many parameters, it will likely fail to output an optimal disease policy in time for its implementation. In this article, we use techniques from convex optimization theory and machine learning to conduct optimizations over disease policies described by hundreds of parameters. In contrast to past approaches for policy optimization based on control theory, our framework can deal with arbitrary uncertainties on the initial conditions and model parameters controlling the spread of the disease. In addition, our methods allow for optimization over weekly-constant policies, specified by either continuous or discrete government measures (e.g.: lockdown on/off). We illustrate our approach by minimizing the total time required to eradicate COVID-19 within the Susceptible-Exposed-Infected-Recovered (SEIR) model proposed by Kissler \emph{et al.} (March, 2020).

An $n\overset{p}{\mapsto}m$ random access code (RAC) is an encoding of $n$ bits into $m$ bits such that any initial bit can be recovered with probability at least $p$, while in a quantum RAC (QRAC), the $n$ bits are encoded into $m$ qubits. Since its proposal, the idea of RACs was generalized in many different ways, e.g. allowing the use of shared entanglement (called entanglement-assisted random access code, or simply EARAC) or recovering multiple bits instead of one. In this paper we generalize the idea of RACs to recovering the value of a given Boolean function $f$ on any subset of fixed size of the initial bits, which we call $f$-random access codes. We study and give protocols for $f$-random access codes with classical ($f$-RAC) and quantum ($f$-QRAC) encoding, together with many different resources, e.g. private or shared randomness, shared entanglement ($f$-EARAC) and Popescu-Rohrlich boxes ($f$-PRRAC). The success probability of our protocols is characterized by the \emph{noise stability} of the Boolean function $f$. Moreover, we give an \emph{upper bound} on the success probability of any $f$-QRAC with shared randomness that matches its success probability up to a multiplicative constant (and $f$-RACs by extension), meaning that quantum protocols can only achieve a limited advantage over their classical counterparts.

Graphical causal inference as pioneered by Judea Pearl arose from research on artificial intelligence (AI), and for a long time had little connection to the field of machine learning. This article discusses where links have been and should be established, introducing key concepts along the way. It argues that the hard open problems of machine learning and AI are intrinsically related to causality, and explains how the field is beginning to understand them.

L. Franken,B. Georgiev,S. Muecke,M. Wolter,N. Piatkowski,C. Bauckhage
0+阅读 · 3月3日
Christoph Hirche
0+阅读 · 3月3日
0+阅读 · 3月2日
Cyril Branciard,Alexandre Clément,Mehdi Mhalla,Simon Perdrix
0+阅读 · 3月2日
Miguel Navascues,Costantino Budroni,Yelena Guryanova
0+阅读 · 3月1日
João F. Doriguello,Ashley Montanaro
0+阅读 · 2月27日
Bernhard Schölkopf
9+阅读 · 2019年11月24日

5+阅读 · 2019年6月18日
Call4Papers
6+阅读 · 2019年2月25日

10+阅读 · 2018年12月24日

8+阅读 · 2018年2月25日

6+阅读 · 2017年12月22日

13+阅读 · 2017年11月9日

12+阅读 · 2017年10月1日

3+阅读 · 2017年9月15日
Top