Abstract We investigate the question which communication tasks can be accomplished within a given operational theory. The concrete task is to find out which communication matrices have a prepare-and-measure implementation with multiple states and a single measurement from a given theory, without using shared randomness. To set a general framework for this question we develop the ultraweak matrix majorization in the set of communication matrices. This preorder gives us means to determine when one communication task is more difficult than another. Furthermore, we introduce several monotones which can be used to compare and characterize the communication matrices. We observe that not only do the monotones allow us to compare communication matrices, but also their maximal values in a given theory are seen to relate to some physical properties of the theory. The maximal values can then be thought as ‘dimensions’, allowing us to compare different theories to each other. We analyse the introduced monotones one by one and demonstrate how the set of implementable communication matrices is different in several theories with the focus being mainly on the difference between classical and quantum theories of a given dimension.
Abstract We investigate the question which communication tasks can be accomplished within a given operational theory. The concrete task is to find out which communication matrices have a prepare-and-measure implementation with multiple states and a single measurement from a given theory, without using shared randomness. To set a general framework for this question we develop the ultraweak matrix majorization in the set of communication matrices. This preorder gives us means to determine when one communication task is more difficult than another. Furthermore, we introduce several monotones which can be used to compare and characterize the communication matrices. We observe that not only do the monotones allow us to compare communication matrices, but also their maximal values in a given theory are seen to relate to some physical properties of the theory. The maximal values can then be thought as ‘dimensions’, allowing us to compare different theories to each other. We analyse the introduced monotones one by one and demonstrate how the set of implementable communication matrices is different in several theories with the focus being mainly on the difference between classical and quantum theories of a given dimension.
A prepare-and-measure scenario is naturally described by a communication matrix that collects all conditional outcome probabilities of the scenario into a row-stochastic matrix. The set of all possible communication matrices is partially ordered via the possibility to transform one matrix to another by pre- and post-processings. By considering maximal elements in this preorder for a subset of matrices implementable in a given theory, it becomes possible to identify communication matrices of maximum utility, i.e., matrices that are not majorized by any other matrices in the theory. The identity matrix of an appropriate size is the greatest element in classical theories, while the maximal elements in quantum theory have remained unknown. We completely characterize the maximal elements in quantum theory, thereby revealing the essential structure of the set of quantum communication matrices. In particular, we show that the identity matrix is the only maximal element in quantum theory but, as opposed to a classical theory, it is not the greatest element. Quantum theory can hence be seen to be distinct from classical theory by the existence of incompatible communication matrices.
Abstract We introduce a class of communication tests where the task is to communicate partial ignorance by means of a physical system. We present a full characterization of the implementations of these tests in the qubit case and partial results for qudits. A peculiar observation is that two physical systems with the same operational dimensions may differ with respect to implementations of these tasks, as is shown to be the case for the qubit and rebit. Finally, we consider the natural question whether some of the communication tests are more difficult than others. A new preordering that we call the ultraweak matrix majorization is presented to answer this question in a theory-independent way.
In this thesis, we consider the properties of measurements in quantum theory and other operational theories. After having introduced the framework of operational theories, we consider a communication scheme based on an experimental prepare-and-measure scenario and demonstrate this with different communication tasks. This gives us context for how the different communication tasks can be implemented in different theories, in doing so establishing quantum theory intuitively as an operational theory among other theories. The main property of measurements we focus on in this work is the simulation of measurements, which consists of manipulating the inputs and outputs of the measurement devices. We study how using this process on existing measurement devices can be used to operationally imitate new devices, and what kind of structure the simulation process induces on measurements. We also consider applications of simulability. Firstly, we consider operational restrictions imposed upon measurements. We argue that the restricted set of physical measurements must be closed with respect to the simulation process since the simulation of physical devices must lead to other physically feasible devices. We demonstrate different types of restrictions by classifying them. As a second application we see how the simulation of measurements relates to compatibility of measurements and how it can be viewed as a generalisation of it. This allows us to present an operational principle previously known to quantum theory, the no-free-information principle, according to which any measurement that is compatible with all other measurement must not provide any useful, and therefore free, information about the system. Whilst this principle holds in quantum theory, there are non-classical theories for which it is violated, and so enforcing this principle may be considered a way to exclude some unphysical theories.
We introduce a generalization of the communication of partial ignorance where both parties of a prepare-and-measure setup receive inputs from a third party before a success metric is maximized over the measurements and preparations. We call these communication scenarios partial ignorance communication tasks of type Tn,m, where n indicates the number of possible correct answers in the communication task and m loosely represents the information about the correct answer that is revealed to the party preparing states. Various methods are used to obtain bounds on the success metrics, including semidefinite programs, ultraweak monotones for communication matrices, and frame theory for quantum states. The simplest scenarios in this alternative generalized prepare-and-measure setting, partial-ignorance communication tasks of types T3,1, T4,1, and T4,2, are analyzed exhaustively for bits and qudits. Finally, this generalized setting allows the introduction of operational equivalences to the preparations and measurements, allowing us to analyze and observe a contextual advantage for quantum theory in the partial ignorance communication task of type T4,1.
Quantum theory is, in some sense, “non-classical.” For instance, the behavior of entangled systems (i.e., shared quantum information) under measurements cannot, in general, be explained by shared classical information. With classical communication, on the other hand, both the correlations entanglement leads to as well as quantum channels can be reproduced in principle. Here, crucial questions are whether the required communications is finite; if so, then its exact amount is related to the “degree of non-classicality” of the quantum primitive. We apply information-theoretic results such as the reverse Shannon theorem for determining the required communication in the asymptotic limit. The communication complexity of a quantum channel is the minimal amount of classical communication required for classically simulating the process of preparation, transmission through the channel, and subsequent measurement of a quantum state. At present, only little is known about this quantity. Our generic procedure allows for systematically evaluating the communication complexity of channels in any general probabilistic theory, in particular quantum theory. The procedure is constructive and provides the most efficient classical protocols. We illustrate it by evaluating the communication complexity of sending single qubits over a noiseless quantum channel with some finite sets of quantum states and measurements. As a second application, we determine the classical-communication rate required for the simulation of the behavior under measurements of entangled states. Here, the communication cost can be directly interpreted as the “non-classicality” of the correlation. A particular example is the simulation of non-maximally entangled pure qubit pairs, where we find the required communication rate to behave monotonically with the strength of the entanglement. For different measures of non-locality, such as the number of required non-local (PR) boxes, another behavior had been reported for the single-shot scenario.
Communication complexity is a fundamental aspect of information science, concerned with the amount of communication required to solve a problem distributed among multiple parties. The standard quantification of one-way communication complexity relies on the minimal dimension of the communicated systems. In this paper, we measure the communication complexity of a task by the minimal required to accomplish it, while leaving the dimension of the communicated systems unconstrained. Distinguishability is defined as the maximum probability of correctly guessing the sender's input from the message, quantifying the message's distinctiveness relative to the sender's input. This measure becomes especially relevant when maintaining the confidentiality of the sender's input is essential. After establishing the generic framework, we focus on three relevant families of communication complexity tasks—the random access codes, equality problems defined by graphs, and the pair-distinguishability tasks. We derive general lower bounds on the minimal classical distinguishability as a function of the success metric of these tasks. We demonstrate that quantum communication outperforms classical communication presenting explicit protocols and utilizing semidefinite programming methods. In particular, we demonstrate for random access codes and Hadamard graph-based equality problems. Specifically, we show that the classical-to-quantum ratio of minimal distinguishability required to achieve the same success metric escalates polynomially and exponentially with the complexity of these tasks, reaching arbitrarily large values. Published by the American Physical Society 2024