We consider the problem of transmitting classical information over a time-invariant channel with memory. A popular class of time-invariant channels with memory are finite-state-machine channels, where a classical state evolves over time and governs the relationship between the classical input and the classical output of the channel. For such channels, various techniques have been developed for estimating and bounding the information rate. In this paper we consider a class of time-invariant channels where a quantum state evolves over time and governs the relationship between the classical input and the classical output of the channel. We propose algorithms for estimating and bounding the information rate of such channels. In particular, we discuss suitable graphical models for doing the relevant computations.
We consider the problem of transmitting classical information over a time-invariant channel with memory. A popular class of time-invariant channels with memory are finite-state-machine channels, where a classical state evolves over time and governs the relationship between the classical input and the classical output of the channel. For such channels, various techniques have been developed for estimating and bounding the information rate. In this paper we consider a class of time-invariant channels where a quantum state evolves over time and governs the relationship between the classical input and the classical output of the channel. We propose algorithms for estimating and bounding the information rate of such channels. In particular, we discuss suitable graphical models for doing the relevant computations.
We consider the scenario of classical communication over a finite-dimensional quantum channel with memory using a separable-state input ensemble and local output measurements. We propose algorithms for estimating the information rate of such communication setups, along with algorithms for bounding the information rate based on so-called auxiliary channels. Some of the algorithms are extensions of their counterparts for (classical) finite-state-machine channels. Notably, we discuss suitable graphical models for doing the relevant computations. Moreover, the auxiliary channels are learned in a data-driven approach; i.e., only input/output sequences of the true channel are needed, but not the channel model of the true channel.
The maximum rates for information transmission through noisy quantum channels has primarily been developed for memoryless channels, where the noise on each transmitted state is treated as independent. Many real-world communication channels experience noise which is modeled better by errors that are correlated between separate channel uses. In this Brief Report, upper bounds on the classical information capacities of a class of quantum memory channels are derived. The class of channels consists of indecomposable quantum memory channels, a generalization of classical indecomposable finite-state channels.
We are interested in classical communication over a quantum channel with memory, in particular, we are interested in quantum-auxiliary-channel-based upper and lower bounds on the information rate. Toward improving these bounds, we propose efficient algorithms for optimizing the auxiliary channel. From a practical perspective, the lower bounds are of significant interest because they represent mismatched information rates, i.e., information rates that are achievable by a communication system where the decoder is matched to the auxiliary channel, instead of the original channel. Moreover, the auxiliary channels are learned in a data-driven approach, i.e., only input/output sequences of the true channel are needed, but not the channel model of the true channel.
We propose a framework to variationally obtain detectable capacity bounds for quantum channels. The proposal of this framework is motivated by the difficulty of estimating the von Neumann entropy of an unknown quantum state. Instead of estimating the von Neumann entropy at the channel output, we propose to estimate the state purity---which can be measured by a single measurement setting---followed by bounding the von Neumann entropy from above and below. This procedure leads to new upper and lower bounds on various communication rates of quantum channels for some fixed input states. Then, by utilizing the variational method to find optimal input states we obtain lower bounds on (i) the quantum capacity of arbitrary channels, (ii) the entanglement-assisted classical capacity of arbitrary channels, and (iii) the classical capacity of covariant channels. Corresponding to these lower bounds, we also obtain upper bounds on (i) N-shot coherent information, (ii) the entanglement-assisted classical capacity, and (iii) the N-shot Holevo capacity of arbitrary quantum channels. All these bounds can be estimated by a single measurement setting without needing a full process tomography or any further a priori knowledge, e.g., preferred basis of the channel.
We present a general model for quantum channels with memory and show that it is sufficiently general to encompass all causal automata: any quantum process in which outputs up to some time t do not depend on inputs at times ${t}^{\ensuremath{'}}>t$ can be decomposed into a concatenated memory channel. We then examine and present different physical setups in which channels with memory may be operated for the transfer of (private) classical and quantum information. These include setups in which either the receiver or a malicious third party have control of the initializing memory. We introduce classical and quantum channel capacities for these settings and give several examples to show that they may or may not coincide. Entropic upper bounds on the various channel capacities are given. For forgetful quantum channels, in which the effect of the initializing memory dies out as time increases, coding theorems are presented to show that these bounds may be saturated. Forgetful quantum channels are shown to be open and dense in the set of quantum memory channels.
How much memory is needed to retain the quantum speedup for collision finding? For a uniformly random function f:[N]→[N], the BHT algorithm finds a collision using O(N1/3) queries and a quantumly accessible classical table containing O(N1/3) input-output pairs, whereas a logarithmic-space Grover search uses O(N) queries. Determining the optimal query-space tradeoff between these extremes remains a major open problem.
We resolve this equation within the class of label-symmetric algorithms, which treat the function f's output labels as interchangeable. We prove that such algorithm that makes T queries, uses S qubits, and finds a collision in a uniformly random function f:[M]→[N] with constant probability satisfies T=Ω(N1/3)andT2S=Ω(NlogN). For the setting where M=N, these bounds are matched by a space-efficient implementation of the BHT algorithm. As a consequence of our tradeoff, any label-symmetric algorithm for the search version of Element Distinctness on f:[n]→[n2] must satisfy T=Ω(n2/3)andT2S=Ω(n2logn), matching Ambainis's quantum walk. Thus, both tradeoffs are optimal within the class of label-symmetric algorithms.
To prove these results, we develop a space-sensitive version of the compressed oracle technique. The compressed oracle records the information learned by the algorithm in an evolving superposition of databases. Using label symmetry and representation theory, we show that an algorithm using S qubits can effectively retain information about only O(S/logN) collision-free database entries. Substituting this estimate into the compressed oracle technique yields the stated tradeoffs.