BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Fernando G. S. L. Brandao

Fernando G. S. L. Brandao appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
quant-phmath-phmath.MPcond-mat.stat-mechComputational Complexitycond-mat.str-elInformation Theorymath.ITcond-mat.otherData Structures and Algorithmshep-thmath.OCmath.PR

Catalog footprint

What is connected

36works
13topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

36 published item(s)

preprint2022arXiv

The Pursuit of Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings

Valiant-Vazirani showed in 1985 [VV85] that solving NP with the promise that "yes" instances have only one witness is powerful enough to solve the entire NP class (under randomized reductions). We are interested in extending this result to the quantum setting. We prove extensions to the classes Merlin-Arthur MA and Quantum-Classical-Merlin-Arthur QCMA. Our results have implications for the complexity of approximating the ground state energy of a quantum local Hamiltonian with a unique ground state and an inverse polynomial spectral gap. We show that the estimation (to within polynomial accuracy) of the ground state energy of poly-gapped 1-D local Hamiltonians is QCMA-hard [AN02], under randomized reductions. This is in stark contrast to the case of constant gapped 1-D Hamiltonians, which is in NP [Has07]. Moreover, it shows that unless QCMA can be reduced to NP by randomized reductions, there is no classical description of the ground state of every poly-gapped local Hamiltonian that allows efficient calculation of expectation values. Finally, we discuss a few of the obstacles to the establishment of an analogous result to the class Quantum-Merlin-Arthur (QMA). In particular, we show that random projections fail to provide a polynomial gap between two witnesses.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Adversarial hypothesis testing and a quantum Stein's Lemma for restricted measurements

Recall the classical hypothesis testing setting with two convex sets of probability distributions P and Q. One receives either n i.i.d. samples from a distribution p in P or from a distribution q in Q and wants to decide from which set the points were sampled. It is known that the optimal exponential rate at which errors decrease can be achieved by a simple maximum-likelihood ratio test which does not depend on p or q, but only on the sets P and Q. We consider an adaptive generalization of this model where the choice of p in P and q in Q can change in each sample in some way that depends arbitrarily on the previous samples. In other words, in the k'th round, an adversary, having observed all the previous samples in rounds 1,...,k-1, chooses p_k in P and q_k in Q, with the goal of confusing the hypothesis test. We prove that even in this case, the optimal exponential error rate can be achieved by a simple maximum-likelihood test that depends only on P and Q. We then show that the adversarial model has applications in hypothesis testing for quantum states using restricted measurements. For example, it can be used to study the problem of distinguishing entangled states from the set of all separable states using only measurements that can be implemented with local operations and classical communication (LOCC). The basic idea is that in our setup, the deleterious effects of entanglement can be simulated by an adaptive classical adversary. We prove a quantum Stein's Lemma in this setting: In many circumstances, the optimal hypothesis testing rate is equal to an appropriate notion of quantum relative entropy between two states. In particular, our arguments yield an alternate proof of Li and Winter's recent strengthening of strong subadditivity for quantum relative entropy.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution

The accurate computation of Hamiltonian ground, excited, and thermal states on quantum computers stands to impact many problems in the physical and computer sciences, from quantum simulation to machine learning. Given the challenges posed in constructing large-scale quantum computers, these tasks should be carried out in a resource-efficient way. In this regard, existing techniques based on phase estimation or variational algorithms display potential disadvantages; phase estimation requires deep circuits with ancillae, that are hard to execute reliably without error correction, while variational algorithms, while flexible with respect to circuit depth, entail additional high-dimensional classical optimization. Here, we introduce the quantum imaginary time evolution and quantum Lanczos algorithms, which are analogues of classical algorithms for finding ground and excited states. Compared to their classical counterparts, they require exponentially less space and time per iteration, and can be implemented without deep circuits and ancillae, or high-dimensional optimization. We furthermore discuss quantum imaginary time evolution as a subroutine to generate Gibbs averages through an analog of minimally entangled typical thermal states. Finally, we demonstrate the potential of these algorithms via an implementation using exact classical emulation as well as through prototype circuits on the Rigetti quantum virtual machine and Aspen-1 quantum processing unit.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Efficient classical simulation of random shallow 2D quantum circuits

