Quantum Algorithms for Testing Hamiltonian Symmetry.

Symmetries in a Hamiltonian play an important role in quantum physics because they correspond directly with conserved quantities of the related system. In this Letter, we propose quantum algorithms capable of testing whether a Hamiltonian exhibits symmetry with respect to a group. We demonstrate that familiar expressions of Hamiltonian symmetry in quantum mechanics correspond directly with the acceptance probabilities of our algorithms. We execute one of our symmetry-testing algorithms on existing quantum computers for simple examples of both symmetric and asymmetric cases.

Quantum Algorithm for Petz Recovery Channels and Pretty Good Measurements.

The Petz recovery channel plays an important role in quantum information science as an operation that approximately reverses the effect of a quantum channel. The pretty good measurement is a special case of the Petz recovery channel, and it allows for near-optimal state discrimination. A hurdle to the experimental realization of these vaunted theoretical tools is the lack of a systematic and efficient method to implement them. This Letter sets out to rectify this lack: Using the recently developed tools of quantum singular value transformation and oblivious amplitude amplification, we provide a quantum algorithm to implement the Petz recovery channel when given the ability to perform the channel that one wishes to reverse. Moreover, we prove that, in some sense, our quantum algorithm's usage of the channel implementation cannot be improved by more than a quadratic factor. Our quantum algorithm also provides a procedure to perform pretty good measurements when given multiple copies of the states that one is trying to distinguish.

Cost of Quantum Entanglement Simplified.

Quantum entanglement is a key physical resource in quantum information processing that allows for performing basic quantum tasks such as teleportation and quantum key distribution, which are impossible in the classical world. Ever since the rise of quantum information theory, it has been an open problem to quantify entanglement in an information-theoretically meaningful way. In particular, every previously defined entanglement measure bearing a precise information-theoretic meaning is not known to be efficiently computable, or if it is efficiently computable, then it is not known to have a precise information-theoretic meaning. In this Letter, we meet this challenge by introducing an entanglement measure that has a precise information-theoretic meaning as the exact cost required to prepare an entangled state when two distant parties are allowed to perform quantum operations that completely preserve the positivity of the partial transpose. Additionally, this entanglement measure is efficiently computable by means of a semidefinite program, and it bears a number of useful properties such as additivity and faithfulness. Our results bring key insights into the fundamental entanglement structure of arbitrary quantum states, and they can be used directly to assess and quantify the entanglement produced in quantum-physical experiments.

Efficiently Computable Bounds for Magic State Distillation.

Magic-state distillation (or nonstabilizer state manipulation) is a crucial component in the leading approaches to realizing scalable, fault-tolerant, and universal quantum computation. Related to nonstabilizer state manipulation is the resource theory of nonstabilizer states, for which one of the goals is to characterize and quantify nonstabilizerness of a quantum state. In this Letter, we introduce the family of thauma measures to quantify the amount of nonstabilizerness in a quantum state, and we exploit this family of measures to address several open questions in the resource theory of nonstabilizer states. As a first application, we establish the hypothesis testing thauma as an efficiently computable benchmark for the one-shot distillable nonstabilizerness, which in turn leads to a variety of bounds on the rate at which nonstabilizerness can be distilled, as well as on the overhead of magic-state distillation. We then prove that the max-thauma can be used as an efficiently computable tool in benchmarking the efficiency of magic-state distillation, and that it can outperform previous approaches based on mana. Finally, we use the min-thauma to bound a quantity known in the literature as the "regularized relative entropy of magic." As a consequence of this bound, we find that two classes of states with maximal mana, a previously established nonstabilizerness measure, cannot be interconverted in the asymptotic regime at a rate equal to one. This result resolves a basic question in the resource theory of nonstabilizer states and reveals a difference between the resource theory of nonstabilizer states and other resource theories such as entanglement and coherence.

Conditional Quantum One-Time Pad.

