Abstract Associative memories are devices storing information that can be fully retrieved given partial disclosure of it. We examine a toy model of associative memory and the ultimate limitations to which it is subjected within the framework of general probabilistic theories (GPTs), which represent the most general class of physical theories satisfying some basic operational axioms. We ask ourselves how large the dimension of a GPT should be so that it can accommodate 2 m states with the property that any N of them are perfectly distinguishable. Call d ( N , m ) the minimal such dimension. Invoking an old result by Danzer and Grünbaum, we prove that d ( 2 , m ) = m + 1 , to be compared with O ( 2 m ) when the GPT is required to be either classical or quantum. This yields an example of a task where GPTs outperform both classical and quantum theory exponentially. More generally, we resolve the case of fixed N and asymptotically large m, proving that d ( N , m ) ⩽ m 1 + o N ( 1 ) (as m → ∞ ) for every N ⩾ 2 , which yields again an exponential improvement over classical and quantum theories. Finally, we develop a numerical approach to the general problem of finding the largest N-wise mutually distinguishable set for a given GPT, which can be seen as an instance of the maximum clique problem on N-regular hypergraphs.
Abstract Associative memories are devices storing information that can be fully retrieved given partial disclosure of it. We examine a toy model of associative memory and the ultimate limitations to which it is subjected within the framework of general probabilistic theories (GPTs), which represent the most general class of physical theories satisfying some basic operational axioms. We ask ourselves how large the dimension of a GPT should be so that it can accommodate 2 m states with the property that any N of them are perfectly distinguishable. Call d ( N , m ) the minimal such dimension. Invoking an old result by Danzer and Grünbaum, we prove that d ( 2 , m ) = m + 1 , to be compared with O ( 2 m ) when the GPT is required to be either classical or quantum. This yields an example of a task where GPTs outperform both classical and quantum theory exponentially. More generally, we resolve the case of fixed N and asymptotically large m, proving that d ( N , m ) ⩽ m 1 + o N ( 1 ) (as m → ∞ ) for every N ⩾ 2 , which yields again an exponential improvement over classical and quantum theories. Finally, we develop a numerical approach to the general problem of finding the largest N-wise mutually distinguishable set for a given GPT, which can be seen as an instance of the maximum clique problem on N-regular hypergraphs.
General probabilistic theories (GPTs) are theoretical models having states, measurements, and probabilities of obtaining measurement outcomes.For example, classical probability theory and quantum theory are GPTs with probability vectors and density matrices as states, respectively.In the study of GPTs, one often describes a finite number of GPTs A 1 , . . ., A n together, as one GPT A = A 1 • • • A n .In this case, we say that A is a whole system of subsystems A 1 , . . ., A n .If A 1 , . . ., A n are quantum systems, then A is called a locally quantum system.A quantum system is locally quantum, but there are many other locally quantum systems.In this thesis, we study three topics associated with quantum systems and locally quantum systems.The first one is capacity.For a GPT, the maximum number of simultaneously and perfectly distinguishable states is called the capacity.It is known that the capacity does not really depend on the GPT.In this thesis, we propose a statement S to determine the capacities of special locally quantum systems, and prove a weaker statement WS.Statement WS is a statement associated with tensor product spaces over C. Our proof works even if replacing the scalar field C with an arbitrary infinite field F. We also show a partial result for finite fields.The second one is differential privacy (DP).DP was born in the study to utilize private data while protecting the data (privacy-preserving data mining, PPDM).For this reason, DP has been studied by using classical probability theory, and has almost never been studied in quantum information theory.In this thesis, we define a quantum version of DP (called classical-quantum DP) and investigate its mathematical aspects.We define the set CQ n of all classical-quantum differentially private n-tuples of quantum states and the subset EC n of CQ n that is essentially classical.We prove that EC n = CQ n if n = 2 and EC n = CQ n if n ≥ 3.The third one is perfect discrimination of two states.In quantum theory, orthogonality is a necessary and sufficient condition to distinguish two states perfectly (denote this equivalence by E).However, equivalence E does not hold for a general GPT.In this thesis, we construct continuous one-parameter families of locally quantum systems in a certain natural manner, and investigate perfect discrimination of two states in the framework of those locally quantum systems.These one-parameter families contain a locally quantum system sufficiently close to a quantum system.Nevertheless, we show that they violate equivalence E.
For a collection of states indexed by [n]=1,…,n, let F(H) denote the optimal unnormalized minimum discrimination error for each nonempty subfamily H⊆[n]. We call F the discrimination profile and characterize exactly which profiles can arise in a general probabilistic theory (GPT). For fixed n, the GPT region Gn is a bounded rational polytope, giving a hierarchy Cn⊆Qn⊆Gn of classical, quantum, and GPT profiles, analogous to the local--quantum--no-signalling hierarchy in Bell theory.
For n=3 we determine the classical and GPT polytopes explicitly. Within G3, the classical region is characterized by β:=F(123)−F(12)−F(13)−F(23)≤0, while the GPT maximum is 1. For qubit triples, the maximal value is attained by the trine, βtr=33/2−2, and we prove the dimension-independent quantum bound βQ≤2/3, with a slight further improvement. Hence 0=βC<33/2−2≤βQ≤2/3<1=βGPT. We conjecture βQ=βtr and prove this for arbitrary pure-state triples, together with further supporting evidence.
For arbitrary n, every classical facet admitting a GPT violation already admits a quantum violation in dimension at most 3. A four-state qubit example shows that quantum success profiles need not be submodular, unlike for n=3. Finally, we exhibit a four-dimensional quantum triple whose discrete profile is classical for all subfamilies but becomes nonclassical when unequal priors are allowed.
Is entanglement an exclusive feature of quantum systems, or is it common to all non-classical theories? And if this is the case, how strong is quantum mechanical entanglement as compared to that exhibited by other theories? The first part of this thesis deals with these questions by considering quantum theory as part of a wider landscape of physical theories, collectively called general probabilistic theories (GPTs). Among the other things, this manuscript contains a detailed introduction to the abstract state space formalism for GPTs. We start with a comprehensive review of the proof of a famous theorem by Ludwig that constitutes one of its cornerstones (Ch. 1). After explaining the basic rules of the game, we translate our questions into precise conjectures and present our progress toward a full solution (Ch. 2). In Ch. 3 we consider entanglement at the level of measurements instead of states, focusing on one of its main implications, i.e. data hiding. We determine the maximal data hiding strength that a quantum mechanical system can exhibit, and also the maximum value among all GPTs, finding that the former scales as the square root of the latter. In the second part of this manuscript we look into quantum entanglement. In Ch. 4 we discuss the entanglement transformation properties of a class of maps that model white noise acting either locally or globally on a bipartite system. In Ch. 5 we employ matrix analysis tools to develop a unified approach to Gaussian entanglement. The third part of this thesis concerns more general forms of non-classical correlations in bipartite continuous variable systems. In Ch. 6 we devise a general scheme that allows to consistently classify correlations of bipartite Gaussian states into classical and quantum ones. Finally, Ch. 7 explores some problems connected with a certain strong subadditivity matrix inequality.
We review our models of quantum associative memories that represent the “quantization” of fully coupled neural networks like the Hopfield model. The idea is to replace the classical irreversible attractor dynamics driven by an Ising model with pattern-dependent weights by the reversible rotation of an input quantum state onto an output quantum state consisting of a linear superposition with probability amplitudes peaked on the stored pattern closest to the input in Hamming distance, resulting in a high probability of measuring a memory pattern very similar to the input. The unitary operator implementing this transformation can be formulated as a sequence of one-qubit and two-qubit elementary quantum gates and is thus the exponential of an ordered quantum Ising model with sequential operations and with pattern-dependent interactions, exactly as in the classical case. Probabilistic quantum memories, that make use of postselection of the measurement result of control qubits, overcome the famed linear storage limitation of their classical counterparts because they permit to completely eliminate crosstalk and spurious memories. The number of control qubits plays the role of an inverse fictitious temperature. The accuracy of pattern retrieval can be tuned by lowering the fictitious temperature under a critical value for quantum content association while the complexity of the retrieval algorithm remains polynomial for any number of patterns polynomial in the number of qubits. These models thus solve the capacity shortage problem of classical associative memories, providing a polynomial improvement in capacity. The price to pay is the probabilistic nature of information retrieval.
A central question in quantum information is whether a given set of states can provide an advantage in some information-processing task. We establish a universal connection between two such questions: how well a set of states can be discriminated, and whether it can power tasks whose advantage stems from generalized contextuality. Working in the framework of generalized probabilistic theories (GPTs), which includes quantum and classical systems as special cases, we show that any set of states able to provide a nonclassical advantage in a contextuality-powered task must obey nontrivial upper bounds on the success probability of every state discrimination task using the full set. Contextual advantage therefore implies limited distinguishability, exposing a trade-off between two basic operational resources. Importantly, this is more than a statement about the idealized limit: perfect distinguishability is not needed to preclude contextuality. Our thresholds lie strictly below unity, so any set whose discrimination performance exceeds them while still imperfectly distinguishable is already guaranteed to admit a noncontextual explanation. The bounds follow from a simple geometric property, linear dependence of the state set, take a closed analytical form, and depend only on the prior of the task and the convex geometry of the states. As an illustration, we apply them to generalized parity-oblivious multiplexing, where sufficiently high success in the task implies that at least one sub-ensemble of the codebook cannot power any contextual advantage.
Abstract Arguably, the largest class of stochastic processes generated by means of a finite memory consists of those that are sequences of observations produced by sequential measurements in a suitable generalized probabilistic theory (GPT). These are constructed from a finite-dimensional memory evolving under a set of possible linear maps, and with probabilities of outcomes determined by linear functions of the memory state. Examples of such models are given by classical hidden Markov processes, where the memory state is a probability distribution, and at each step it evolves according to a non-negative matrix, and hidden quantum Markov processes, where the memory is a finite-dimensional quantum system, and at each step it evolves according to a completely positive map. Here we show that the set of processes admitting a finite-dimensional explanation do not need to be explainable in terms of either classical probability or quantum mechanics. To wit, we exhibit families of processes that have a finite-dimensional explanation, defined manifestly by the dynamics of an explicitly given GPT, but that do not admit a quantum, and therefore not even classical, explanation in finite dimension. Furthermore, we present a family of quantum processes on qubits and qutrits that do not admit a classical finite-dimensional realization, which includes examples introduced earlier by Fox, Rubin, Dharmadikari and Nadkarni as functions of infinite-dimensional Markov chains, and lower bound the size of the memory of a classical model realizing a noisy version of the qubit processes.