Random quantum circuits are commonly viewed as hard to simulate classically. In some regimes this has been formally conjectured, and there had been no evidence against the more general possibility that for circuits with uniformly random gates, approximate simulation of typical instances is almost as hard as exact simulation. We prove that this is not the case by exhibiting a shallow circuit family with uniformly random gates that cannot be efficiently classically simulated near-exactly under standard hardness assumptions, but can be simulated approximately for all but a superpolynomially small fraction of circuit instances in time linear in the number of qubits and gates. We furthermore conjecture that sufficiently shallow random circuits are efficiently simulable more generally. To this end, we propose and analyze two simulation algorithms. Implementing one of our algorithms numerically, we give strong evidence that it is efficient both asymptotically and, in some cases, in practice. To argue analytically for efficiency, we reduce the simulation of 2D shallow random circuits to the simulation of a form of 1D dynamics consisting of alternating rounds of random local unitaries and weak measurements -- a type of process that has generally been observed to undergo a phase transition from an efficient-to-simulate regime to an inefficient-to-simulate regime as measurement strength is varied. Using a mapping from quantum circuits to statistical mechanical models, we give evidence that a similar computational phase transition occurs for our algorithms as parameters of the circuit architecture like the local Hilbert space dimension and circuit depth are varied.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Supplementary information for "Quantum supremacy using a programmable superconducting processor"

This is an updated version of supplementary information to accompany "Quantum supremacy using a programmable superconducting processor", an article published in the October 24, 2019 issue of Nature. The main article is freely available at https://www.nature.com/articles/s41586-019-1666-5. Summary of changes since arXiv:1910.11333v1 (submitted 23 Oct 2019): added URL for qFlex source code; added Erratum section; added Figure S41 comparing statistical and total uncertainty for log and linear XEB; new References [1,65]; miscellaneous updates for clarity and style consistency; miscellaneous typographical and formatting corrections.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Efficient Quantum Pseudorandomness

Randomness is both a useful way to model natural systems and a useful tool for engineered systems, e.g. in computation, communication and control. Fully random transformations require exponential time for either classical or quantum systems, but in many case pseudorandom operations can emulate certain properties of truly random ones. Indeed in the classical realm there is by now a well-developed theory of such pseudorandom operations. However the construction of such objects turns out to be much harder in the quantum case. Here we show that random quantum circuits are a powerful source of quantum pseudorandomness. This gives the for the first time a polynomialtime construction of quantum unitary designs, which can replace fully random operations in most applications, and shows that generic quantum dynamics cannot be distinguished from truly random processes. We discuss applications of our result to quantum information science, cryptography and to understanding self-equilibration of closed quantum dynamics.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Quantum Conditional Mutual Information, Reconstructed States, and State Redistribution

We give two strengthenings of an inequality for the quantum conditional mutual information of a tripartite quantum state recently proved by Fawzi and Renner, connecting it with the ability to reconstruct the state from its bipartite reductions. Namely we show that the conditional mutual information is an upper bound on the regularised relative entropy distance between the quantum state and its reconstructed version. It is also an upper bound for the measured relative entropy distance of the state to its reconstructed version. The main ingredient of the proof is the fact that the conditional mutual information is the optimal quantum communication rate in the task of state redistribution.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Quantum Gibbs Samplers: the commuting case

We analyze the problem of preparing quantum Gibbs states of lattice spin Hamiltonians with local and commuting terms on a quantum computer and in nature. Our central result is an equivalence between the behavior of correlations in the Gibbs state and the mixing time of the semigroup which drives the system to thermal equilibrium (the Gibbs sampler). We introduce a framework for analyzing the correlation and mixing characteristics of quantum Gibbs states and quantum Gibbs samplers, which is rooted in the theory of non-commutative Lp spaces. We consider two distinct classes of Gibbs samplers, one of which being the well-studied Davies generators modelling the dynamics on the system due to weak-coupling with a large Markovian environment. We show that their gap is independent of system size if, and only if, a certain strong form of clustering of correlations holds in the Gibbs state. As concrete applications of our formalism, we show that for every one-dimensional lattice system, or for systems in lattices of any dimension at high enough temperatures, the Gibbs samplers of commuting Hamiltonians are always gapped, giving an efficient way of preparing these states on a quantum computer.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The Mathematics of Entanglement

