Quantum Computing for Molecular Biology.

Molecular biology and biochemistry interpret microscopic processes in the living world in terms of molecular structures and their interactions, which are quantum mechanical by their very nature. Whereas the theoretical foundations of these interactions are well established, the computational solution of the relevant quantum mechanical equations is very hard. However, much of molecular function in biology can be understood in terms of classical mechanics, where the interactions of electrons and nuclei have been mapped onto effective classical surrogate potentials that model the interaction of atoms or even larger entities. The simple mathematical structure of these potentials offers huge computational advantages; however, this comes at the cost that all quantum correlations and the rigorous many-particle nature of the interactions are omitted. In this work, we discuss how quantum computation may advance the practical usefulness of the quantum foundations of molecular biology by offering computational advantages for simulations of biomolecules. We not only discuss typical quantum mechanical problems of the electronic structure of biomolecules in this context, but also consider the dominating classical problems (such as protein folding and drug design) as well as data-driven approaches of bioinformatics and the degree to which they might become amenable to quantum simulation and quantum computation.

Tip of the Quantum Entropy Cone.

Relations among von Neumann entropies of different parts of an N-partite quantum system have direct impact on our understanding of diverse situations ranging from spin systems to quantum coding theory and black holes. Best formulated in terms of the set Σ_{N}^{*} of possible vectors comprising the entropies of the whole and its parts, the famous strong subaddivity inequality constrains its closure Σ[over ¯]_{N}^{*}, which is a convex cone. Further homogeneous constrained inequalities are also known. In this Letter we provide (nonhomogeneous) inequalities that constrain Σ_{N}^{*} near the apex (the vector of zero entropies) of Σ[over ¯]_{N}^{*}, in particular showing that Σ_{N}^{*} is not a cone for N≥3. Our inequalities apply to vectors with certain entropy constraints saturated and, in particular, they show that while it is always possible to upscale an entropy vector to arbitrary integer multiples it is not always possible to downscale it to arbitrarily small size, thus answering a question posed by Winter.

Upper Bounds on Device-Independent Quantum Key Distribution.

Quantum key distribution (QKD) is a method that distributes a secret key to a sender and a receiver by the transmission of quantum particles (e.g., photons). Device-independent quantum key distribution (DIQKD) is a version of QKD with a stronger notion of security, in that the sender and receiver base their protocol only on the statistics of input and outputs of their devices as inspired by Bell's theorem. We study the rate at which DIQKD can be carried out for a given bipartite quantum state distributed between the sender and receiver or a quantum channel connecting them. We provide upper bounds on the achievable rate going beyond upper bounds possible for QKD. In particular, we construct states and channels where the QKD rate is significant while the DIQKD rate is negligible. This gap is illustrated for a practical case arising when using standard postprocessing techniques for entangled two-qubit states.

Asymptotic Performance of Port-Based Teleportation.

Quantum teleportation is one of the fundamental building blocks of quantum Shannon theory. While ordinary teleportation is simple and efficient, port-based teleportation (PBT) enables applications such as universal programmable quantum processors, instantaneous non-local quantum computation and attacks on position-based quantum cryptography. In this work, we determine the fundamental limit on the performance of PBT: for arbitrary fixed input dimension and a large number N of ports, the error of the optimal protocol is proportional to the inverse square of N. We prove this by deriving an achievability bound, obtained by relating the corresponding optimization problem to the lowest Dirichlet eigenvalue of the Laplacian on the ordered simplex. We also give an improved converse bound of matching order in the number of ports. In addition, we determine the leading-order asymptotics of PBT variants defined in terms of maximally entangled resource states. The proofs of these results rely on connecting recently-derived representation-theoretic formulas to random matrix theory. Along the way, we refine a convergence result for the fluctuations of the Schur-Weyl distribution by Johansson, which might be of independent interest.

SARS-CoV-2 transmission routes from genetic data: A Danish case study

BACKGROUND: The first cases of COVID-19 caused by the SARS-CoV-2 virus were reported in China in December 2019. The disease has since spread globally. Many countries have instated measures to slow the spread of the virus. Information about the spread of the virus in a country can inform the gradual reopening of a country and help to avoid a second wave of infections. Our study focuses on Denmark, which is opening up when this study is performed (end-May 2020) after a lockdown in mid-March. METHODS: We perform a phylogenetic analysis of 742 publicly available Danish SARS-CoV-2 genome sequences and put them into context using sequences from other countries. RESULTS: Our findings are consistent with several introductions of the virus to Denmark from independent sources. We identify several chains of mutations that occurred in Denmark. In at least one case we find evidence that the virus spread from Denmark to other countries. A number of the mutations found in Denmark are non-synonymous, and in general there is a considerable variety of strains. The proportions of the most common haplotypes remain stable after lockdown. CONCLUSION: Employing phylogenetic methods on Danish genome sequences of SARS-CoV-2, we exemplify how genetic data can be used to trace the introduction of a virus to a country. This provides alternative means for verifying existing assumptions. For example, our analysis supports the hypothesis that the virus was brought to Denmark by skiers returning from Ischgl. On the other hand, we identify transmission routes which suggest that Denmark was part of a network of countries among which the virus was being transmitted. This challenges the common narrative that Denmark only got infected from abroad. Our analysis concerning the ratio of haplotypes does not indicate that the major haplotypes appearing in Denmark have a different degree of virality.