Suppose that Alice and Bob are located in distant laboratories, which are connected by an ideal quantum channel. Suppose further that they share many copies of a quantum state ρ_{ABE}, such that Alice possesses the A systems and Bob the BE systems. In our model, there is an identifiable part of Bob's laboratory that is insecure: a third party named Eve has infiltrated Bob's laboratory and gained control of the E systems. Alice, knowing this, would like use their shared state and the ideal quantum channel to communicate a message in such a way that Bob, who has access to the whole of his laboratory (BE systems), can decode it, while Eve, who has access only to a sector of Bob's laboratory (E systems) and the ideal quantum channel connecting Alice to Bob, cannot learn anything about Alice's transmitted message. We call this task the conditional one-time pad, and in this Letter, we prove that the optimal rate of secret communication for this task is equal to the conditional quantum mutual information I(A;B|E) of their shared state. We thus give the conditional quantum mutual information an operational meaning that is different from those given in prior works, via state redistribution, conditional erasure, or state deconstruction. We also generalize the model and method in several ways, one of which is a secret-sharing task, i.e., the case in which Alice's message should be secure from someone possessing only the AB or AE systems, but should be decodable by someone possessing all systems A, B, and E.

Extendibility Limits the Performance of Quantum Processors.

Resource theories in quantum information science are helpful for the study and quantification of the performance of information-processing tasks that involve quantum systems. These resource theories also find applications in other areas of study; e.g., the resource theories of entanglement and coherence have found use and implications in the study of quantum thermodynamics and memory effects in quantum dynamics. In this paper, we introduce the resource theory of unextendibility, which is associated with the inability of extending quantum entanglement in a given quantum state to multiple parties. The free states in this resource theory are the k-extendible states, and the free channels are k-extendible channels, which preserve the class of k-extendible states. We make use of this resource theory to derive nonasymptotic, upper bounds on the rate at which quantum communication or entanglement preservation is possible by utilizing an arbitrary quantum channel a finite number of times, along with the assistance of k-extendible channels at no cost. We then show that the bounds obtained are significantly tighter than previously known bounds for quantum communication over both the depolarizing and erasure channels.

Extendibility of Bosonic Gaussian States.

Extendibility of bosonic Gaussian states is a key issue in continuous-variable quantum information. We show that a bosonic Gaussian state is k-extendible if and only if it has a Gaussian k-extension, and we derive a simple semidefinite program, whose size scales linearly with the number of local modes, to efficiently decide k-extendibility of any given bosonic Gaussian state. When the system to be extended comprises one mode only, we provide a closed-form solution. Implications of these results for the steerability of quantum states and for the extendibility of bosonic Gaussian channels are discussed. We then derive upper bounds on the distance of a k-extendible bosonic Gaussian state to the set of all separable states, in terms of trace norm and Rényi relative entropies. These bounds, which can be seen as "Gaussian de Finetti theorems," exhibit a universal scaling in the total number of modes, independently of the mean energy of the state. Finally, we establish an upper bound on the entanglement of formation of Gaussian k-extendible states, which has no analogue in the finite-dimensional setting.

Entropic Energy-Time Uncertainty Relation.