These notes are from a series of lectures given at the Universidad de Los Andes in Bogotá, Colombia on some topics of current interest in quantum information. While they aim to be self-contained, they are necessarily incomplete and idiosyncratic in their coverage. For a more thorough introduction to the subject, we recommend one of the textbooks by Nielsen and Chuang or by Wilde, or the lecture notes of Mermin, Preskill or Watrous. Our notes by contrast are meant to be a relatively rapid introduction into some more contemporary topics in this fast-moving field. They are meant to be accessible to advanced undergraduates or starting graduate students.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Entanglement area law from specific heat capacity

We study the scaling of entanglement in low-energy states of quantum many-body models on lattices of arbitrary dimensions. We allow for unbounded Hamiltonians such that systems with bosonic degrees of freedom are included. We show that if at low enough temperatures the specific heat capacity of the model decays exponentially with inverse temperature, the entanglement in every low-energy state satisfies an area law (with a logarithmic correction). This behaviour of the heat capacity is typically observed in gapped systems. Assuming merely that the low-temperature specific heat decays polynomially with temperature, we find a subvolume scaling of entanglement. Our results give experimentally verifiable conditions for area laws, show that they are a generic property of low-energy states of matter, and, to the best of our knowledge, constitute the first proof of an area law for unbounded Hamiltonians beyond those that are integrable.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Equivalence of Statistical Mechanical Ensembles for Non-Critical Quantum Systems

We consider the problem of whether the canonical and microcanonical ensembles are locally equivalent for short-ranged quantum Hamiltonians of $N$ spins arranged on a $d$-dimensional lattices. For any temperature for which the system has a finite correlation length, we prove that the canonical and microcanonical state are approximately equal on regions containing up to $O(N^{1/(d+1)})$ spins. The proof rests on a variant of the Berry--Esseen theorem for quantum lattice systems and ideas from quantum information theory.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Estimating operator norms using covering nets

We present several polynomial- and quasipolynomial-time approximation schemes for a large class of generalized operator norms. Special cases include the $2\rightarrow q$ norm of matrices for $q>2$, the support function of the set of separable quantum states, finding the least noisy output of entanglement-breaking quantum channels, and approximating the injective tensor norm for a map between two Banach spaces whose factorization norm through $\ell_1^n$ is bounded. These reproduce and in some cases improve upon the performance of previous algorithms by Brandão-Christandl-Yard and followup work, which were based on the Sum-of-Squares hierarchy and whose analysis used techniques from quantum information such as the monogamy principle of entanglement. Our algorithms, by contrast, are based on brute force enumeration over carefully chosen covering nets. These have the advantage of using less memory, having much simpler proofs and giving new geometric insights into the problem. Net-based algorithms for similar problems were also presented by Shi-Wu and Barak-Kelner-Steurer, but in each case with a run-time that is exponential in the rank of some matrix. We achieve polynomial or quasipolynomial runtimes by using the much smaller nets that exist in $\ell_1$ spaces. This principle has been used in learning theory, where it is known as Maurey's empirical method.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Exponential Decay of Correlations Implies Area Law

We prove that a finite correlation length, i.e. exponential decay of correlations, implies an area law for the entanglement entropy of quantum states defined on a line. The entropy bound is exponential in the correlation length of the state, thus reproducing as a particular case Hastings proof of an area law for groundstates of 1D gapped Hamiltonians. As a consequence, we show that 1D quantum states with exponential decay of correlations have an efficient classical approximate description as a matrix product state of polynomial bond dimension, thus giving an equivalence between injective matrix product states and states with a finite correlation length. The result can be seen as a rigorous justification, in one dimension, of the intuition that states with exponential decay of correlations, usually associated with non-critical phases of matter, are simple to describe. It also has implications for quantum computing: It shows that unless a pure state quantum computation involves states with long-range correlations, decaying at most algebraically with the distance, it can be efficiently simulated classically. The proof relies on several previous tools from quantum information theory - including entanglement distillation protocols achieving the hashing bound, properties of single-shot smooth entropies, and the quantum substate theorem - and also on some newly developed ones. In particular we derive a new bound on correlations established by local random measurements, and we give a generalization to the max-entropy of a result of Hastings concerning the saturation of mutual information in multiparticle systems. The proof can also be interpreted as providing a limitation on the phenomenon of data hiding in quantum states.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Generic emergence of classical features in quantum Darwinism