Private States, Quantum Data Hiding, and the Swapping of Perfect Secrecy.

An important contribution to the understanding of quantum key distribution has been the discovery of entangled states from which secret bits, but no maximally entangled states, can be extracted [Horodecki et al., Phys. Rev. Lett. 94, 200501 (2005)PRLTAO0031-900710.1103/PhysRevLett.94.200501]. The construction of those states was based on an intuition that the quantum mechanical phenomena of data hiding and privacy might be related. In this Letter we firmly connect these two phenomena and highlight three aspects of this result. First, we simplify the definition of the secret key rate. Second, we give a formula for the one-way distillable entanglement of certain private states. Third, we consider the problem of extending the distance of quantum key distribution with help of intermediate stations, a setting called the quantum key repeater. We show that for protocols that first distill private states, it is essentially optimal to use the standard quantum repeater protocol based on entanglement distillation and entanglement swapping.

Catalytic Decoupling of Quantum Information.

The decoupling technique is a fundamental tool in quantum information theory with applications ranging from thermodynamics to many-body physics and black hole radiation whereby a quantum system is decoupled from another one by discarding an appropriately chosen part of it. Here, we introduce catalytic decoupling, i.e., decoupling with the help of an independent system. Thereby, we remove a restriction on the standard decoupling notion and present a tight characterization in terms of the max-mutual information. The novel notion unifies various tasks and leads to a resource theory of decoupling.

Clean Quantum and Classical Communication Protocols.

By how much must the communication complexity of a function increase if we demand that the parties not only correctly compute the function but also return all registers (other than the one containing the answer) to their initial states at the end of the communication protocol? Protocols that achieve this are referred to as clean and the associated cost as the clean communication complexity. Here we present clean protocols for calculating the inner product of two n-bit strings, showing that (in the absence of preshared entanglement) at most n+3 qubits or n+O(sqrt[n]) bits of communication are required. The quantum protocol provides inspiration for obtaining the optimal method to implement distributed cnot gates in parallel while minimizing the amount of quantum communication. For more general functions, we show that nearly all Boolean functions require close to 2n bits of classical communication to compute and close to n qubits if the parties have access to preshared entanglement. Both of these values are maximal for their respective paradigms.

Limitations on quantum key repeaters.

A major application of quantum communication is the distribution of entangled particles for use in quantum key distribution. Owing to noise in the communication line, quantum key distribution is, in practice, limited to a distance of a few hundred kilometres, and can only be extended to longer distances by use of a quantum repeater, a device that performs entanglement distillation and quantum teleportation. The existence of noisy entangled states that are undistillable but nevertheless useful for quantum key distribution raises the question of the feasibility of a quantum key repeater, which would work beyond the limits of entanglement distillation, hence possibly tolerating higher noise levels than existing protocols. Here we exhibit fundamental limits on such a device in the form of bounds on the rate at which it may extract secure key. As a consequence, we give examples of states suitable for quantum key distribution but unsuitable for the most general quantum key repeater protocol.

Entanglement polytopes: multiparticle entanglement from single-particle information.

Entangled many-body states are an essential resource for quantum computing and interferometry. Determining the type of entanglement present in a system usually requires access to an exponential number of parameters. We show that in the case of pure, multiparticle quantum states, features of the global entanglement can already be extracted from local information alone. This is achieved by associating any given class of entanglement with an entanglement polytope-a geometric object that characterizes the single-particle states compatible with that class. Our results, applicable to systems of arbitrary size and statistics, give rise to local witnesses for global pure-state entanglement and can be generalized to states affected by low levels of noise.

Pinning of fermionic occupation numbers.

The Pauli exclusion principle is a constraint on the natural occupation numbers of fermionic states. It has been suspected since at least the 1970s, and only proved very recently, that there is a multitude of further constraints on these numbers, generalizing the Pauli principle. Here, we provide the first analytic analysis of the physical relevance of these constraints. We compute the natural occupation numbers for the ground states of a family of interacting fermions in a harmonic potential. Intriguingly, we find that the occupation numbers are almost, but not exactly, pinned to the boundary of the allowed region (quasipinned). The result suggests that the physics behind the phenomenon is richer than previously appreciated. In particular, it shows that for some models, the generalized Pauli constraints play a role for the ground state, even though they do not limit the ground-state energy. Our findings suggest a generalization of the Hartree-Fock approximation.

Complete insecurity of quantum protocols for classical two-party computation.

A fundamental task in modern cryptography is the joint computation of a function which has two inputs, one from Alice and one from Bob, such that neither of the two can learn more about the other's input than what is implied by the value of the function. In this Letter, we show that any quantum protocol for the computation of a classical deterministic function that outputs the result to both parties (two-sided computation) and that is secure against a cheating Bob can be completely broken by a cheating Alice. Whereas it is known that quantum protocols for this task cannot be completely secure, our result implies that security for one party implies complete insecurity for the other. Our findings stand in stark contrast to recent protocols for weak coin tossing and highlight the limits of cryptography within quantum mechanics. We remark that our conclusions remain valid, even if security is only required to be approximate and if the function that is computed for Bob is different from that of Alice.