Energy-time uncertainty plays an important role in quantum foundations and technologies, and it was even discussed by the founders of quantum mechanics. However, standard approaches (e.g., Robertson's uncertainty relation) do not apply to energy-time uncertainty because, in general, there is no Hermitian operator associated with time. Following previous approaches, we quantify time uncertainty by how well one can read off the time from a quantum clock. We then use entropy to quantify the information-theoretic distinguishability of the various time states of the clock. Our main result is an entropic energy-time uncertainty relation for general time-independent Hamiltonians, stated for both the discrete-time and continuous-time cases. Our uncertainty relation is strong, in the sense that it allows for a quantum memory to help reduce the uncertainty, and this formulation leads us to reinterpret it as a bound on the relative entropy of asymmetry. Because of the operational relevance of entropy, we anticipate that our uncertainty relation will have information-processing applications.

Union bound for quantum information processing.

In this paper, we prove a quantum union bound that is relevant when performing a sequence of binary-outcome quantum measurements on a quantum state. The quantum union bound proved here involves a tunable parameter that can be optimized, and this tunable parameter plays a similar role to a parameter involved in the Hayashi-Nagaoka inequality (Hayashi & Nagaoka 2003 IEEE Trans. Inf. Theory 49, 1753-1768. (doi:10.1109/TIT.2003.813556)), used often in quantum information theory when analysing the error probability of a square-root measurement. An advantage of the proof delivered here is that it is elementary, relying only on basic properties of projectors, Pythagoras' theorem, and the Cauchy-Schwarz inequality. As a non-trivial application of our quantum union bound, we prove that a sequential decoding strategy for classical communication over a quantum channel achieves a lower bound on the channel's second-order coding rate. This demonstrates the advantage of our quantum union bound in the non-asymptotic regime, in which a communication channel is called a finite number of times. We expect that the bound will find a range of applications in quantum communication theory, quantum algorithms and quantum complexity theory.

Conditional Decoupling of Quantum Information.

Insights from quantum information theory show that correlation measures based on quantum entropy are fundamental tools that reveal the entanglement structure of multipartite states. In that spirit, Groisman, Popescu, and Winter [Phys. Rev. A 72, 032317 (2005)PLRAAN1050-294710.1103/PhysRevA.72.032317] showed that the quantum mutual information I(A;B) quantifies the minimal rate of noise needed to erase the correlations in a bipartite state of quantum systems AB. Here, we investigate correlations in tripartite systems ABE. In particular, we are interested in the minimal rate of noise needed to apply to the systems AE in order to erase the correlations between A and B given the information in system E, in such a way that there is only negligible disturbance on the marginal BE. We present two such models of conditional decoupling, called deconstruction and conditional erasure cost of tripartite states ABE. Our main result is that both are equal to the conditional quantum mutual information I(A;B|E)-establishing it as an operational measure for tripartite quantum correlations.

Fundamental Limits on the Capacities of Bipartite Quantum Interactions.

Bipartite quantum interactions have applications in a number of different areas of quantum physics, reaching from fundamental areas such as quantum thermodynamics and the theory of quantum measurements to other applications such as quantum computers, quantum key distribution, and other information processing protocols. A particular aspect of the study of bipartite interactions is concerned with the entanglement that can be created from such interactions. In this Letter, we present our work on two basic building blocks of bipartite quantum protocols, namely, the generation of maximally entangled states and secret key via bipartite quantum interactions. In particular, we provide a nontrivial, efficiently computable upper bound on the positive-partial-transpose-assisted quantum capacity of a bipartite quantum interaction. In addition, we provide an upper bound on the secret-key-agreement capacity of a bipartite quantum interaction assisted by local operations and classical communication. As an application, we introduce a cryptographic protocol for the readout of a digital memory device that is secure against a passive eavesdropper.

Unconstrained Capacities of Quantum Key Distribution and Entanglement Distillation for Pure-Loss Bosonic Broadcast Channels.

We consider quantum key distribution (QKD) and entanglement distribution using a single-sender multiple-receiver pure-loss bosonic broadcast channel. We determine the unconstrained capacity region for the distillation of bipartite entanglement and secret key between the sender and each receiver, whenever they are allowed arbitrary public classical communication. A practical implication of our result is that the capacity region demonstrated drastically improves upon rates achievable using a naive time-sharing strategy, which has been employed in previously demonstrated network QKD systems. We show a simple example of a broadcast QKD protocol overcoming the limit of the point-to-point strategy. Our result is thus an important step toward opening a new framework of network channel-based quantum communication technology.

Gaussian Hypothesis Testing and Quantum Illumination.

Quantum hypothesis testing is one of the most basic tasks in quantum information theory and has fundamental links with quantum communication and estimation theory. In this paper, we establish a formula that characterizes the decay rate of the minimal type-II error probability in a quantum hypothesis test of two Gaussian states given a fixed constraint on the type-I error probability. This formula is a direct function of the mean vectors and covariance matrices of the quantum Gaussian states in question. We give an application to quantum illumination, which is the task of determining whether there is a low-reflectivity object embedded in a target region with a bright thermal-noise bath. For the asymmetric-error setting, we find that a quantum illumination transmitter can achieve an error probability exponent stronger than a coherent-state transmitter of the same mean photon number, and furthermore, that it requires far fewer trials to do so. This occurs when the background thermal noise is either low or bright, which means that a quantum advantage is even easier to witness than in the symmetric-error setting because it occurs for a larger range of parameters. Going forward from here, we expect our formula to have applications in settings well beyond those considered in this paper, especially to quantum communication tasks involving quantum Gaussian channels.

Multipartite quantum correlations and local recoverability.

Characterizing genuine multipartite quantum correlations in quantum physical systems has historically been a challenging problem in quantum information theory. More recently, however, the total correlation or multipartite information measure has been helpful in accomplishing this goal, especially with the multipartite symmetric quantum (MSQ) discord (Piani et al. 2008 Phys. Rev. Lett. 100, 090502. (doi:10.1103/PhysRevLett.100.090502)) and the conditional entanglement of multipartite information (CEMI) (Yang et al. 2008 Phys. Rev. Lett. 101, 140501. (doi:10.1103/PhysRevLett.101.140501)). Here, we apply a recent and significant improvement of strong subadditivity of quantum entropy (Fawzi & Renner 2014 (http://arxiv.org/abs/1410.0664)) in order to develop these quantities further. In particular, we prove that the MSQ discord is nearly equal to zero if and only if the multipartite state for which it is evaluated is approximately locally recoverable after performing measurements on each of its systems. Furthermore, we prove that the CEMI is a faithful entanglement measure, i.e. it vanishes if and only if the multipartite state for which it is evaluated is a fully separable state. Along the way, we provide an operational interpretation of the MSQ discord in terms of the partial state distribution protocol, which in turn, as a special case, gives an interpretation for the original discord quantity. Finally, we prove an inequality that could potentially improve upon the Fawzi-Renner inequality in the multipartite context, but it remains an open question to determine whether this is so.

Fundamental rate-loss tradeoff for optical quantum key distribution.

Since 1984, various optical quantum key distribution (QKD) protocols have been proposed and examined. In all of them, the rate of secret key generation decays exponentially with distance. A natural and fundamental question is then whether there are yet-to-be discovered optical QKD protocols (without quantum repeaters) that could circumvent this rate-distance tradeoff. This paper provides a major step towards answering this question. Here we show that the secret key agreement capacity of a lossy and noisy optical channel assisted by unlimited two-way public classical communication is limited by an upper bound that is solely a function of the channel loss, regardless of how much optical power the protocol may use. Our result has major implications for understanding the secret key agreement capacity of optical channels-a long-standing open problem in optical quantum information theory-and strongly suggests a real need for quantum repeaters to perform QKD at high rates over long distances.

Noise and disturbance in quantum measurements: an information-theoretic approach.

We introduce information-theoretic definitions for noise and disturbance in quantum measurements and prove a state-independent noise-disturbance tradeoff relation that these quantities have to satisfy in any conceivable setup. Contrary to previous approaches, the information-theoretic quantities we define are invariant under the relabelling of outcomes and allow for the possibility of using quantum or classical operations to "correct" for the disturbance. We also show how our bound implies strong tradeoff relations for mean square deviations.

Quantum state cloning using Deutschian closed timelike curves.

We show that it is possible to clone quantum states to arbitrary accuracy in the presence of a Deutschian closed timelike curve (D-CTC), with a fidelity converging to one in the limit as the dimension of the CTC system becomes large--thus resolving an open conjecture [Brun et al., Phys. Rev. Lett. 102, 210402 (2009)]. This result follows from a D-CTC-assisted scheme for producing perfect clones of a quantum state prepared in a known eigenbasis, and the fact that one can reconstruct an approximation of a quantum state from empirical estimates of the probabilities of an informationally complete measurement. Our results imply more generally that every continuous, but otherwise arbitrarily nonlinear map from states to states, can be implemented to arbitrary accuracy with D-CTCs. Furthermore, our results show that Deutsch's model for closed timelike curves is in fact a classical model, in the sense that two arbitrary, distinct density operators are perfectly distinguishable (in the limit of a large closed timelike curve system); hence, in this model quantum mechanics becomes a classical theory in which each density operator is a distinct point in a classical phase space.

Information trade-offs for optical quantum communication.

Recent work has precisely characterized the achievable trade-offs between three key information processing tasks-classical communication (generation or consumption), quantum communication (generation or consumption), and shared entanglement (distribution or consumption), measured in bits, qubits, and ebits per channel use, respectively. Slices and corner points of this three-dimensional region reduce to well-known protocols for quantum channels. A trade-off coding technique can attain any point in the region and can outperform time sharing between the best-known protocols for accomplishing each information processing task by itself. Previously, the benefits of trade-off coding that had been found were too small to be of practical value (viz., for the dephasing and the universal cloning machine channels). In this Letter, we demonstrate that the associated performance gains are in fact remarkably high for several physically relevant bosonic channels that model free-space or fiber-optic links, thermal-noise channels, and amplifiers. We show that significant performance gains from trade-off coding also apply when trading photon-number resources between transmitting public and private classical information simultaneously over secret-key-assisted bosonic channels.

Localized closed timelike curves can perfectly distinguish quantum states.

We show that qubits traveling along closed timelike curves are a resource that a party can exploit to distinguish perfectly any set of quantum states. As a result, an adversary with access to closed timelike curves can break any prepare-and-measure quantum key distribution protocol. Our result also implies that a party with access to closed timelike curves can violate the Holevo bound.