Quantum Darwinism explains the emergence of classical reality from the underlying quantum reality by the fact that a quantum system is observed indirectly, by looking at parts of its environment, so that only specific information about the system that is redundantly proliferated to many parts of the environment becomes accessible and objective. However it is not clear under what conditions this mechanism holds true. Here we rigorously prove that the emergence of classicality is a general feature of any quantum dynamics: observers who acquire information about a quantum system indirectly have access at most to classical information about one and the same measurement of the quantum system; moreover, if such information is available to many observers, they necessarily agree. Remarkably, our analysis goes beyond the system-environment categorization. We also provide a full characterization of the so-called quantum discord in terms of local redistribution of correlations.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Robust Device-Independent Randomness Amplification with Few Devices

Randomness amplification is the task of transforming a source of somewhat random bits into a source of fully random bits. Although it is impossible to amplify randomness from a single source by classical means, the situation is different considering non-local correlations allowed by quantum mechanics. Here we give the first device-independent protocol for randomness amplification using a constant number of devices. The protocol involves four devices, can amplify any non-deterministic source into a fully random source, tolerates a constant rate of error, and has its correctness based solely on the assumption of no-signaling between the devices. In contrast all previous protocols either required an unbounded number of devices, or could only amplify sources sufficiently close to fully random.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The second laws of quantum thermodynamics

The second law of thermodynamics tells us which state transformations are so statistically unlikely that they are effectively forbidden. Its original formulation, due to Clausius, states that "Heat can never pass from a colder to a warmer body without some other change, connected therewith, occurring at the same time". The second law applies to systems composed of many particles interacting; however, we are seeing that one can make sense of thermodynamics in the regime where we only have a small number of particles interacting with a heat bath. Is there a second law of thermodynamics in this regime? Here, we find that for processes which are cyclic or very close to cyclic, the second law for microscopic systems takes on a very different form than it does at the macroscopic scale, imposing not just one constraint on what state transformations are possible, but an entire family of constraints. In particular, we find a family of free energies which generalise the traditional one, and show that they can never increase. We further find that there are three regimes which determine which family of second laws govern state transitions, depending on how cyclic the process is. In one regime one can cause an apparent violation of the usual second law, through a process of embezzling work from a large system which remains arbitrarily close to its original state. These second laws are not only relevant for small systems, but also apply to individual macroscopic systems interacting via long-range interactions, which only satisfy the ordinary second law on average. By making precise the definition of thermal operations, the laws of thermodynamics take on a simple form with the first law defining the class of thermal operations, the zeroeth law emerging as a unique condition ensuring the theory is nontrivial, and the remaining laws being a monotonicity property of our generalised free energies.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

An area law for entanglement from exponential decay of correlations

Area laws for entanglement in quantum many-body systems give useful information about their low-temperature behaviour and are tightly connected to the possibility of good numerical simulations. An intuition from quantum many-body physics suggests that an area law should hold whenever there is exponential decay of correlations in the system, a property found, for instance, in non-critical phases of matter. However, the existence of quantum data-hiding state--that is, states having very small correlations, yet a volume scaling of entanglement--was believed to be a serious obstruction to such an implication. Here we prove that notwithstanding the phenomenon of data hiding, one-dimensional quantum many-body states satisfying exponential decay of correlations always fulfil an area law. To obtain this result we combine several recent advances in quantum information theory, thus showing the usefulness of the field for addressing problems in other areas of physics.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Are all maximally entangled states pure?

We study if all maximally entangled states are pure through several entanglement monotones. In the bipartite case, we find that the same conditions which lead to the uniqueness of the entropy of entanglement as a measure of entanglement, exclude the existence of maximally mixed entangled states. In the multipartite scenario, our conclusions allow us to generalize the idea of monogamy of entanglement: we establish the \textit{polygamy of entanglement}, expressing that if a general state is maximally entangled with respect to some kind of multipartite entanglement, then it is necessarily factorized of any other system.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Correlated entanglement distillation and the structure of the set of undistillable states

