This special issue will focus on Quantum Information Science, especially Communication and Computing. It will aim to bridge theory, practice and basic science, ranging from the state-of-the-art in quantum computing, to communication, coding, cryptography, and compression, as well as the current challenges remaining. An overarching theme is how the information-theoretic and quantum-physical perspectives complement each other in building these quantum technologies.
Quantum phenomena provide computing and information handling paradigms that are clearly different and very likely much more powerful than their classical counterparts. Over the past few years, several governments throughout the world have allocated substantial funding aimed at boosting quantum information science. Much progress has been made on the theoretical side, and experiments have been conducted in which quantum computational operations were executed on a small number of quantum bits. In particular, 2019 marked the anniversaries of two principal developments in the field: the 25 years of quantum factoring and 35 years of quantum key distribution algorithms. This special issue showcases the information and coding theory related questions that are central to the field today.
Quantum information science is an exciting, wide, rapidly progressing, cross-disciplinary field, and that very nature makes it both attractive and hard to enter. In this primer, we first provide answers to the three essential questions that any newcomer needs to know: How is quantum information represented? How is quantum information processed? How is classical information extracted from quantum states? We then introduce the most basic quantum information theoretic notions concerning entropy, sources, and channels, as well as secure communications and error correction. We conclude with examples that illustrate the power of quantum correlations. No prior knowledge of quantum mechanics is assumed.
We study quantum statistical inference tasks of hypothesis testing and their canonical variations, in order to review relations between their corresponding figures of merit-measures of statistical distance-and demonstrate the crucial differences which arise in the quantum regime in contrast to the classical setting. In our analysis, we primarily focus on the geometric approach to data inference problems, within which the aforementioned measures can be neatly interpreted as particular forms of divergences that quantify distances in the space of probability distributions or, when dealing with quantum systems, of density matrices. Moreover, with help of the standard language of Riemannian geometry we identify both the metrics such divergences must induce and the relations such metrics must then naturally inherit. Finally, we discuss exemplary applications of such a geometric approach to problems of quantum parameter estimation, “speed limits” and thermodynamics.
A common scenario in distributed computing involves a client who asks a server to perform a computation on a remote computer. An important problem is to determine the minimum amount of communication needed to specify the desired computation. Here we extend this problem to the quantum domain, analyzing the total amount of (classical and quantum) communication needed by a server in order to accurately execute a quantum process chosen by a client from a parametric family of quantum processes. We derive a general lower bound on the communication cost, establishing a relation with the precision limits of quantum metrology: if a v-dimensional family of processes can be estimated with mean squared error n-β by using n parallel queries, then the communication cost for n parallel executions of a process in the family is at least (β v/2 - ε) logn qubits at the leading order in n, for every ε > 0. For a class of quantum processes satisfying the standard quantum limit (β = 1), we show that the bound can be attained by transmitting an approximate classical description of the desired process. For quantum processes satisfying the Heisenberg limit (β = 2), our bound shows that the communication cost is at least twice as the cost of communicating standard quantum limited processes with the same number of parameters.
We introduce and analyse a multiple-access channel with two senders and one receiver, in the presence of i.i.d. noise coming from the environment. Partial side information about the environmental states allows the senders to modulate their signals accordingly. An adversarial jammer with its own access to information on environmental states and the modulation signals can jam a fraction of the transmissions. Our results show that for many choices of the system parameters, entanglement shared between the two senders allows them to communicate at non-zero rates with the receiver, while for the same parameters the system forbids any communication without entanglement-assistance, even if the senders have access to common randomness (local correlations). A simplified model displaying a similar behaviour but with a compound channel instead of a jammer is outlined to introduce basic aspects of the modeling. We complement these results by demonstrating that there even exist model parameters for which entanglement-assisted communication is no longer possible, but a hypothetical use of nonlocal no-signalling correlations between Alice and Bob could enable them to communicate to Charlie again.
Recently, Anshu et al. introduced “partially” smoothed information measures and used them to derive tighter bounds for several information-processing tasks, including quantum state merging and privacy amplification against quantum adversaries [鶹ýAV Trans. Inf. Theory 66, 5022 (2020)]. Yet, a tight second-order asymptotic expansion of the partially smoothed conditional min-entropy in the i.i.d. setting remains an open question. Here we establish the second-order term in the expansion for pure states, and find that it differs from that of the original “globally” smoothed conditional min-entropy. Remarkably, this reveals that the second-order term is not uniform across states, since for other classes of states the second-order term for partially and globally smoothed quantities coincides. In view of the tight bounds on the entanglement cost of state merging in terms of the partially-smoothed conditional min-entropy by Anshu et al., this indicates that the second-order asymptotic rate for that task will not separate so neatly into a term depending on the state (the variance) and a term depending on the error (the quantile). Finally, by relating the task of quantum compression to that of quantum state merging, our derived expansion allows us to determine the second-order asymptotic expansion of the optimal rate of quantum data compression. This closes a gap in the bounds determined by Datta and Leditzky [鶹ýAV Trans. Inf. Theory 61, 582 (2015)], and shows that the straightforward compression protocol of cutting off the eigenspace of least weight is indeed asymptotically optimal at second order.
We continue the study of the quantum channel version of Shannon's zero-error capacity problem. We generalize the celebrated Haemers bound to noncommutative graphs (obtained from quantum channels). We prove basic properties of this bound, such as additivity under the direct sum and submultiplicativity under the tensor product. The Haemers bound upper bounds the Shannon capacity of noncommutative graphs, and we show that it can outperform other known upper bounds, including noncommutative analogues of the Lovász theta function (Duan-Severini-Winter, 鶹ýAV Trans. Inform. Theory, 2013 and Boreland-Todorov-Winter, arXiv preprint, 2019).
We consider a setting where a stream of qubits is processed sequentially. We derive fundamental limits on the rate at which classical information can be transmitted using qubits that decohere as they wait to be processed. Specifically, we model the sequential processing of qubits using a single server queue, and derive expressions for the classical capacity of such a quantum `queue-channel.' Focusing on two important noise models, namely the erasure channel and the depolarizing channel, we obtain explicit single-letter capacity formulas in terms of the stationary waiting time of qubits in the queue. Our capacity proof also implies that a `classical' coding/decoding strategy is optimal, i.e., an encoder which uses only orthogonal product states, and a decoder which measures in a fixed product basis, are sufficient to achieve the classical capacity of both queue-channels. Our proof technique for the converse theorem generalizes readily - in particular, whenever the underlying quantum noise channel is additive, we can obtain a single-letter upper bound on the classical capacity of the corresponding quantum queue-channel. More broadly, our work begins to quantitatively address the impact of decoherence on the performance limits of quantum information processing systems.
It is known that quantum resources can allow us to achieve a family of equilibria that can have sometimes a better social welfare, while guaranteeing privacy. We use graph games to propose a way to build non-cooperative games from graph states, and we show how to achieve an unlimited improvement with quantum advice compared to classical advice.
The entropy of a quantum system is a measure of its randomness, and has applications in measuring quantum entanglement. We study the problem of estimating the von Neumann entropy, S(ρ), and Rényi entropy, Sα(ρ) of an unknown mixed quantum state ρ in d dimensions, given access to independent copies of ρ. We provide algorithms with copy complexity O(d2/α) for estimating Sα(ρ) for α <; 1, and copy complexity O(d2) for estimating S(ρ), and Sα(ρ) for non-integral α > 1. These bounds are at least quadratic in d, which is the order dependence on the number of copies required for estimating the entire state ρ. For integral α > 1, on the other hand, we provide an algorithm for estimating Sα(ρ) with a sub-quadratic copy complexity of O(d2-2/α), and we show the optimality of the algorithms by providing a matching lower bound.
Quantum state discrimination (QSD) is a key enabler in quantum sensing and networking, for which we envision the utility of non-coherent quantum states such as photon-added coherent states (PACSs). This paper addresses the problem of discriminating between two noisy PACSs. First, we provide representation of PACSs affected by thermal noise during state preparation in terms of Fock basis and quasi-probability distributions. Then, we demonstrate that the use of PACSs instead of coherent states can significantly reduce the error probability in QSD. Finally, we quantify the effects of phase diffusion and photon loss on QSD performance. The findings of this paper reveal the utility of PACSs in several applications involving QSD.
One of the main problems in quantum information systems is the presence of errors due to noise, and for this reason quantum error-correcting codes (QECCs) play a key role. While most of the known codes are designed for correcting generic errors, i.e., errors represented by arbitrary combinations of Pauli X, Y and Z operators, in this paper we investigate the design of stabilizer QECC able to correct a given number eg of generic Pauli errors, plus eZ Pauli errors of a specified type, e.g., Z errors. These codes can be of interest when the quantum channel is asymmetric in that some types of error occur more frequently than others. We first derive a generalized quantum Hamming bound for such codes, then propose a design methodology based on syndrome assignments. For example, we found a [[9, 1]] quantum error-correcting code able to correct up to one generic qubit error plus one Z error in arbitrary positions. This, according to the generalized quantum Hamming bound, is the shortest code with the specified error correction capability. Finally, we evaluate analytically the performance of the new codes over asymmetric channels.
Quantum stabilizer codes constructed from sparse matrices have good performance and can be efficiently decoded by belief propagation (BP). A conventional BP decoding algorithm treats binary stabilizer codes as additive codes over GF(4). This algorithm has a relatively complex process of handling check-node messages, which incurs higher decoding complexity. Moreover, BP decoding of a stabilizer code usually suffers a performance loss due to the many short cycles in the underlying Tanner graph. In this paper, we propose a refined BP decoding algorithm for quantum codes with complexity roughly the same as binary BP. For a given error syndrome, this algorithm decodes to the same output as the conventional quaternary BP but the passed node-to-node messages are single-valued, unlike the quaternary BP, where multivalued node-to-node messages are required. Furthermore, the techniques of message strength normalization can naturally be applied to these single-valued messages to improve the performance. Another observation is that the message-update schedule affects the performance of BP decoding against short cycles. We show that running BP with message strength normalization according to a serial schedule (or other schedules) may significantly improve the decoding performance and error floor in computer simulation.
In order to perform universal fault-tolerant quantum computation, one needs to implement a logical non-Clifford gate. Consequently, it is important to understand codes that implement such gates transversally. In this paper, we adopt an algebraic approach to characterize all stabilizer codes for which transversal $T$ and $T^{\dagger }$ gates preserve the codespace. Our Heisenberg perspective reduces this question to a finite geometry problem that translates to the design of certain classical codes. We prove three corollaries of this result: (a) For any non-degenerate $[\![n,k,d]\!]$ stabilizer code supporting a physical transversal $T$ (which might not be logical $T$ ), there exists an $[\![n,k,d]\!]$ CSS code with the same property; (b) Triorthogonal codes form the most general family of CSS codes that realize logical transversal $T$ via physical transversal $T$ ; (c) Triorthogonality is necessary for physical transversal $T$ on a CSS code to realize the logical identity. The main tool we use is a recent characterization of a particular family of diagonal gates in the Clifford hierarchy that are efficiently described by symmetric matrices over rings of integers [N. Rengaswamy et al., Phys. Rev. A 100, 022304]. We refer to these operations as Quadratic Form Diagonal (QFD) gates. Our framework generalizes all existing stabilizer code constructions that realize logical gates via transversal $T$ . We provide several examples of codes and briefly discuss connections to decreasing monomial codes, pin codes, generalized triorthogonality and quasitransversality. We partially extend these results towards characterizing all stabilizer codes that support transversal $\pi /2^{\ell }~Z$ -rotations. In particular, using Ax’s theorem on residue weights of polynomials, we provide an alternate characterization of logical gates induced by transversal $\pi /2^{\ell }~Z$ -rotations on a family of quantum Reed-Muller codes. We also briefly discuss a general approach to analyze QFD gates that might lead to a characterization of all stabilizer codes that support any given physical transversal 1- or 2-local diagonal gate.
Restricted Boltzmann Machines trained with different numbers of iterations were used to provide a large diverse set of energy functions each containing many local valleys (LVs). They were used to confirm the property of the D-Wave quantum annealer (QA) to find potentially important LVs in the energy functions of Markov Random Fields that may be missed by classical searches. Even after a prohibitively long classical search by simulated annealing (SA), as many as 30-50% of the QA-found LVs remained not found by the SA. In order to establish if those LVs represent potentially important regions of the configuration space, they were compared to LVs that were found by both techniques. With respect to most of the important LV parameters, the LVs found only by the QA (missed by SA) were distributed in a wide range of the parameters' values. In an attempt to explain which LVs could not be found easily by the SA, it was established that for large or small, shallow or deep, wide or narrow LVs, the LVs found only by the QA are distinguished by a few-times smaller size of the LV basin of attraction (BoA). Apparently, the size of the BoA is much less important for QA search compared to the classical search, allowing QA to easily find many potentially important (e.g., wide and deep) LVs missed by even prohibitively lengthy classical searches.
Due to Csiszár and Körner, the private capacity of classical wiretap channels has a single-letter characterization in terms of the private information. For quantum wiretap channels, however, it is known that regularization of the private information is necessary to reach the capacity. Here, we study hybrid classical-quantum wiretap channels in order to resolve to what extent quantum effects are needed to witness non-additivity phenomena in quantum Shannon theory. For wiretap channels with quantum inputs but classical outputs, we prove that the characterization of the capacity in terms of the private information stays single-letter. Hence, entangled input states are of no asymptotic advantage in this setting. For wiretap channels with classical inputs, we show by means of explicit examples that the private information already becomes non-additive when either one of the two receivers becomes quantum (with the other receiver staying classical). This gives non-additivity examples that are not caused by entanglement and illustrates that quantum adversaries are strictly different from classical adversaries in the wiretap model.
We introduce a new setting for two-party cryptography by introducing the notion of temporarily trusted third parties. These third parties act honest-but-curious during the execution of the protocol. Once the protocol concludes and the trust period expires, these third parties may collaborate with an adversarial party. We implement a variant of the cryptographic primitive of bit commitment in this setting, which we call erasable bit commitment. In this primitive, the sender has the choice of either opening or erasing her commitment after the commit phase. For example, she can ask for an erase before the trust period expires in case the conditions for opening the commitment have not been met. The erasure prevents a future coalition of the trusted party and the receiver from extracting any information about the commitment. However, this option also weakens the cryptographic primitive relative to standard bit commitment. Furthermore, the committed information is not revealed to the trusted node at any stage during the protocol. Our protocol requires a constant number of third parties and can tolerate a small number of corrupt third parties as well as implementation errors.
We investigate the quantum-secure covert-communication capabilities of lossy thermal-noise bosonic channels, the quantum-mechanical model for many practical channels. We determine the expressions for the covert capacity of these channels: Lno-EA, when Alice and Bob share only a classical secret, and LEA, when they benefit from entanglement assistance. We find that entanglement assistance alters the fundamental scaling law for covert communication. Instead of Lno-EA√n - rno-EA(n), rno-EA(n) = o(√n), entanglement assistance allows LEA√nlogn - rEA(n), rEA(n) = o(√nlogn), covert bits to be transmitted reliably over n channel uses.
Secret and perfect randomness is an essential resource in cryptography. Yet, it is not even clear that such exists. It is well known that the tools of classical computer science do not allow us to create secret and perfect randomness from a single weak public source. Quantum physics, on the other hand, allows for such a process, even in the most paranoid cryptographic sense termed “device-independent quantum cryptography”. We propose and prove the security of a new device-independent protocol that takes any single public Santha-Vazirani source as input and creates a secret close to uniform string in the presence of a quantum adversary. Our work is the first to achieve randomness amplification with all the following properties: (1) amplification and “privatization” of a public Santha-Vazirani source with arbitrary bias (2) the use of a device with only two components (3) non-vanishing extraction rate and (4) maximal noise tolerance. In particular, this implies that our protocol is the first protocol that can possibly be implemented with reachable parameters. We achieve these by combining three new tools: a particular family of Bell inequalities, a proof technique to lower bound entropy in the device-independent setting, and a framework for quantum-proof multi-source extractors.
We propose a protocol based on pulse-position modulation and multi-level coding that allows one to bootstrap traditional quantum key distribution protocols while ensuring covertness, in the sense that no statistical test by the adversary can detect the presence of communication over the quantum channel better than a random guess. When run over a bosonic channel, our protocol can leverage existing discrete-modulated continuous-variable protocols. Since existing techniques to bound Eve's information do not directly apply, we develop a new bound that results in positive, although very low, throughput for a range of channel parameters. The analysis of the protocol performance shows that covert secret key expansion is possible using a public authenticated classical channel and a quantum channel largely but not fully under the control of an adversary, which we precisely define. We also establish a converse result showing that, under the golden standard of quantum key distribution, by which the adversary completely controls the quantum channel, no covert key generation is possible.
In the classical private information retrieval (PIR) setup, a user wants to retrieve a file from a database or a distributed storage system (DSS) without revealing the file identity to the servers holding the data. In the quantum PIR (QPIR) setting, a user privately retrieves a classical file by receiving quantum information from the servers. The QPIR problem has been treated by Song et al. in the case of replicated servers, both without collusion and with all but one servers colluding. In this paper, the QPIR setting is extended to account for maximum distance separable (MDS) coded servers. The proposed protocol works for any [n,k]-MDS code and t-collusion with t = n-k. Similarly to the previous cases, the rates achieved are better than those known or conjectured in the classical counterparts. Further, it is demonstrated how the protocol can adapted to achieve significantly higher retrieval rates from DSSs encoded with a locally repairable code (LRC) with disjoint repair groups, each of which is an MDS code.