results for au:Renes_J in:quant-ph

- We examine the task of privacy amplification from information-theoretic and coding-theoretic points of view. In the former, we give a one-shot characterization of the optimal rate of privacy amplification against classical adversaries in terms of the optimal type-II error in asymmetric hypothesis testing. This formulation can be easily computed to give finite-blocklength bounds and turns out to be equivalent to smooth min-entropy bounds by Renner and Wolf [Asiacrypt 2005] and Watanabe and Hayashi [ISIT 2013], as well as a bound in terms of the $E_\gamma$ divergence by Yang, Schaefer, and Poor [arXiv:1706.03866 [cs.IT]]. In the latter, we show that protocols for privacy amplification based on linear codes can be easily repurposed for channel simulation. Combined with known relations between channel simulation and lossy source coding, this implies that privacy amplification can be understood as a basic primitive for both channel simulation and lossy compression. Applied to symmetric channels or lossy compression settings, our construction leads to proto- cols of optimal rate in the asymptotic i.i.d. limit. Finally, appealing to the notion of channel duality recently detailed by us in [IEEE Trans. Info. Theory 64, 577 (2018)], we show that linear error-correcting codes for symmetric channels with quantum output can be transformed into linear lossy source coding schemes for classical variables arising from the dual channel. This explains a "curious duality" in these problems for the (self-dual) erasure channel observed by Martinian and Yedidia [Allerton 2003; arXiv:cs/0408008] and partly anticipates recent results on optimal lossy compression by polar and low-density generator matrix codes.
- We extend the recent bounds of Sason and Verdú relating Rényi entropy and Bayesian hypothesis testing [arXiv:1701.01974] to the quantum domain and show that they have a number of different applications. First, we obtain a sharper bound relating the optimal probability of correctly distinguishing elements of an ensemble of states to that of the pretty good measurement, and an analogous bound for optimal and pretty good entanglement recovery. Second, we obtain bounds relating optimal guessing and entanglement recovery to the fidelity of the state with a product state, which then leads to tight tripartite uncertainty and monogamy relations.
- Apr 21 2017 quant-ph arXiv:1704.05857v1We construct two simple error correction schemes adapted to amplitude damping noise for Bacon-Shor codes and investigate their prospects for fault-tolerant implementation. Both consist solely of Clifford gates and require far fewer qubits, relative to the standard method, to achieve correction to a desired order in the damping rate. The first, employing one-bit teleportation and single-qubit measurements, needs only one fourth as many physical qubits, while the second, using just stabilizer measurements and Pauli corrections, needs only half. We show that existing fault-tolerance methods can be employed for the latter, while the former can be made to avoid potential catastrophic errors and can easily cope with damping faults in ancilla qubits.
- For any given channel $W$ with classical inputs and possibly quantum outputs, a dual classical-input channel $W^\perp$ can be defined by embedding the original into a channel $\mathcal N$ with quantum inputs and outputs. Here we give new uncertainty relations for a general class of entropies that lead to very close relationships between the original channel and its dual. Moreover, we show that channel duality can be combined with duality of linear codes, whereupon the uncertainty relations imply that the performance of a given code over a given channel is entirely characterized by the performance of the dual code on the dual channel. This has several applications. In the context of polar codes, it implies that the rates of polarization to ideal and useless channels must be identical. Duality also relates the tasks of channel coding and privacy amplification, implying that the finite blocklength performance of extractors and codes is precisely linked, and that optimal rate extractors can be transformed into capacity-achieving codes, and vice versa. Finally, duality also extends to the EXIT function of any channel and code. Here it implies that for any channel family, if the EXIT function for a fixed code has a sharp transition, then it must be such that the rate of the code equals the capacity at the transition. This may give a different route to proving a code family achieves capacity by establishing sharp EXIT function transitions.
- We prove polarization theorems for arbitrary classical-quantum (cq) channels. The input alphabet is endowed with an arbitrary Abelian group operation and an Arıkan-style transformation is applied using this operation. It is shown that as the number of polarization steps becomes large, the synthetic cq-channels polarize to deterministic homomorphism channels which project their input to a quotient group of the input alphabet. This result is used to construct polar codes for arbitrary cq-channels and arbitrary classical-quantum multiple access channels (cq-MAC). The encoder can be implemented in $O(N\log N)$ operations, where $N$ is the blocklength of the code. A quantum successive cancellation decoder for the constructed codes is proposed. It is shown that the probability of error of this decoder decays faster than $2^{-N^{\beta}}$ for any $\beta<\frac{1}{2}$.
- The notions of error and disturbance appearing in quantum uncertainty relations are often quantified by the discrepancy of a physical quantity from its ideal value. However, these real and ideal values are not the outcomes of simultaneous measurements, and comparing the values of unmeasured observables is not necessarily meaningful according to quantum theory. To overcome these conceptual difficulties, we take a different approach and define error and disturbance in an operational manner. In particular, we formulate both in terms of the probability that one can successfully distinguish the actual measurement device from the relevant hypothetical ideal by any experimental test whatsoever. This definition itself does not rely on the formalism of quantum theory, avoiding many of the conceptual difficulties of usual definitions. We then derive new Heisenberg-type uncertainty relations for both joint measurability and the error-disturbance tradeoff for arbitrary observables of finite-dimensional systems, as well as for the case of position and momentum. Our relations may be directly applied in information processing settings, for example to infer that devices which can faithfully transmit information regarding one observable do not leak any information about conjugate observables to the environment. We also show that Englert's wave-particle duality relation [PRL 77, 2154 (1996)] can be viewed as an error-disturbance uncertainty relation.
- Quantum generalizations of Renyi's entropies are a useful tool to describe a variety of operational tasks in quantum information processing. Two families of such generalizations turn out to be particularly useful: the Petz quantum Renyi divergence $\bar{D}_{\alpha}$ and the minimal quantum Renyi divergence $\tilde{D}_{\alpha}$. In this paper, we prove a reverse Araki-Lieb-Thirring inequality that implies a new relation between these two families of divergences, namely that $\alpha \bar{D}_{\alpha}(\rho \| \sigma) \leq \tilde{D}_{\alpha}(\rho \| \sigma)$ for $\alpha \in [0,1]$ and where $\rho$ and $\sigma$ are density operators. This bound suggests defining a "pretty good fidelity", whose relation to the usual fidelity implies the known relations between the optimal and pretty good measurement as well as the optimal and pretty good singlet fraction. We also find a new necessary and sufficient condition for optimality of the pretty good measurement and singlet fraction.
- Belief propagation is a powerful tool in statistical physics, machine learning, and modern coding theory. As a decoding method, it is ubiquitous in classical error correction and has also been applied to stabilizer-based quantum error correction. The algorithm works by passing messages between nodes of the factor graph associated with the code and enables efficient decoding, in some cases even up to the Shannon capacity of the channel. Here we construct a belief propagation algorithm which passes quantum messages on the factor graph and is capable of decoding the classical-quantum channel with pure state outputs. This gives explicit decoding circuits whose number of gates is quadratic in the blocklength of the code. We also show that this decoder can be modified to work with polar codes for the pure state channel and as part of a polar decoder for transmitting quantum information over the amplitude damping channel. These represent the first explicit capacity-achieving decoders for non-Pauli channels.
- May 06 2016 quant-ph arXiv:1605.01420v2The uncertainty principle can be understood as constraining the probability of winning a game in which Alice measures one of two conjugate observables, such as position or momentum, on a system provided by Bob, and he is to guess the outcome. Two variants are possible: either Alice tells Bob which observable she measured, or he has to furnish guesses for both cases. Here I derive new uncertainty relations for both, formulated directly in terms of Bob's guessing probabilities. For the former these relate to the entanglement that can be recovered by action on Bob's system alone. This gives a condition for approximate quantum error correction in terms of the recoverability of "amplitude" and "phase" information, implicitly used in the recent construction of efficient quantum polar codes. I also find a tight relation on the guessing probabilities for the latter game, which has application to wave-particle duality relations.
- Optical communication channels are ultimately quantum-mechanical in nature, and we must therefore look beyond classical information theory to determine their communication capacity as well as to find efficient encoding and decoding schemes of the highest rates. Thermal channels, which arise from linear coupling of the field to a thermal environment, are of particular practical relevance; their classical capacity has been recently established, but their quantum capacity remains unknown. While the capacity sets the ultimate limit on reliable communication rates, it does not promise that such rates are achievable by practical means. Here we construct efficiently encodable codes for thermal channels which achieve the classical capacity and the so-called Gaussian coherent information for transmission of classical and quantum information, respectively. Our codes are based on combining polar codes with a discretization of the channel input into a finite "constellation" of coherent states. Encoding of classical information can be done using linear optics.
- We introduce and study a generalization of majorization called relative submajorization and show that it has many applications to the resource theories of thermodynamics, bipartite entanglement, and quantum coherence. In particular, we show that relative submajorization characterizes both the probability and approximation error that can be obtained when transforming one resource to another, also when assisted by additional standard resources such as useful work or maximally-entangled states. These characterizations have a geometric formulation as the ratios or differences, respectively, between the Lorenz curves associated with the input and output resources. We also find several interesting bounds on the reversibility of a given transformation in terms of the properties of the forward transformation. The main technical tool used to establish these results is linear programming duality.
- We prove a one-shot "minimax" converse bound for quantum channel coding assisted by positive partial transpose channels between sender and receiver. The bound is similar in spirit to the converse by Polyanskiy, Poor, and Verdu [IEEE Trans. Info. Theory 56, 2307-2359 (2010)] for classical channel coding, and also enjoys the saddle point property enabling the order of optimizations to be interchanged. Equivalently, the bound can be formulated as a semidefinite program satisfying strong duality. The convex nature of the bound implies channel symmetries can substantially simplify the optimization, enabling us to explicitly compute the finite blocklength behavior for several simple qubit channels. In particular, we find that finite blocklength converse statements for the classical erasure channel apply to the assisted quantum erasure channel, while bounds for the classical binary symmetric channel apply to both the assisted dephasing and depolarizing channels. This implies that these qubit channels inherit statements regarding the asymptotic limit of large blocklength, such as the strong converse or second-order converse rates, from their classical counterparts. Moreover, for the dephasing channel, the finite blocklength bounds are as tight as those for the classical binary symmetric channel, since coding for classical phase errors yields equivalently-performing unassisted quantum codes.
- The quantum capacity of a memoryless channel is often used as a single figure of merit to characterize its ability to transmit quantum information coherently. The capacity determines the maximal rate at which we can code reliably over asymptotically many uses of the channel. We argue that this asymptotic treatment is insufficient to the point of being irrelevant in the quantum setting where decoherence severely limits our ability to manipulate large quantum systems in the encoder and decoder. For all practical purposes we should instead focus on the trade-off between three parameters: the rate of the code, the number of coherent uses of the channel, and the fidelity of the transmission. The aim is then to specify the region determined by allowed combinations of these parameters. Towards this goal, we find approximate and exact characterizations of the region of allowed triplets for the qubit dephasing channel and for the erasure channel with classical post-processing assistance. In each case the region is parametrized by a second channel parameter, the quantum channel dispersion. In the process we also develop several general inner (achievable) and outer (converse) bounds on the coding region that are valid for all finite-dimensional quantum channels and can be computed efficiently. Applied to the depolarizing channel, this allows us to determine a lower bound on the number of coherent uses of the channel necessary to witness super-additivity of the coherent information.
- Arıkan's polar coding technique is based on the idea of synthesizing $n$ channels from the $n$ instances of the physical channel by a simple linear encoding transformation. Each synthesized channel corresponds to a particular input to the encoder. For large $n$, the synthesized channels become either essentially noiseless or almost perfectly noisy, but in total carry as much information as the original $n$ channels. Capacity can therefore be achieved by transmitting messages over the essentially noiseless synthesized channels. Unfortunately, the set of inputs corresponding to reliable synthesized channels is poorly understood, in particular how the set depends on the underlying physical channel. In this work, we present two analytic conditions sufficient to determine if the reliable inputs corresponding to different discrete memoryless channels are aligned or not, i.e. if one set is contained in the other. Understanding the alignment of the polarized sets is important as it is directly related to universality properties of the induced polar codes, which are essential in particular for network coding problems. We demonstrate the performance of our conditions on a few examples for wiretap and broadcast channels. Finally we show that these conditions imply that the simple quantum polar coding scheme of Renes et al. [Phys. Rev. Lett. 109, 050504 (2012)] requires entanglement assistance for general channels, but also show such assistance to be unnecessary in many cases of interest.
- Sep 16 2014 quant-ph cond-mat.stat-mech arXiv:1409.3998v2Thermodynamics has recently been extended to small scales with resource theories that model heat exchanges. Real physical systems exchange diverse quantities: heat, particles, angular momentum, etc. We generalize thermodynamic resource theories to exchanges of observables other than heat, to baths other than heat baths, and to free energies other than the Helmholtz free energy. These generalizations are illustrated with "grand-potential" theories that model movements of heat and particles. Free operations include unitaries that conserve energy and particle number. From this conservation law and from resource-theory principles, the grand-canonical form of the free states is derived. States are shown to form a quasiorder characterized by free operations, d-majorization, the hypothesis-testing entropy, and rescaled Lorenz curves. We calculate the work distillable from, and we bound the work cost of creating, a state. These work quantities can differ but converge to the grand potential in the thermodynamic limit. Extending thermodynamic resource theories beyond heat baths, we open diverse realistic systems to modeling with one-shot statistical mechanics. Prospective applications such as electrochemical batteries are hoped to bridge one-shot theory to experiments.
- A pure-loss bosonic channel is a simple model for communication over free-space or fiber-optic links. More generally, phase-insensitive bosonic channels model other kinds of noise, such as thermalizing or amplifying processes. Recent work has established the classical capacity of all of these channels, and furthermore, it is now known that a strong converse theorem holds for the classical capacity of these channels under a particular photon number constraint. The goal of the present paper is to initiate the study of second-order coding rates for these channels, by beginning with the simplest one, the pure-loss bosonic channel. In a second-order analysis of communication, one fixes the tolerable error probability and seeks to understand the back-off from capacity for a sufficiently large yet finite number of channel uses. We find a lower bound on the maximum achievable code size for the pure-loss bosonic channel, in terms of the known expression for its capacity and a quantity called channel dispersion. We accomplish this by proving a general "one-shot" coding theorem for channels with classical inputs and pure-state quantum outputs which reside in a separable Hilbert space. The theorem leads to an optimal second-order characterization when the channel output is finite-dimensional, and it remains an open question to determine whether the characterization is optimal for the pure-loss bosonic channel.
- Physical implementations of cryptographic algorithms leak information, which makes them vulnerable to so-called side-channel attacks. The problem of secure computation in the presence of leakage is generally known as leakage resilience. In this work, we establish a connection between leakage resilience and fault-tolerant quantum computation. We first prove that for a general leakage model, there exists a corresponding noise model in which fault tolerance implies leakage resilience. Then we show how to use constructions for fault-tolerant quantum computation to implement classical circuits that are secure in specific leakage models.
- We derive new Heisenberg-type uncertainty relations for both joint measurability and the error-disturbance tradeoff for arbitrary observables of finite-dimensional systems. The relations are formulated in terms of a directly operational quantity, namely the probability of distinguishing the actual operation of a device from its hypothetical ideal, by any possible testing procedure whatsoever. Moreover, they may be directly applied in information processing settings, for example to infer that devices which can faithfully transmit information regarding one observable do not leak any information about conjugate observables to the environment. Though intuitively apparent from Heisenberg's original arguments, only more limited versions of this statement have previously been formalized.
- Adopting a resource theory framework of thermodynamics for quantum and nano systems pioneered by Janzing et al. [Int. J. Th. Phys. 39, 2717 (2000)], we formulate the cost in useful work of transforming one resource state into another as a linear program of convex optimization. This approach is based on the characterization of thermal quasiorder given by Janzing et al. and later by Horodecki and Oppenheim [Nat. Comm. 4, 2059 (2013)]. Both characterizations are related to an extended version of majorization studied by Ruch, Schranner, and Seligman under the name mixing distance [J. Chem. Phys. 69, 386 (1978)].
- The laws of quantum mechanics place fundamental limits on the accuracy of measurements and therefore on the estimation of unknown parameters of a quantum system. In this work, we prove lower bounds on the size of confidence regions reported by any region estimator for a given ensemble of probe states and probability of success. Our bounds are derived from a previously unnoticed connection between the size of confidence regions and the error probabilities of a corresponding binary hypothesis test. In group-covariant scenarios, we find that there is an ultimate bound for any estimation scheme which depends only on the representation-theoretic data of the probe system, and we evaluate its asymptotics in the limit of many systems, establishing a general "Heisenberg limit" for region estimation. We apply our results to several examples, in particular to phase estimation, where our bounds allow us to recover the well-known Heisenberg and shot-noise scaling.
- Jul 04 2013 quant-ph arXiv:1307.1136v3We construct an explicit quantum coding scheme which achieves a communication rate not less than the coherent information when used to transmit quantum information over a noisy quantum channel. For Pauli and erasure channels we also present efficient encoding and decoding algorithms for this communication scheme based on polar codes (essentially linear in the blocklength), but which do not require the sender and receiver to share any entanglement before the protocol begins. Due to the existence of degeneracies in the involved error-correcting codes it is indeed possible that the rate of the scheme exceeds the coherent information. We provide a simple criterion which indicates such performance. Finally we discuss how the scheme can be used for secret key distillation as well as private channel coding.
- We provide a framework for one-shot quantum rate distortion coding, in which the goal is to determine the minimum number of qubits required to compress quantum information as a function of the probability that the distortion incurred upon decompression exceeds some specified level. We obtain a one-shot characterization of the minimum qubit compression size for an entanglement-assisted quantum rate-distortion code in terms of the smooth max-information, a quantity previously employed in the one-shot quantum reverse Shannon theorem. Next, we show how this characterization converges to the known expression for the entanglement-assisted quantum rate distortion function for asymptotically many copies of a memoryless quantum information source. Finally, we give a tight, finite blocklength characterization for the entanglement-assisted minimum qubit compression size of a memoryless isotropic qubit source subject to an average symbol-wise distortion constraint.
- We show that quantum-to-classical channels, i.e., quantum measurements, can be asymptotically simulated by an amount of classical communication equal to the quantum mutual information of the measurement, if sufficient shared randomness is available. This result generalizes Winter's measurement compression theorem for fixed independent and identically distributed inputs [Winter, CMP 244 (157), 2004] to arbitrary inputs, and more importantly, it identifies the quantum mutual information of a measurement as the information gained by performing it, independent of the input state on which it is performed. Our result is a generalization of the classical reverse Shannon theorem to quantum-to-classical channels. In this sense, it can be seen as a quantum reverse Shannon theorem for quantum-to-classical channels, but with the entanglement assistance and quantum communication replaced by shared randomness and classical communication, respectively. The proof is based on a novel one-shot state merging protocol for "classically coherent states" as well as the post-selection technique for quantum channels, and it uses techniques developed for the quantum reverse Shannon theorem [Berta et al., CMP 306 (579), 2011].
- Dec 12 2012 quant-ph arXiv:1212.2379v1The overarching goal of this thesis is to demonstrate that complementarity is at the heart of quantum information theory, that it allows us to make (some) sense of just what information "quantum information" refers to, and that it is useful in understanding and constructing quantum information processing protocols. The detailed research results which form the basis of these claims are to be found in the included papers, and the aim here is to present an overview comprehensible to a more general audience.
- We construct new polar coding schemes for the transmission of quantum or private classical information over arbitrary quantum channels. In the former case, our coding scheme achieves the symmetric coherent information and in the latter the symmetric private information. Both schemes are built from a polar coding construction capable of transmitting classical information over a quantum channel [Wilde and Guha, IEEE Transactions on Information Theory, in press]. Appropriately merging two such classical-quantum schemes, one for transmitting "amplitude" information and the other for transmitting "phase," leads to the new private and quantum coding schemes, similar to the construction for Pauli and erasure channels in [Renes, Dupuis, and Renner, Physical Review Letters 109, 050504 (2012)]. The encoding is entirely similar to the classical case, and thus efficient. The decoding can also be performed by successive cancellation, as in the classical case, but no efficient successive cancellation scheme is yet known for arbitrary quantum channels. An efficient code construction is unfortunately still unknown. Generally, our two coding schemes require entanglement or secret-key assistance, respectively, but we extend two known conditions under which the needed assistance rate vanishes. Finally, although our results are formulated for qubit channels, we show how the scheme can be extended to multiple qubits. This then demonstrates a near-explicit coding method for realizing one of the most striking phenomena in quantum information theory: the superactivation effect, whereby two quantum channels which individually have zero quantum capacity can have a non-zero quantum capacity when used together.
- Nov 15 2012 quant-ph arXiv:1211.3141v2We study an entropy measure for quantum systems that generalizes the von Neumann entropy as well as its classical counterpart, the Gibbs or Shannon entropy. The entropy measure is based on hypothesis testing and has an elegant formulation as a semidefinite program, a type of convex optimization. After establishing a few basic properties, we prove upper and lower bounds in terms of the smooth entropies, a family of entropy measures that is used to characterize a wide range of operational quantities. From the formulation as a semidefinite program, we also prove a result on decomposition of hypothesis tests, which leads to a chain rule for the entropy.
- We construct a new secret-key assisted polar coding scheme for private classical communication over a quantum or classical wiretap channel. The security of our scheme rests on an entropic uncertainty relation, in addition to the channel polarization effect. Our scheme achieves the symmetric private information rate by synthesizing "amplitude" and "phase" channels from an arbitrary quantum wiretap channel. We find that the secret-key consumption rate of the scheme vanishes for an arbitrary degradable quantum wiretap channel. Furthermore, we provide an additional sufficient condition for when the secret key rate vanishes, and we suspect that satisfying this condition implies that the scheme requires no secret key at all. Thus, this latter condition addresses an open question from the Mahdavifar-Vardy scheme for polar coding over a classical wiretap channel.
- We construct a new entanglement-assisted quantum polar coding scheme which achieves the symmetric coherent information rate by synthesizing "amplitude" and "phase" channels from a given, arbitrary quantum channel. We first demonstrate the coding scheme for arbitrary quantum channels with qubit inputs, and we show that quantum data can be reliably decoded by O(N) rounds of coherent quantum successive cancellation, followed by N controlled-NOT gates (where N is the number of channel uses). We also find that the entanglement consumption rate of the code vanishes for degradable quantum channels. Finally, we extend the coding scheme to channels with multiple qubit inputs. This gives a near-explicit method for realizing one of the most striking phenomena in quantum information theory: the superactivation effect, whereby two quantum channels which individually have zero quantum capacity can have a non-zero quantum capacity when used together.
- Nov 17 2011 quant-ph arXiv:1111.3882v3The ideas of thermodynamics have proved fruitful in the setting of quantum information theory, in particular the notion that when the allowed transformations of a system are restricted, certain states of the system become useful resources with which one can prepare previously inaccessible states. The theory of entanglement is perhaps the best-known and most well-understood resource theory in this sense. Here we return to the basic questions of thermodynamics using the formalism of resource theories developed in quantum information theory and show that the free energy of thermodynamics emerges naturally from the resource theory of energy-preserving transformations. Specifically, the free energy quantifies the amount of useful work which can be extracted from asymptotically-many copies of a quantum system when using only reversible energy-preserving transformations and a thermal bath at fixed temperature. The free energy also quantifies the rate at which resource states can be reversibly interconverted asymptotically, provided that a sublinear amount of coherent superposition over energy levels is available, a situation analogous to the sublinear amount of classical communication required for entanglement dilution.
- Polar coding, introduced 2008 by Arikan, is the first (very) efficiently encodable and decodable coding scheme whose information transmission rate provably achieves the Shannon bound for classical discrete memoryless channels in the asymptotic limit of large block sizes. Here we study the use of polar codes for the transmission of quantum information. Focusing on the case of qubit Pauli channels and qubit erasure channels, we use classical polar codes to construct a coding scheme which, using some pre-shared entanglement, asymptotically achieves a net transmission rate equal to the coherent information using efficient encoding and decoding operations and code construction. Furthermore, for channels with sufficiently low noise level, we demonstrate that the rate of preshared entanglement required is zero.
- While solid-state devices offer naturally reliable hardware for modern classical computers, thus far quantum information processors resemble vacuum tube computers in being neither reliable nor scalable. Strongly correlated many body states stabilized in topologically ordered matter offer the possibility of naturally fault tolerant computing, but are both challenging to engineer and coherently control and cannot be easily adapted to different physical platforms. We propose an architecture which achieves some of the robustness properties of topological models but with a drastically simpler construction. Quantum information is stored in the symmetry-protected degenerate ground states of spin-1 chains, while quantum gates are performed by adiabatic non-Abelian holonomies using only single-site fields and nearest-neighbor couplings. Gate operations respect the symmetry, and so inherit some protection from noise and disorder from the symmetry-protected ground states.
- We show that optimal protocols for noisy channel coding of public or private information over either classical or quantum channels can be directly constructed from two more primitive information-theoretic tools: privacy amplification and information reconciliation, also known as data compression with side information. We do this in the one-shot scenario of structureless resources, and formulate our results in terms of the smooth min- and max-entropy. In the context of classical information theory, this shows that essentially all two-terminal protocols can be reduced to these two primitives, which are in turn governed by the smooth min- and max-entropies, respectively. In the context of quantum information theory, the recently-established duality of these two protocols means essentially all two-terminal protocols can be constructed using just a single primitive.
- Aug 04 2010 quant-ph arXiv:1008.0452v3The task of compressing classical information in the one-shot scenario is studied in the setting where the decompressor additionally has access to some given quantum side information. In this hybrid classical-quantum version of the famous Slepian-Wolf problem, the smooth max-entropy is found to govern the number of bits into which classical information can be compressed so that it can be reliably recovered from the compressed version and quantum side information. Combining this result with known results on privacy amplification then yields bounds on the amount of common randomness and secret key that can be recovered in one-shot from hybrid classical-quantum systems using one-way classical communication.
- Apr 28 2010 quant-ph cond-mat.str-el arXiv:1004.4906v3Single-spin measurements on the ground state of an interacting spin lattice can be used to perform a quantum computation. We show how such measurements can mimic renormalization group transformations and remove the short-ranged variations of the state that can reduce the fidelity of a computation. This suggests that the quantum computational ability of a spin lattice could be a robust property of a quantum phase. We illustrate our idea with the ground state of a spin-1 chain, which can serve as a quantum computational wire not only at the Affleck-Kennedy-Lieb-Tasaki point, but within the rotationally-invariant Haldane phase.
- Mar 06 2010 quant-ph arXiv:1003.1150v3The breakthrough of quantum error correction brought with it the picture of quantum information as a sort of combination of two complementary types of classical information, "amplitude" and "phase". Here I show how this intuition can be used to construct two new conditions for approximate quantum error correction. The first states that entanglement is locally recoverable from a bipartite state when one system can be used to approximately predict the outcomes of two complementary observables on the other. The second, more in the spirit of the recent decoupling approach, states that entanglement is locally recoverable when the environment cannot reliably predict either.
- Mar 04 2010 quant-ph arXiv:1003.0703v2We show that the tasks of privacy amplification against quantum adversaries and data compression with quantum side information are dual in the sense that the ability to perform one implies the ability to perform the other. These are two of the most important primitives in classical information theory, and are shown to be connected by complementarity and the uncertainty principle in the quantum setting. Applications include a new uncertainty principle formulated in terms of smooth min- and max-entropies, as well as new conditions for approximate quantum error correction.
- Sep 08 2009 quant-ph arXiv:0909.0950v4The uncertainty principle, originally formulated by Heisenberg, dramatically illustrates the difference between classical and quantum mechanics. The principle bounds the uncertainties about the outcomes of two incompatible measurements, such as position and momentum, on a particle. It implies that one cannot predict the outcomes for both possible choices of measurement to arbitrary precision, even if information about the preparation of the particle is available in a classical memory. However, if the particle is prepared entangled with a quantum memory, a device which is likely to soon be available, it is possible to predict the outcomes for both measurement choices precisely. In this work we strengthen the uncertainty principle to incorporate this case, providing a lower bound on the uncertainties which depends on the amount of entanglement between the particle and the quantum memory. We detail the application of our result to witnessing entanglement and to quantum key distribution.
- May 11 2009 quant-ph arXiv:0905.1324v1We construct an optimal state merging protocol by adapting a recently-discovered optimal entanglement distillation protcol [Renes and Boileau, Phys. Rev. A . 73, 032335 (2008)]. The proof of optimality relies only on directly establishing sufficient "amplitude" and "phase" correlations between Alice and Bob and not on usual techniques of decoupling Alice from the environment. This strengthens the intuition from quantum error-correction that these two correlations are all that really matter in two-party quantum information processing.
- Dec 19 2008 quant-ph arXiv:0812.3607v2We introduce symmetric extensions of bipartite quantum states as a tool for analyzing protocols that distill secret key from quantum correlations. Whether the correlations are coming from a prepare-and-measure quantum key distribution scheme or from an entanglement-based scheme, the protocol has to produce effective states without a symmetric extension in order to succeed. By formulating the symmetric extension problem as a semidefinite program, we solve the problem for Bell-diagonal states. Applying this result to the six-state and BB84 schemes, we show that for the entangled states that cannot be distilled by current key distillation procedures, the failure can be understood in terms of a failure to break a symmetric extension.
- Jun 25 2008 quant-ph arXiv:0806.3984v2We conjecture a new entropic uncertainty principle governing the entropy of complementary observations made on a system given side information in the form of quantum states, generalizing the entropic uncertainty relation of Maassen and Uffink [Phys. Rev. Lett. 60, 1103 (1988)]. We prove a special case for certain conjugate observables by adapting a similar result found by Christandl and Winter pertaining to quantum channels [IEEE Trans. Inf. Theory 51, 3159 (2005)], and discuss possible applications of this result to the decoupling of quantum systems and for security analysis in quantum cryptography.
- Mar 22 2008 quant-ph arXiv:0803.3096v2One of the remarkable features of quantum mechanics is the ability to ensure secrecy. Private states embody this effect, as they are precisely those multipartite quantum states from which two parties can produce a shared secret that cannot in any circumstance be correlated to an external system. Naturally, these play an important role in quantum key distribution (QKD) and quantum information theory. However, a general distillation method has heretofore been missing. Inspired by Koashi's complementary control scenario (arXiv:0704.3661v1 [quant-ph]), we give a new definition of private states in terms of one party's potential knowledge of two complementary measurements made on the other and use this to construct a general method of private state distillation using quantum error-correcting codes. The procedure achieves the same key rate as recent, more information-theoretic approaches while demonstrating the physical principles underlying privacy of the key. Additionally, the same approach can be used to establish the hashing inequality for entanglement distillation, as well as the direct quantum coding theorem.
- Dec 11 2007 quant-ph arXiv:0712.1494v2We study the advantages to be gained in quantum key distribution (QKD) protocols by combining the techniques of local randomization, or noisy preprocessing, and structured (nonrandom) block codes. Extending the results of [Smith, Renes, and Smolin, quant-ph/0607018] pertaining to BB84, we improve the best-known lower bound on the error rate for the 6-state protocol from 14.11% for local randomization alone to at least 14.59%. Additionally, we also study the effects of iterating the combined preprocessing scheme and find further improvements to the BB84 protocol already at small block lengths.
- Feb 21 2007 quant-ph arXiv:quant-ph/0702187v1We show that three principle means of treating privacy amplification in quantum key distribution, private state distillation, classical privacy amplification, and via the uncertainty principle, are equivalent and interchangeable. By adapting the security proof based on the uncertainty principle, we construct a new protocol for private state distillation which we prove is identical to standard classical privacy amplification. Underlying this approach is a new characterization of private states, related to their standard formulation by the uncertainty principle, which gives a more physical understanding of security in quantum key distribution.
- Jul 04 2006 quant-ph arXiv:quant-ph/0607018v2A central goal in information theory and cryptography is finding simple characterizations of optimal communication rates subject to various restrictions and security requirements. Ideally, the optimal key rate for a quantum key distribution (QKD) protocol would be given by \em single-letter formula involving a simple optimization over a single use of an effective channel. We explore the possibility of such a formula for one of the simplest and most widely used QKD protocols--Bennett-Brassard-84 (BB84) with one way classical post-processing. We show that a conjectured single-letter key-rate formula is false, uncovering a deep ignorance about asymptotically good private codes and pointing towards unfortunate complications in the theory of QKD. These complications are not without benefit--with added complexity comes better key rates than previously thought possible. We improve the threshold for secure key generation from a bit error rate of 0.124 to 0.129.
- Mar 30 2006 quant-ph arXiv:quant-ph/0603262v2We provide a simple security proof for prepare & measure quantum key distribution protocols employing noisy processing and one-way postprocessing of the key. This is achieved by showing that the security of such a protocol is equivalent to that of an associated key distribution protocol in which, instead of the usual maximally-entangled states, a more general \em private state is distilled. Besides a more general target state, the usual entanglement distillation tools are employed (in particular, Calderbank-Shor-Steane (CSS)-like codes), with the crucial difference that noisy processing allows some phase errors to be left uncorrected without compromising the privacy of the key.
- Jul 13 2005 quant-ph arXiv:quant-ph/0507108v1Let Alice and Bob be able to make local quantum measurements and communicate classically. The set of mathematically consistent joint probability assignments (``states'') for such measurements is properly larger than the set of quantum-mechanical mixed states for the Alice-Bob system. It is canonically isomorphic to the set of positive (not necessarily completely positive) linear maps Phi from the bounded linear operators on Alice's space to those on Bob's, for which Tr Phi(I)=1. We review the fact that allowing classical communication is equivalent to enforcing ``no-instantaneous-signalling'' (``no--influence'') in the direction opposite the communication. We establish that in the subclass of ``decomposable'' states, i.e. convex combinations of positive states with "PTP" ones whose partial transpose is positive, the extremal states are just the extremal positive and extremal PTP states. We show that two such states, shared by the same pair of parties, cannot necessarily be combined as independent states (their tensor product) if the full set of quantum operations is allowed locally to each party. We use a framework of ``test spaces'' and states on these, suited for exhibiting the analogies and deviations of empirical probabilistic theories from classical probability theory. This leads to a deeper understanding of analogies between quantum mechanics and Bayesian probability theory. The existence of a ``most Bayesian'' quantum rule for updating states after measurement, and its association with the situation when information on one system is gained by measuring another, is a case of a general proposition holding for test spaces combined subject to the no-signalling requirement.
- Generalized decoding, effective channels, and simplified security proofs in quantum key distributionMay 10 2005 quant-ph arXiv:quant-ph/0505061v3Prepare and measure quantum key distribution protocols can be decomposed into two basic steps: delivery of the signals over a quantum channel and distillation of a secret key from the signal and measurement records by classical processing and public communication. Here we formalize the distillation process for a general protocol in a purely quantum-mechanical framework and demonstrate that it can be viewed as creating an ``effective'' quantum channel between the legitimate users Alice and Bob. The process of secret key generation can then be viewed as entanglement distribution using this channel, which enables application of entanglement-based security proofs to essentially any prepare and measure protocol. To ensure secrecy of the key, Alice and Bob must be able to estimate the channel noise from errors in the key, and we further show how symmetries of the distillation process simplify this task. Applying this method, we prove the security of several key distribution protocols based on equiangular spherical codes.
- Sep 09 2004 quant-ph arXiv:quant-ph/0409043v1Quantum key distribution protocols based on equiangular spherical codes are introduced and their behavior under the intercept/resend attack investigated. Such protocols offer a greater range of secure noise tolerance and speed options than protocols based on their cousins, the mutually-unbiased bases, while also enabling the determination of the channel noise rate without the need to sacrifice key bits. For fixed number of signal states in a given dimension, the spherical code protocols offer Alice and Bob more noise tolerance at the price of slower key generation rates.
- Aug 16 2004 quant-ph arXiv:quant-ph/0408085v4Quantum key distribution (QKD) protocols are cryptographic techniques with security based only on the laws of quantum mechanics. Two prominent QKD schemes are the BB84 and B92 protocols that use four and two quantum states, respectively. In 2000, Phoenix et al. proposed a new family of three state protocols that offers advantages over the previous schemes. Until now, an error rate threshold for security of the symmetric trine spherical code QKD protocol has only been shown for the trivial intercept/resend eavesdropping strategy. In this paper, we prove the unconditional security of the trine spherical code QKD protocol, demonstrating its security up to a bit error rate of 9.81%. We also discuss on how this proof applies to a version of the trine spherical code QKD protocol where the error rate is evaluated from the number of inconclusive events.
- Feb 20 2004 quant-ph arXiv:quant-ph/0402135v3Recently spherical codes were introduced as potentially more capable ensembles for quantum key distribution. Here we develop specific key creation protocols for the two qubit-based spherical codes, the trine and tetrahedron, and analyze them in the context of a suitably-tailored intercept/resend attack, both in standard form, and a ``gentler'' version whose back-action on the quantum state is weaker. When compared to the standard unbiased basis protocols, BB84 and six-state, two distinct advantages are found. First, they offer improved tolerance of eavesdropping, the trine besting its counterpart BB84 and the tetrahedron the six-state protocol. Second, the key error rate may be computed from the sift rate of the protocol itself, removing the need to sacrifice key bits for this purpose. This simplifies the protocol and improves the overall key rate.
- Nov 18 2003 quant-ph arXiv:quant-ph/0311106v2Mutually unbiased bases have been extensively studied in the literature and are simple and effective in quantum key distribution protocols, but they are not optimal. Here equiangular spherical codes are introduced as a more efficient and robust resource for key distribution. Such codes are sets of states that are as evenly spaced throughout the vector space as possible. In the case the two parties use qubits and face the intercept/resend eavesdropping strategy, they can make use of three equally-spaced states, called a \emphtrine, to outperform the original four-state BB84 protocol in both speed and reliability. This points toward the optimality of spherical codes in arbitrary dimensions.
- We consider the existence in arbitrary finite dimensions d of a POVM comprised of d^2 rank-one operators all of whose operator inner products are equal. Such a set is called a ``symmetric, informationally complete'' POVM (SIC-POVM) and is equivalent to a set of d^2 equiangular lines in C^d. SIC-POVMs are relevant for quantum state tomography, quantum cryptography, and foundational issues in quantum mechanics. We construct SIC-POVMs in dimensions two, three, and four. We further conjecture that a particular kind of group-covariant SIC-POVM exists in arbitrary dimensions, providing numerical results up to dimension 45 to bolster this claim.
- Jun 27 2003 quant-ph arXiv:quant-ph/0306179v1We prove a Gleason-type theorem for the quantum probability rule using frame functions defined on positive-operator-valued measures (POVMs), as opposed to the restricted class of orthogonal projection-valued measures used in the original theorem. The advantage of this method is that it works for two-dimensional quantum systems (qubits) and even for vector spaces over rational fields--settings where the standard theorem fails. Furthermore, unlike the method necessary for proving the original result, the present one is rather elementary. In the case of a qubit, we investigate similar results for frame functions defined upon various restricted classes of POVMs. For the so-called trine measurements, the standard quantum probability rule is again recovered.
- Apr 07 1999 quant-ph arXiv:quant-ph/9904021v2We describe some applications of quantum information theory to the analysis of quantum limits on measurement sensitivity. A measurement of a weak force acting on a quantum system is a determination of a classical parameter appearing in the master equation that governs the evolution of the system; limitations on measurement accuracy arise because it is not possible to distinguish perfectly among the different possible values of this parameter. Tools developed in the study of quantum information and computation can be exploited to improve the precision of physics experiments; examples include superdense coding, fast database search, and the quantum Fourier transform.