We consider entanglement distillation under the assumption that the input states are allowed to be correlated among each other. We hence replace the usually considered independent and identically-distributed hypothesis by the weaker assumption of merely having identical reductions. We find that whether a state is then distillable or not is only a property of these reductions, and not of the correlations that are present in the input state. This is shown by establishing an appealing relation between the set of copy-correlated undistillable states and the standard set of undistillable states: The former turns out to be the convex hull of the latter. As an example of the usefulness of our approach to the study of entanglement distillation, we prove a new activation result, which generalizes earlier findings: it is shown that for every entangled state and every positive integer k, there exists a copy-correlated k-undistillable state such that their tensor product is single-copy distillable. Finally, the relation of our results to the conjecture about the existence of bound entangled states with a non-positive partial transpose is discussed.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Entangled inputs cannot make imperfect quantum channels perfect

Entangled inputs can enhance the capacity of quantum channels, this being one of the consequences of the celebrated result showing the non-additivity of several quantities relevant for quantum information science. In this work, we answer the converse question (whether entangled inputs can ever render noisy quantum channels have maximum capacity) to the negative: No sophisticated entangled input of any quantum channel can ever enhance the capacity to the maximum possible value; a result that holds true for all channels both for the classical as well as the quantum capacity. This result can hence be seen as a bound as to how "non-additive quantum information can be". As a main result, we find first practical and remarkably simple computable single-shot bounds to capacities, related to entanglement measures. As examples, we discuss the qubit amplitude damping and identify the first meaningful bound for its classical capacity.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Entanglement distillation by extendible maps

It is known that from entangled states that have positive partial transpose it is not possible to distill maximally entangled states by local operations and classical communication (LOCC). A long-standing open question is whether maximally entangled states can be distilled from every state with a non-positive partial transpose. In this paper we study a possible approach to the question consisting of enlarging the class of operations allowed. Namely, instead of LOCC operations we consider k-extendible operations, defined as maps whose Choi-Jamiolkowski state is k-extendible. We find that this class is unexpectedly powerful - e.g. it is capable of distilling EPR pairs even from product states. We also perform numerical studies of distillation of Werner states by those maps, which show that if we raise the extension index k simultaneously with the number of copies of the state, then the class of k-extendible operations is not that powerful anymore and provide a better approximation to the set of LOCC operations.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Entanglement quantifiers and phase transitions

By the topological argument that the identity matrix is surrounded by a set of separable states follows the result that if a system is entangled at thermal equilibrium for some temperature, then it presents a phase transition (PT) where entanglement can be viewed as the order parameter. However, analyzing different entanglement measures in the 2-qubit context, we see that different entanglement quantifiers can indicate different orders for the same PT. Examples are given for different Hamiltonians. Moving to the multipartite context we show necessary and sufficient conditions for a family of entanglement monotones to attest quantum phase transitions.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Exponential Quantum Speed-ups are Generic

A central problem in quantum computation is to understand which quantum circuits are useful for exponential speed-ups over classical computation. We address this question in the setting of query complexity and show that for almost any sufficiently long quantum circuit one can construct a black-box problem which is solved by the circuit with a constant number of quantum queries, but which requires exponentially many classical queries, even if the classical machine has the ability to postselect. We prove the result in two steps. In the first, we show that almost any element of an approximate unitary 3-design is useful to solve a certain black-box problem efficiently. The problem is based on a recent oracle construction of Aaronson and gives an exponential separation between quantum and classical bounded-error with postselection query complexities. In the second step, which may be of independent interest, we prove that linear-sized random quantum circuits give an approximate unitary 3-design. The key ingredient in the proof is a technique from quantum many-body theory to lower bound the spectral gap of local quantum Hamiltonians.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Quantitative entanglement witnesses

Entanglement witnesses provide tools to detect entanglement in experimental situations without the need of having full tomographic knowledge about the state. If one estimates in an experiment an expectation value smaller than zero, one can directly infer that the state has been entangled, or specifically multi-partite entangled, in the first place. In this article, we emphasize that all these tests - based on the very same data - give rise to quantitative estimates in terms of entanglement measures: "If a test is strongly violated, one can also infer that the state was quantitatively very much entangled". We consider various measures of entanglement, including the negativity, the entanglement of formation, and the robustness of entanglement, in the bipartite and multipartite setting. As examples, we discuss several experiments in the context of quantum state preparation that have recently been performed.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Remarks on the equivalence of full additivity and monotonicity for the entanglement cost

We analyse the relationship between the full additivity of the entanglement cost and its full monotonicity under local operations and classical communication. We show that the two properties are equivalent for the entanglement cost. The proof works for the regularization of any convex, subadditive, and asymptotically continuous entanglement monotone, and hence also applies to the asymptotic relative entropy of entanglement.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Robust Device Independent Randomness Amplification