Detection of multiparticle entanglement: quantifying the search for symmetric extensions.

We provide quantitative bounds on the characterization 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 norm induced by one-way local operations and classical communication, or in the Frobenius norm). Our results provide a theoretical justification for the use of the search for symmetric extensions as a test for multiparticle entanglement.

Reliable quantum state tomography.

Quantum state tomography is the task of inferring the state of a quantum system by appropriate measurements. Since the frequency distributions of the outcomes of any finite number of measurements will generally deviate from their asymptotic limits, the estimates computed by standard methods do not in general coincide with the true state and, therefore, have no operational significance unless their accuracy is defined in terms of error bounds. Here we show that quantum state tomography, together with an appropriate data analysis procedure, yields reliable and tight error bounds, specified in terms of confidence regions-a concept originating from classical statistics. Confidence regions are subsets of the state space in which the true state lies with high probability, independently of any prior assumption on the distribution of the possible states. Our method for computing confidence regions can be applied to arbitrary measurements including fully coherent ones; it is practical and particularly well suited for tomography on systems consisting of a small number of qubits, which are currently in the focus of interest in experimental quantum information science.

Highly entangled states with almost no secrecy.

In this Letter we illuminate the relation between entanglement and secrecy by providing the first example of a quantum state that is highly entangled, but from which, nevertheless, almost no secrecy can be extracted. More precisely, we provide two bounds on the bipartite entanglement of the totally antisymmetric state in dimension d×d. First, we show that the amount of secrecy that can be extracted from the state is low; to be precise it is bounded by O(1/d). Second, we show that the state is highly entangled in the sense that we need a large amount of singlets to create the state: entanglement cost is larger than a constant, independent of d. In order to obtain our results we use representation theory, linear programming, and the entanglement measure known as squashed entanglement. Our findings also clarify the relation between the squashed entanglement and the relative entropy of entanglement.

Postselection technique for quantum channels with applications to quantum cryptography.

We propose a general method for studying properties of quantum channels acting on an n-partite system, whose action is invariant under permutations of the subsystems. Our main result is that, in order to prove that a certain property holds for an arbitrary input, it is sufficient to consider the case where the input is a particular de Finetti-type state, i.e., a state which consists of n identical and independent copies of an (unknown) state on a single subsystem. Our technique can be applied to the analysis of information-theoretic problems. For example, in quantum cryptography, we get a simple proof for the fact that security of a discrete-variable quantum key distribution protocol against collective attacks implies security of the protocol against the most general attacks. The resulting security bounds are tighter than previously known bounds obtained with help of the exponential de Finetti theorem.

Quantum computational complexity of the N-representability problem: QMA complete.

We study the computational complexity of the N-representability problem in quantum chemistry. We show that this problem is quantum Merlin-Arthur complete, which is the quantum generalization of nondeterministic polynomial time complete. Our proof uses a simple mapping from spin systems to fermionic systems, as well as a convex optimization technique that reduces the problem of finding ground states to N representability.

Security of quantum bit string commitment depends on the information measure.

Unconditionally secure nonrelativistic bit commitment is known to be impossible in both the classical and the quantum world. However, when committing to a string of n bits at once, how far can we stretch the quantum limits? In this Letter, we introduce a framework of quantum schemes where Alice commits a string of n bits to Bob, in such a way that she can only cheat on a bits and Bob can learn at most b bits of information before the reveal phase. Our results are twofold: we show by an explicit construction that in the traditional approach, where the reveal and guess probabilities form the security criteria, no good schemes can exist: a + b is at least n. If, however, we use a more liberal criterion of security, the accessible information, we construct schemes where a = 4log2(n) + O(1) and b = 4, which is impossible classically. Our findings significantly extend known no-go results for quantum bit commitment.

Mirror inversion of quantum states in linear registers.

Transfer of data in linear quantum registers can be significantly simplified with preengineered but not dynamically controlled interqubit couplings. We show how to implement a mirror inversion of the state of the register in each excitation subspace with respect to the center of the register. Our construction is especially appealing as it requires no dynamical control over individual interqubit interactions. If, however, individual control of the interactions is available then the mirror inversion operation can be performed on any substring of qubits in the register. In this case, a sequence of mirror inversions can generate any permutation of a quantum state of the involved qubits.

Perfect state transfer in quantum spin networks.

We propose a class of qubit networks that admit the perfect state transfer of any quantum state in a fixed period of time. Unlike many other schemes for quantum computation and communication, these networks do not require qubit couplings to be switched on and off. When restricted to N-qubit spin networks of identical qubit couplings, we show that 2log3N is the maximal perfect communication distance for hypercube geometries. Moreover, if one allows fixed but different couplings between the qubits, then perfect state transfer can be achieved over arbitrarily long distances in a linear chain.