In randomness amplification a slightly random source is used to produce an improved random source. Perhaps surprisingly, a single source of randomness cannot be amplified at all classically. However, the situation is different if one considers correlations allowed by quantum mechanics as an extra resource. Here we present a protocol that amplifies Santha-Vazirani sources arbitrarily close to deterministic into fully random sources. The protocol is device independent, depending only on the observed statistics of the devices and on the validity of the no-signaling principle between different devices. It improves previously-known protocols in two respects. First the protocol is tolerant to noise so that even noisy quantum-mechanical systems give rise to good devices for the protocol. Second it is simpler, being based on the violation of a four-party Bell inequality and on the XOR as a hash function. As a technical tool we prove a new de Finetti theorem where the subsystems are selected from a Santha-Vazirani source.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Faithful Squashed Entanglement

Squashed entanglement is a measure for the entanglement of bipartite quantum states. In this paper we present a lower bound for squashed entanglement in terms of a distance to the set of separable states. This implies that squashed entanglement is faithful, that is, strictly positive if and only if the state is entangled. We derive the bound on squashed entanglement from a bound on quantum conditional mutual information, which is used to define squashed entanglement and corresponds to the amount by which strong subadditivity of von Neumann entropy fails to be saturated. Our result therefore sheds light on the structure of states that almost satisfy strong subadditivity with equality. The proof is based on two recent results from quantum information theory: the operational interpretation of the quantum mutual information as the optimal rate for state redistribution and the interpretation of the regularised relative entropy of entanglement as an error exponent in hypothesis testing. The distance to the set of separable states is measured by the one-way LOCC norm, an operationally-motivated norm giving the optimal probability of distinguishing two bipartite quantum states, each shared by two parties, using any protocol formed by local quantum operations and one-directional classical communication between the parties. A similar result for the Frobenius or Euclidean norm follows immediately. The result has two applications in complexity theory. The first is a quasipolynomial-time algorithm solving the weak membership problem for the set of separable states in one-way LOCC or Euclidean norm. The second concerns quantum Merlin-Arthur games. Here we show that multiple provers are not more powerful than a single prover when the verifier is restricted to one-way LOCC operations thereby providing a new characterisation of the complexity class QMA.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A quasipolynomial-time algorithm for the quantum separability problem

We present a quasipolynomial-time algorithm for solving the weak membership problem for the convex set of separable, i.e. non-entangled, bipartite density matrices. The algorithm decides whether a density matrix is separable or whether it is eps-away from the set of the separable states in time exp(O(eps^-2 log |A| log |B|)), where |A| and |B| are the local dimensions, and the distance is measured with either the Euclidean norm, or with the so-called LOCC norm. The latter is an operationally motivated norm giving the optimal probability of distinguishing two bipartite quantum states, each shared by two parties, using any protocol formed by quantum local operations and classical communication (LOCC) between the parties. We also obtain improved algorithms for optimizing over the set of separable states and for computing the ground-state energy of mean-field Hamiltonians. The techniques we develop are also applied to quantum Merlin-Arthur games, where we show that multiple provers are not more powerful than a single prover when the verifier is restricted to LOCC protocols, or when the verification procedure is formed by a measurement of small Euclidean norm. This answers a question posed by Aaronson et al (Theory of Computing 5, 1, 2009) and provides two new characterizations of the complexity class QMA, a quantum analog of NP. Our algorithm uses semidefinite programming to search for a symmetric extension, as first proposed by Doherty, Parrilo and Spedialieri (Phys. Rev. A, 69, 022308, 2004). The bound on the runtime follows from an improved de Finetti-type bound quantifying the monogamy of quantum entanglement, proved in (arXiv:1010.1750). This result, in turn, follows from a new lower bound on the quantum conditional mutual information and the entanglement measure squashed entanglement.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Detection of Multiparticle Entanglement: Quantifying the Search for Symmetric Extensions

We provide quantitative bounds on the characterisation of multiparticle separable states by states that have locally symmetric extensions. The bounds are derived from two-particle bounds and relate to recent studies on quantum versions of de Finetti's theorem. We discuss algorithmic applications of our results, in particular a quasipolynomial-time algorithm to decide whether a multiparticle quantum state is separable or entangled (for constant number of particles and constant error in the LOCC or Frobenius norm). Our results provide a theoretical justification for the use of the Search for Symmetric Extensions as a practical test for multiparticle entanglement.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

One-shot rates for entanglement manipulation under non-entangling maps

We obtain expressions for the optimal rates of one- shot entanglement manipulation under operations which generate a negligible amount of entanglement. As the optimal rates for entanglement distillation and dilution in this paradigm, we obtain the max- and min-relative entropies of entanglement, the two logarithmic robustnesses of entanglement, and smoothed versions thereof. This gives a new operational meaning to these entanglement measures. Moreover, by considering the limit of many identical copies of the shared entangled state, we partially recover the recently found reversibility of entanglement manipu- lation under the class of operations which asymptotically do not generate entanglement.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

A Generalization of Quantum Stein's Lemma

We present a generalization of quantum Stein's Lemma to the situation in which the alternative hypothesis is formed by a family of states, which can moreover be non-i.i.d.. We consider sets of states which satisfy a few natural properties, the most important being the closedness under permutations of the copies. We then determine the error rate function in a very similar fashion to quantum Stein's Lemma, in terms of the quantum relative entropy. Our result has two applications to entanglement theory. First it gives an operational meaning to an entanglement measure known as regularized relative entropy of entanglement. Second, it shows that this measure is faithful, being strictly positive on every entangled state. This implies, in particular, that whenever a multipartite state can be asymptotically converted into another entangled state by local operations and classical communication, the rate of conversion must be non-zero. Therefore, the operational definition of multipartite entanglement is equivalent to its mathematical definition.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

A reversible theory of entanglement and its relation to the second law

We consider the manipulation of multipartite entangled states in the limit of many copies under quantum operations that asymptotically cannot generate entanglement. As announced in [Brandao and Plenio, Nature Physics 4, 8 (2008)], and in stark contrast to the manipulation of entanglement under local operations and classical communication, the entanglement shared by two or more parties can be reversibly interconverted in this setting. The unique entanglement measure is identified as the regularized relative entropy of entanglement, which is shown to be equal to a regularized and smoothed version of the logarithmic robustness of entanglement. Here we give a rigorous proof of this result, which is fundamentally based on a certain recent extension of quantum Stein's Lemma proved in [Brandao and Plenio, Commun. Math. 295, 791 (2010)], giving the best measurement strategy for discriminating several copies of an entangled state from an arbitrary sequence of non-entangled states, with an optimal distinguishability rate equal to the regularized relative entropy of entanglement. We moreover analyse the connection of our approach to axiomatic formulations of the second law of thermodynamics.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

On Hastings' counterexamples to the minimum output entropy additivity conjecture

Hastings recently reported a randomized construction of channels violating the minimum output entropy additivity conjecture. Here we revisit his argument, presenting a simplified proof. In particular, we do not resort to the exact probability distribution of the Schmidt coefficients of a random bipartite pure state, as in the original proof, but rather derive the necessary large deviation bounds by a concentration of measure argument. Furthermore, we prove non-additivity for the overwhelming majority of channels consisting of a Haar random isometry followed by partial trace over the environment, for an environment dimension much bigger than the output dimension. This makes Hastings' original reasoning clearer and extends the class of channels for which additivity can be shown to be violated.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

A polaritonic two-component Bose-Hubbard model

We show that polaritons in an array of interacting micro-cavities with strong atom-photon coupling can form a two-component Bose-Hubbard model. Both polariton species are thereby protected against spontaneous emission as their atomic part is stored in two ground states of the atoms. The parameters of the effective model can be tuned via the driving strength of external lasers. We also describe a method to measure the number statistics in one cavity for each polariton species independently.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

Entanglement activation and the robustness of quantum correlations

We show that the usefulness of a state as an activator in teleportation protocols is equivalent to the robustness of its entanglement to noise. The robustness of entanglement of a bi-partite state is linked to the maximum increase in the the fidelity of teleportation of any other state when the former is used as an extra resource. On the one hand, this connection gives an operational meaning to the robustness of entanglement. On the other hand, it shows that the activation capability - which has a central role as an operational way of quantifying bound entangled states - can be estimated experimentally by measuring entanglement witnesses.

0 citations0 reviewsNo code linkedOpen access