Source author record

Seth Lloyd

Seth Lloyd appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Catalog footprint

What is connected

92works

34topics

4close collaborators

Actions

Connect this record

Open graph Browse works

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.

preprint2024arXiv

Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis

Quantum algorithms for topological data analysis (TDA) seem to provide an exponential advantage over the best classical approach while remaining immune to dequantization procedures and the data-loading problem. In this paper, we give complexity-theoretic evidence that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. Specifically, we prove that the problem of computing Betti numbers exactly is #P-hard, while the problem of approximating Betti numbers up to multiplicative error is NP-hard. Moreover, both problems retain their hardness if restricted to the regime where quantum algorithms for TDA perform best. Because quantum computers are not expected to solve #P-hard or NP-hard problems in subexponential time, our results imply that quantum algorithms for TDA offer only a polynomial advantage in the worst case. We support our claim by showing that the seminal quantum algorithm for TDA developed by Lloyd, Garnerone and Zanardi achieves a quadratic speedup over the best known classical approach in asymptotically almost all cases. Finally, we argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices rather than as a list of vertices and edges.

preprint2022arXiv

Learning quantum data with the quantum Earth Mover's distance

Quantifying how far the output of a learning algorithm is from its target is an essential task in machine learning. However, in quantum settings, the loss landscapes of commonly used distance metrics often produce undesirable outcomes such as poor local minima and exponentially decaying gradients. To overcome these obstacles, we consider here the recently proposed quantum earth mover's (EM) or Wasserstein-1 distance as a quantum analog to the classical EM distance. We show that the quantum EM distance possesses unique properties, not found in other commonly used quantum distance metrics, that make quantum learning more stable and efficient. We propose a quantum Wasserstein generative adversarial network (qWGAN) which takes advantage of the quantum EM distance and provides an efficient means of performing learning on quantum data. We provide examples where our qWGAN is capable of learning a diverse set of quantum data with only resources polynomial in the number of qubits.

preprint2022arXiv

Quantum advantage for differential equation analysis

Quantum algorithms for both differential equation solving and for machine learning potentially offer an exponential speedup over all known classical algorithms. However, there also exist obstacles to obtaining this potential speedup in useful problem instances. The essential obstacle for quantum differential equation solving is that outputting useful information may require difficult post-processing, and the essential obstacle for quantum machine learning is that inputting the training set is a difficult task just by itself. In this paper, we demonstrate, when combined, these difficulties solve one another. We show how the output of quantum differential equation solving can serve as the input for quantum machine learning, allowing dynamical analysis in terms of principal components, power spectra, and wavelet decompositions. To illustrate this, we consider continuous time Markov processes on epidemiological and social networks. These quantum algorithms provide an exponential advantage over existing classical Monte Carlo methods.

preprint2022arXiv

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 paper 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.

preprint2022arXiv

Quantum algorithms for group convolution, cross-correlation, and equivariant transformations

Group convolutions and cross-correlations, which are equivariant to the actions of group elements, are commonly used in mathematics to analyze or take advantage of symmetries inherent in a given problem setting. Here, we provide efficient quantum algorithms for performing linear group convolutions and cross-correlations on data stored as quantum states. Runtimes for our algorithms are logarithmic in the dimension of the group thus offering an exponential speedup compared to classical algorithms when input data is provided as a quantum state and linear operations are well conditioned. Motivated by the rich literature on quantum algorithms for solving algebraic problems, our theoretical framework opens a path for quantizing many algorithms in machine learning and numerical methods that employ group operations.

preprint2022arXiv

Quantum Maxwell's Demon Assisted by Non-Markovian Effects

Maxwell's demon is the quintessential example of information control, which is necessary for designing quantum devices. In thermodynamics, the demon is an intelligent being who utilizes the entropic nature of information to sort excitations between reservoirs, thus lowering the total entropy. So far, implementations of Maxwell's demon have largely been limited to Markovian baths. In our work, we study the degree to which such a demon may be assisted by non-Markovian effects using a superconducting circuit platform. The setup is two baths connected by a demon-controlled qutrit interface, allowing the transfer of excitations only if the overall entropy of the two baths is lowered. The largest entropy reduction is achieved in a non-Markovian regime, and importantly, due to non-Markovian effects, the demon performance can be optimized through proper timing. Our results demonstrate that non-Markovian effects can be exploited to boost the information transfer rate in quantum Maxwell demons.

preprint2022arXiv

Resonant Quantum Principal Component Analysis

Principal component analysis has been widely adopted to reduce the dimension of data while preserving the information. The quantum version of PCA (qPCA) can be used to analyze an unknown low-rank density matrix by rapidly revealing the principal components of it, i.e. the eigenvectors of the density matrix with largest eigenvalues. However, due to the substantial resource requirement, its experimental implementation remains challenging. Here, we develop a resonant analysis algorithm with the minimal resource for ancillary qubits, in which only one frequency scanning probe qubit is required to extract the principal components. In the experiment, we demonstrate the distillation of the first principal component of a 4$\times$4 density matrix, with the efficiency of 86.0% and fidelity of 0.90. This work shows the speed-up ability of quantum algorithm in dimension reduction of data and thus could be used as part of quantum artificial intelligence algorithms in the future.

preprint2022arXiv

The Quantum Wasserstein Distance of Order 1

We propose a generalization of the Wasserstein distance of order 1 to the quantum states of $n$ qudits. The proposal recovers the Hamming distance for the vectors of the canonical basis, and more generally the classical Wasserstein distance for quantum states diagonal in the canonical basis. The proposed distance is invariant with respect to permutations of the qudits and unitary operations acting on one qudit and is additive with respect to the tensor product. Our main result is a continuity bound for the von Neumann entropy with respect to the proposed distance, which significantly strengthens the best continuity bound with respect to the trace distance. We also propose a generalization of the Lipschitz constant to quantum observables. The notion of quantum Lipschitz constant allows us to compute the proposed distance with a semidefinite program. We prove a quantum version of Marton's transportation inequality and a quantum Gaussian concentration inequality for the spectrum of quantum Lipschitz observables. Moreover, we derive bounds on the contraction coefficients of shallow quantum circuits and of the tensor product of one-qudit quantum channels with respect to the proposed distance. We discuss other possible applications in quantum machine learning, quantum Shannon theory, and quantum many-body systems.

preprint2020arXiv

Learning Unitaries by Gradient Descent

We study the hardness of learning unitary transformations in $U(d)$ via gradient descent on time parameters of alternating operator sequences. We provide numerical evidence that, despite the non-convex nature of the loss landscape, gradient descent always converges to the target unitary when the sequence contains $d^2$ or more parameters. Rates of convergence indicate a "computational phase transition." With less than $d^2$ parameters, gradient descent converges to a sub-optimal solution, whereas with more than $d^2$ parameters, gradient descent converges exponentially to an optimal solution.

preprint2020arXiv

Quantum Computer Systems for Scientific Discovery

The great promise of quantum computers comes with the dual challenges of building them and finding their useful applications. We argue that these two challenges should be considered together, by co-designing full-stack quantum computer systems along with their applications in order to hasten their development and potential for scientific discovery. In this context, we identify scientific and community needs, opportunities, a sampling of a few use case studies, and significant challenges for the development of quantum computers for science over the next 2--10 years. This document is written by a community of university, national laboratory, and industrial researchers in the field of Quantum Information Science and Technology, and is based on a summary from a U.S. National Science Foundation workshop on Quantum Computing held on October 21--22, 2019 in Alexandria, VA.

preprint2020arXiv

Quantum embeddings for machine learning

Quantum classifiers are trainable quantum circuits used as machine learning models. The first part of the circuit implements a quantum feature map that encodes classical inputs into quantum states, embedding the data in a high-dimensional Hilbert space; the second part of the circuit executes a quantum measurement interpreted as the output of the model. Usually, the measurement is trained to distinguish quantum-embedded data. We propose to instead train the first part of the circuit -- the embedding -- with the objective of maximally separating data classes in Hilbert space, a strategy we call quantum metric learning. As a result, the measurement minimizing a linear classification loss is already known and depends on the metric used: for embeddings separating data using the l1 or trace distance, this is the Helstrom measurement, while for the l2 or Hilbert-Schmidt distance, it is a simple overlap measurement. This approach provides a powerful analytic framework for quantum machine learning and eliminates a major component in current models, freeing up more precious resources to best leverage the capabilities of near-term quantum information processors.

preprint2020arXiv

Quantum Medical Imaging Algorithms

A central task in medical imaging is the reconstruction of an image or function from data collected by medical devices (e.g., CT, MRI, and PET scanners). We provide quantum algorithms for image reconstruction with exponential speedup over classical counterparts when data is input as a quantum state. Since outputs of our algorithms are stored in quantum states, individual pixels of reconstructed images may not be efficiently accessed classically; instead, we discuss various methods to extract information from outputs using a variety of quantum post-processing algorithms.

preprint2020arXiv

Quantum polar decomposition algorithm

The polar decomposition for a matrix $A$ is $A=UB$, where $B$ is a positive Hermitian matrix and $U$ is unitary (or, if $A$ is not square, an isometry). This paper shows that the ability to apply a Hamiltonian $\pmatrix{ 0 & A^\dagger \cr A & 0 \cr} $ translates into the ability to perform the transformations $e^{-iBt}$ and $U$ in a deterministic fashion. We show how to use the quantum polar decomposition algorithm to solve the quantum Procrustes problem, to perform pretty good measurements, to find the positive Hamiltonian closest to any Hamiltonian, and to perform a Hamiltonian version of the quantum singular value transformation.

preprint2020arXiv

Quantum transport simulations in a programmable nanophotonic processor

Environmental noise and disorder play critical roles in quantum particle and wave transport in complex media, including solid-state and biological systems. Recent work has predicted that coupling between noisy environments and disordered systems, in which coherent transport has been arrested due to localization effects, could actually enhance transport. Photonic integrated circuits are promising platforms for studying such effects, with a central goal being the development of large systems providing low-loss, high-fidelity control over all parameters of the transport problem. Here, we fully map the role of disorder in quantum transport using a nanophotonic processor consisting of a mesh of 88 generalized beamsplitters programmable on microsecond timescales. Over 64,400 transport experiments, we observe several distinct transport regimes, including environment-assisted quantum transport and the ''quantum Goldilocks'' regime in strong, statically disordered discrete-time systems. Low loss and high-fidelity programmable transformations make this nanophotonic processor a promising platform for many-boson quantum simulation experiments.

preprint2020arXiv

Quantum-inspired algorithms in practice

We study the practical performance of quantum-inspired algorithms for recommendation systems and linear systems of equations. These algorithms were shown to have an exponential asymptotic speedup compared to previously known classical methods for problems involving low-rank matrices, but with complexity bounds that exhibit a hefty polynomial overhead compared to quantum algorithms. This raised the question of whether these methods were actually useful in practice. We conduct a theoretical analysis aimed at identifying their computational bottlenecks, then implement and benchmark the algorithms on a variety of problems, including applications to portfolio optimization and movie recommendations. On the one hand, our analysis reveals that the performance of these algorithms is better than the theoretical complexity bounds would suggest. On the other hand, their performance as seen in our implementation degrades noticeably as the rank and condition number of the input matrix are increased. Overall, our results indicate that quantum-inspired algorithms can perform well in practice provided that stringent conditions are met: low rank, low condition number, and very large dimension of the input matrix. By contrast, practical datasets are often sparse and high-rank, precisely the type that can be handled by quantum algorithms.

preprint2019arXiv

Dense coding capacity of a quantum channel

We consider the fundamental protocol of dense coding of classical information assuming that noise affects both the forward and backward communication lines between Alice and Bob. Assuming that this noise is described by the same quantum channel, we define its dense coding capacity by optimizing over all adaptive strategies that Alice can implement, while Bob encodes the information by means of Pauli operators. Exploiting techniques of channel simulation and protocol stretching, we are able to establish the dense coding capacity of Pauli channels in arbitrary finite dimension, with simple formulas for depolarizing and dephasing qubit channels.

preprint2019arXiv

Optimization and learning of quantum programs

A programmable quantum processor is a fundamental model of quantum computation. In this model, any quantum channel can be approximated by applying a fixed universal quantum operation onto an input state and a quantum `program' state, whose role is to condition the operation performed by the processor. It is known that perfect channel simulation is only possible in the limit of infinitely large program states, so that finding the best program state represents an open problem in the presence of realistic finite-dimensional resources. Here we prove that the search for the optimal quantum program is a convex optimization problem. This can be solved either exactly, by minimizing a diamond distance cost function via semi-definite programming, or approximately, by minimizing other cost functions via gradient-based machine learning methods. We apply this general result to a number of different designs for the programmable quantum processor, from the shallow protocol of quantum teleportation, to deeper schemes relying on port-based teleportation and parametric quantum circuits. We benchmark the various designs by investigating their optimal performance in simulating arbitrary unitaries, Pauli and amplitude damping channels.

preprint2016arXiv

A Quantum Enigma Machine: Experimentally Demonstrating Quantum Data Locking

Claude Shannon proved in 1949 that information-theoretic-secure encryption is possible if the encryption key is used only once, is random, and is at least as long as the message itself. Notwithstanding, when information is encoded in a quantum system, the phenomenon of quantum data locking allows one to encrypt a message with a shorter key and still provide information-theoretic security. We present one of the first feasible experimental demonstrations of quantum data locking for direct communication and propose a scheme for a quantum enigma machine that encrypts 6 bits per photon (containing messages, new encryption keys, and forward error correction bits) with less than 6 bits per photon of encryption key while remaining information-theoretically secure.

preprint2016arXiv

Chiral Quantum Walks

Given its importance to many other areas of physics, from condensed matter physics to thermodynamics, time-reversal symmetry has had relatively little influence on quantum information science. Here we develop a network-based picture of time-reversal theory, classifying Hamiltonians and quantum circuits as time-symmetric or not in terms of the elements and geometries of their underlying networks. Many of the typical circuits of quantum information science are found to exhibit time-asymmetry. Moreover, we show that time-asymmetry in circuits can be controlled using local gates only, and can simulate time-asymmetry in Hamiltonian evolution. We experimentally implement a fundamental example in which controlled time-reversal asymmetry in a palindromic quantum circuit leads to near-perfect transport. Our results pave the way for using time-symmetry breaking to control coherent transport, and imply that time-asymmetry represents an omnipresent yet poorly understood effect in quantum information science.

preprint2016arXiv

Decoherent histories approach to the cosmological measure problem

The method of decoherent histories allows probabilities to be assigned to sequences of quantum events in systems, such as the universe as a whole, where there is no external observer to make measurements. This paper applies the method of decoherent histories to address cosmological questions. Using a series of simple examples, beginning with the harmonic oscillator, we show that systems in a stationary state such as an energy eigenstate or thermal state can exhibit decoherent histories with non-trivial dynamics. We then examine decoherent histories in a universe that undergoes eternal inflation. Decoherent histories that assign probabilities to sequences of events in the vicinity of a timelike geodesic supply a natural cosmological measure. Under reasonable conditions, such sequences of events do not suffer from the presence of unlikely statistical fluctuations that mimic reality.

preprint2016arXiv

From clocks to cloners: Catalytic transformations under covariant operations and recoverability

There are various physical scenarios in which one can only implement operations with a certain symmetry. Under such restriction, a system in a symmetry-breaking state can be used as a catalyst, e.g. to prepare another system in a desired symmetry-breaking state. This sort of (approximate) catalytic state transformations are relevant in the context of (i) state preparation using a bounded-size quantum clock or reference frame, where the clock or reference frame acts as a catalyst, (ii) quantum thermodynamics, where again a clock can be used as a catalyst to prepare states which contain coherence with respect to the system Hamiltonian, and (iii) cloning of unknown quantum states, where the given copies of state can be interpreted as a catalyst for preparing the new copies. Using a recent result of Fawzi and Renner on approximate recoverability, we show that the achievable accuracy in this kind of catalytic transformations can be determined by a single function, namely the relative entropy of asymmetry, which is equal to the difference between the entropy of state and its symmetrized version: if the desired state transition does not require a large increase of this quantity, then it can be implemented with high fidelity using only symmetric operations. Our lower bound on the achievable fidelity is tight in the case of cloners, and can be achieved using the Petz recovery map, which interestingly turns out to be the optimal cloning map found by Werner.

preprint2016arXiv

Global coherence of quantum evolutions based on decoherent histories: theory and application to photosynthetic quantum energy transport

Assessing the role of interference in natural and artificial quantum dyanamical processes is a crucial task in quantum information theory. To this aim, an appopriate formalism is provided by the decoherent histories framework. While this approach has been deeply explored from different theoretical perspectives, it still lacks of a comprehensive set of tools able to concisely quantify the amount of coherence developed by a given dynamics. In this paper we introduce and test different measures of the (average) coherence present in dissipative (Markovian) quantum evolutions, at various time scales and for different levels of environmentally induced decoherence. In order to show the effectiveness of the introduced tools, we apply them to a paradigmatic quantum process where the role of coherence is being hotly debated: exciton transport in photosynthetic complexes. To spot out the essential features that may determine the performance of the transport we focus on a relevant trimeric subunit of the FMO complex and we use a simplified (Haken-Strobl) model for the system-bath interaction. Our analysis illustrates how the high efficiency of environmentally assisted transport can be traced back to a quantum recoil avoiding effect on the exciton dynamics, that preserves and sustains the benefits of the initial fast quantum delocalization of the exciton over the network. Indeed, for intermediate levels of decoherence, the bath is seen to selectively kill the negative interference between different exciton pathways, while retaining the initial positive one. The concepts and tools here developed show how the decoherent histories approach can be used to quantify the relation between coherence and efficiency in quantum dynamical processes.

preprint2016arXiv

On the uncomputability of the spectral gap

This paper reviews the 1994 proof that the spectral gap of Hamiltonian quantum systems capable of universal computation is uncomputable.

preprint2016arXiv

Passive states as optimal inputs for single-jump lossy quantum channels

The passive states of a quantum system minimize the average energy among all the states with a given spectrum. We prove that passive states are the optimal inputs of single-jump lossy quantum channels. These channels arise from a weak interaction of the quantum system of interest with a large Markovian bath in its ground state, such that the interaction Hamiltonian couples only consecutive energy eigenstates of the system. We prove that the output generated by any input state $ρ$ majorizes the output generated by the passive input state $ρ_0$ with the same spectrum of $ρ$. Then, the output generated by $ρ$ can be obtained applying a random unitary operation to the output generated by $ρ_0$. This is an extension of De Palma et al., IEEE Trans. Inf. Theory 62, 2895 (2016), where the same result is proved for one-mode bosonic Gaussian channels. We also prove that for finite temperature this optimality property can fail already in a two-level system, where the best input is a coherent superposition of the two energy eigenstates.

preprint2016arXiv

Quantum data hiding in the presence of noise

When classical or quantum information is broadcast to separate receivers, there exist codes that encrypt the encoded data such that the receivers cannot recover it when performing local operations and classical communication, but they can decode reliably if they bring their systems together and perform a collective measurement. This phenomenon is known as quantum data hiding and hitherto has been studied under the assumption that noise does not affect the encoded systems. With the aim of applying the quantum data hiding effect in practical scenarios, here we define the data-hiding capacity for hiding classical information using a quantum channel. Using this notion, we establish a regularized upper bound on the data hiding capacity of any quantum broadcast channel, and we prove that coherent-state encodings have a strong limitation on their data hiding rates. We then prove a lower bound on the data hiding capacity of channels that map the maximally mixed state to the maximally mixed state (we call these channels "mictodiactic"---they can be seen as a generalization of unital channels when the input and output spaces are not necessarily isomorphic) and argue how to extend this bound to generic channels and to more than two receivers.

preprint2016arXiv

The power of one qumode for quantum computation

Although quantum computers are capable of solving problems like factoring exponentially faster than the best-known classical algorithms, determining the resources responsible for their computational power remains unclear. An important class of problems where quantum computers possess an advantage is phase estimation, which includes applications like factoring. We introduce a new computational model based on a single squeezed state resource that can perform phase estimation, which we call the power of one qumode. This model is inspired by an interesting computational model known as deterministic quantum computing with one quantum bit (DQC1). Using the power of one qumode, we identify that the amount of squeezing is sufficient to quantify the resource requirements of different computational problems based on phase estimation. In particular, it establishes a quantitative relationship between the resources required for factoring and DQC1. For example, we find the squeezing required to factor has an exponential scaling whereas no squeezing (i.e., a coherent state) is already sufficient to solve the hardest problem in DQC1.

preprint2016arXiv

Time Independent Universal Computing with Spin Chains: Quantum Plinko Machine

We present a scheme for universal quantum computing using XY Heisenberg spin chains. Information is encoded into packets propagating down these chains, and they interact with each other to perform universal quantum computation. A circuit using g gate blocks on m qubits can be encoded into chains of length $O(g^{3+δ} m^{3+δ})$ for all $δ>0$ with vanishingly small error.

preprint2015arXiv

Adiabatic and Hamiltonian computing on a 2D lattice with simple 2-qubit interactions

We show how to perform universal Hamiltonian and adiabatic computing using a time-independent Hamiltonian on a 2D grid describing a system of hopping particles which string together and interact to perform the computation. In this construction, the movement of one particle is controlled by the presence or absence of other particles, an effective quantum field effect transistor that allows the construction of controlled-NOT and controlled-rotation gates. The construction translates into a model for universal quantum computation with time-independent 2-qubit ZZ and XX+YY interactions on an (almost) planar grid. The effective Hamiltonian is arrived at by a single use of first-order perturbation theory avoiding the use of perturbation gadgets. The dynamics and spectral properties of the effective Hamiltonian can be fully determined as it corresponds to a particular realization of a mapping between a quantum circuit and a Hamiltonian called the space-time circuit-to-Hamiltonian construction. Because of the simple interactions required, and because no higher-order perturbation gadgets are employed, our construction is potentially realizable using superconducting or other solid-state qubits.

preprint2015arXiv

Any non-affine one-to-one binary gate suffices for computation

Any non-affine one-to-one binary gate can be wired together with suitable inputs to give AND, OR, NOT and fan-out gates, and so suffices to construct a general-purpose computer.

preprint2015arXiv

Continuous-variable quantum enigma machines for long-distance key distribution

Quantum physics allows for unconditionally secure communication through insecure communication channels. The achievable rates of quantum-secured communication are fundamentally limited by the laws of quantum physics and in particular by the properties of entanglement. For a lossy communication line, this implies that the secret-key generation rate vanishes at least exponentially with the communication distance. We show that this fundamental limitation can be violated in a realistic scenario where the eavesdropper can store quantum information for only a finite, yet arbitrarily long, time. We consider communication through a lossy bononic channel (modeling linear loss in optical fibers) and we show that it is in principle possible to achieve a constant rate of key generation of one bit per optical mode over arbitrarily long communication distances.

preprint2015arXiv

Core-halo instability in dynamical systems

This paper proves an instability theorem for dynamical systems. As one adds interactions between subystems in a complex system, structured or random, a threshold of connectivity is reached beyond which the overall dynamics inevitably goes unstable. The threshold occurs at the point at which flows and interactions between subsystems (`surface' effects) overwhelm internal stabilizing dynamics (`volume' effects). The theorem is used to identify instability thresholds in systems that possess a core-halo or core-periphery structure, including the gravo-thermal catastrophe -- i.e., star collapse and explosion -- and the interbank payment network. In the core-halo model, the same dynamical instability underlies both gravitational and financial collapse.

preprint2015arXiv

MDI-QKD: Continuous- versus discrete-variables at metropolitan distances

In a comment, Xu, Curty, Qi, Qian, and Lo claimed that discrete-variable (DV) measurement device independent (MDI) quantum key distribution (QKD) would compete with its continuous-variable (CV) counterpart at metropolitan distances. Actually, Xu et al.'s analysis supports exactly the opposite by showing that the experimental rate of our CV protocol (achieved with practical room-temperature devices) remains one order of magnitude higher than their purely-numerical and over-optimistic extrapolation for qubits, based on nearly-ideal parameters and cryogenic detectors (unsuitable solutions for a realistic metropolitan network, which is expected to run on cheap room-temperature devices, potentially even mobile). The experimental rate of our protocol (expressed as bits per relay use) is confirmed to be two-three orders of magnitude higher than the rate of any realistic simulation of practical DV-MDI-QKD over short-medium distances. Of course this does not mean that DV-MDI-QKD networks should not be investigated or built, but increasing their rate is a non-trivial practical problem clearly beyond the analysis of Xu et al. Finally, in order to clarify the facts, we also refute a series of incorrect arguments against CV-MDI-QKD and, more generally, CV-QKD, which were made by Xu et al. with the goal of supporting their thesis.

preprint2015arXiv

Quantum algorithms for topological and geometric analysis of big data

Extracting useful information from large data sets can be a daunting task. Topological methods for analyzing data sets provide a powerful technique for extracting such information. Persistent homology is a sophisticated tool for identifying such topological features -- connected components, holes, or voids -- and for determining how such features persist as the data is viewed at different scales. This paper provides quantum algorithms for calculating Betti numbers in persistent homology, and for finding eigenvectors and eigenvalues of the combinatorial Laplacian. The algorithms provide an exponential speedup over classical algorithms for topological data analysis.

preprint2015arXiv

Quantum data locking for high-rate private communication

We show that, if the accessible information is used as a security quantifier, quantum channels with a certain symmetry can convey private messages at a tremendously high rate, as high as less than one bit below the rate of non-private classical communication. This result is obtained by exploiting the quantum data locking effect. The price to pay to achieve such a high private communication rate is that accessible information security is in general not composable. However, composable security holds against an eavesdropper who is forced to measure her share of the quantum system within a finite time after she gets it.

preprint2015arXiv

Quantum Time

We give a consistent quantum description of time, based on Page and Wootters' conditional probabilities mechanism, that overcomes the criticisms that were raised against similar previous proposals. In particular we show how the model allows to reproduce the correct statistics of sequential measurements performed on a system at different times.

preprint2015arXiv

The multi-mode quantum Entropy Power Inequality

The quantum version of a fundamental entropic data-processing inequality is presented. It establishes a lower bound for the entropy that can be generated in the output channels of a scattering process, which involves a collection of independent input bosonic modes (e.g., the modes of the electromagnetic field). The impact of this inequality in quantum information theory is potentially large and some relevant implications are considered in this work.

preprint2014arXiv

Analysis of a work of quantum art

This paper provides a quantum-mechanical analysis of an artwork, `Wigner's friends,' by Diemut Strebe. The work consists of two telescopes, one on earth, one launched into space, and explores ideas of quantum correlations and quantum measurement. This paper examines the scientific basis of the work and analyzes the form of quantum correlation between the two telescope systems.

preprint2014arXiv

High-rate quantum cryptography in untrusted networks

We extend the field of continuous-variable quantum cryptography to a network formulation where two honest parties connect to an untrusted relay by insecure quantum links. To generate secret correlations, they transmit coherent states to the relay where a continuous-variable Bell detection is performed and the outcome broadcast. Even though the detection could be fully corrupted and the links subject to optimal coherent attacks, the honest parties can still extract a secret key, achieving high rates when the relay is proximal to one party, as typical in public networks with access points or proxy servers. Our theory is confirmed by an experiment generating key-rates which are orders of magnitude higher than those achievable with discrete-variable protocols. Thus, using the cheapest possible quantum resources, we experimentally show the possibility of high-rate quantum key distribution in network topologies where direct links are missing between end-users and intermediate relays cannot be trusted.

preprint2014arXiv

Maximally strong entropic uncertainty relations and gauge invariance

Uncertainty relations are among the unique fingerprints of quantum physics, being direct expression of non-commutativity and complementarity. Entropic uncertainty relations arise in quantum information theory as the most natural expression of the uncertainty principle and have proven themselves important tools for cryptographic security proofs. An open question has been how strong entropic uncertainty relations can be. Here we answer this question by showing that there exist observables that obey maximally strong entropic uncertainty relations in high dimensional Hilbert spaces. Actually, we show that maximally strong uncertainty relations are typically verified if the observables are distributed somehow uniformly. In particular, we show that phase randomness in a mutually unbiased basis is sufficient, providing a link between uncertainty relations and local gauge invariance. For quantum systems of finite dimensions our approach provides an explicit relation between the strength of the uncertainty and its probability.

preprint2014arXiv

Optimality of Gaussian Discord

In this Letter we exploit the recently-solved conjecture on the bosonic minimum output entropy to show the optimality of Gaussian discord, so that the computation of quantum discord for bipartite Gaussian states can be restricted to local Gaussian measurements. We prove such optimality for a large family of Gaussian states, including all two-mode squeezed thermal states, which are the most typical Gaussian states realized in experiments. Our family also includes other types of Gaussian states and spans their entire set in a suitable limit where they become Choi-matrices of Gaussian channels. As a result, we completely characterize the quantum correlations possessed by some of the most important bosonic states in quantum optics and quantum information.

preprint2014arXiv

Quantum brachistochrone curves as geodesics: obtaining accurate control protocols for time-optimal quantum gates

Most methods of optimal control cannot obtain accurate time-optimal protocols. The quantum brachistochrone equation is an exception, and has the potential to provide accurate time-optimal protocols for essentially any quantum control problem. So far this potential has not been realized, however, due to the inadequacy of conventional numerical methods to solve it. Here, using differential geometry, we reformulate the quantum brachistochrone curves as geodesics on the unitary group. With this identification we are able to obtain a numerical method that efficiently solves the brachistochrone problem. We apply it to two examples demonstrating its power.

preprint2014arXiv

Quantum support vector machine for big data classification

Supervised machine learning is the classification of new data based on already classified training examples. In this work, we show that the support vector machine, an optimized binary classifier, can be implemented on a quantum computer, with complexity logarithmic in the size of the vectors and the number of training examples. In cases when classical sampling algorithms require polynomial time, an exponential speed-up is obtained. At the core of this quantum big data algorithm is a non-sparse matrix exponentiation technique for efficiently performing a matrix inversion of the training data inner-product (kernel) matrix.

preprint2014arXiv

Quantum-locked key distribution at nearly the classical capacity rate

Quantum data locking is a protocol that allows for a small secret key to (un)lock an exponentially larger amount of information, hence yielding the strongest violation of the classical one-time pad encryption in the quantum setting. This violation mirrors a large gap existing between two security criteria for quantum cryptography quantified by two entropic quantities: the Holevo information and the accessible information. We show that the latter becomes a sensible security criterion if an upper bound on the coherence time of the eavesdropper's quantum memory is known. Under this condition we introduce a protocol for secret key generation through a memoryless qudit channel. For channels with enough symmetry, such as the d-dimensional erasure and depolarizing channels, this protocol allows secret key generation at an asymptotic rate as high as the classical capacity minus one bit.

preprint2014arXiv

Robust quantum data locking from phase modulation

Quantum data locking is a unique quantum phenomenon that allows a relatively short key to (un)lock an arbitrarily long message encoded in a quantum state, in such a way that an eavesdropper who measures the state but does not know the key has essentially no information about the encrypted message. The application of quantum data locking in cryptography would allow one to overcome the limitations of the one-time pad encryption, which requires the key to have the same length as the message. However, it is known that the strength of quantum data locking is also its Achilles heel, as the leakage of a few bits of the key or the message may in principle allow the eavesdropper to unlock a disproportionate amount of information. In this paper we show that there exist quantum data locking schemes that can be made robust against information leakage by increasing the length of the shared key by a proportionate amount. This implies that a constant size key can still encrypt an arbitrarily long message as long as a fraction of it remains secret to the eavesdropper. Moreover, we greatly simplify the structure of the protocol by proving that phase modulation suffices to generate strong locking schemes, paving the way to optical experimental realizations. Also, we show that successful data locking protocols can be constructed using random codewords, which very well could be helpful in discovering random codes for data locking over noisy quantum channels.

preprint2014arXiv

Simplicial Ricci Flow: An Example of a Neck Pinch Singularity in 3D

We examine a Type-1 neck pinch singularity in simplicial Ricci flow (SRF) for an axisymmetric piecewise flat 3-dimensional geometry with 3-sphere topology. SRF was recently introduced as an unstructured mesh formulation of Hamilton's Ricci flow (RF). It describes the RF of a piecewise-flat simplicial geometry. In this paper, we apply the SRF equations to a representative double-lobed axisymmetric piecewise flat geometry with mirror symmetry at the neck similar to the geometry studied by Angenent and Knopf (A-K). We choose a specific radial profile and compare the SRF equations with the corresponding finite-difference solution of the continuum A-K RF equations. The piecewise-flat 3-geometries considered here are built of isosceles-triangle-based frustum blocks. The axial symmetry of this model allows us to use frustum blocks instead of tetrahedra. The 2-sphere cross-sectional geometries in our model are regular icosahedra. We demonstrate that, under a suitably-pinched initial geometry, the SRF equations for this relatively low-resolution discrete geometry yield the canonical Type-1 neck pinch singularity found in the corresponding continuum solution. We adaptively remesh during the evolution to keep the circumcentric dual lattice well-centered. Without such remeshing, we cannot evolve the discrete geometry to neck pinch. We conclude with a discussion of future generalizations and tests of this SRF model.

preprint2014arXiv

Unitarity of black hole evaporation in final-state projection models

Almheiri et al. have emphasized that otherwise reasonable beliefs about black hole evaporation are incompatible with the monogamy of quantum entanglement, a general property of quantum mechanics. We investigate the final-state projection model of black hole evaporation proposed by Horowitz and Maldacena, pointing out that this model admits cloning of quantum states and polygamous entanglement, allowing unitarity of the evaporation process to be reconciled with smoothness of the black hole event horizon. Though the model seems to require carefully tuned dynamics to ensure exact unitarity of the black hole S-matrix, for a generic final-state boundary condition the deviations from unitarity are exponentially small in the black hole entropy; furthermore observers inside black holes need not detect any deviations from standard quantum mechanics. Though measurements performed inside old black holes could potentially produce causality-violating phenomena, the computational complexity of decoding the Hawking radiation may render the causality violation unobservable. Final-state projection models illustrate how inviolable principles of standard quantum mechanics might be circumvented in a theory of quantum gravity.

preprint2014arXiv

Universal quantum computation in integrable systems

Quantized integrable systems can be made to perform universal quantum computation by the application of a global time-varying control. The action-angle variables of the integrable system function as qubits or qudits, which can be coupled selectively by the global control to induce universal quantum logic gates. By contrast, chaotic quantum systems, even if controllable, do not generically allow quantum computation under global control.

preprint2013arXiv

A Turing test for free will

Before Alan Turing made his crucial contributions to the theory of computation, he studied the question of whether quantum mechanics could throw light on the nature of free will. This article investigates the roles of quantum mechanics and computation in free will. Although quantum mechanics implies that events are intrinsically unpredictable, the `pure stochasticity' of quantum mechanics adds only randomness to decision making processes, not freedom. By contrast, the theory of computation implies that even when our decisions arise from a completely deterministic decision-making process, the outcomes of that process can be intrinsically unpredictable, even to -- especially to -- ourselves. I argue that this intrinsic computational unpredictability of the decision making process is what give rise to our impression that we possess free will. Finally, I propose a `Turing test' for free will: a decision maker who passes this test will tend to believe that he, she, or it possesses free will, whether the world is deterministic or not.

preprint2013arXiv

Marcus rate for electron transfer and the Goldilocks principle

We examine electron transfer between two quantum states in the presence of a dissipative environment represented as a set of independent harmonic oscillators. For this simple model, the Marcus transfer rates can be derived and we show that these rates are associated to an explicit expression for the environment correlation time. We demonstrate that as a manifestation of the Goldilocks principle, the optimal transfer is governed by a single parameter which is equal to just the inverse root square of two.

preprint2013arXiv

Pure state quantum statistical mechanics and black holes

Chapter 3 of S. Lloyd's 1988 Ph.D. thesis, `Black Holes, Demons, and the Loss of Coherence: How complex systems get information and what they do with it,' supervisor Heinz Pagels. Reformulates statistical mechanics in terms of pure states and shows that (a) quantum statistics of typical pure states are very close to the mechanics of statistical mechanical ensembles; (b) if a system is in a typical state with energy E, then the reduced density matrix of a subsystem is very close to a thermal state. (A similar result was derived using Levy's lemma some years later by S. Popescu, A.J. Short, A.Winter, Nature Physics 2, 754-758 (2006).) Pure state quantum statistical mechanics is applied to black holesto show that for typical states of matter insideand outside a black hole, the external state is likely to be thermal. Proposes novel interpretation of probabilities in quantum statistical mechanics. Full thesis available at http://meche.mit.edu/documents/slloyd_thesis.pdf. This chapter was submitted for publication to Physical Review in 1988 but rejected by one sentence referee report: `There is no physics in this paper.' You be the judge.

preprint2013arXiv

Quantum algorithms for supervised and unsupervised machine learning

Machine-learning tasks frequently involve problems of manipulating and classifying large numbers of vectors in high-dimensional spaces. Classical algorithms for solving such problems typically take time polynomial in the number of vectors and the dimension of the space. Quantum computers are good at manipulating high-dimensional vectors in large tensor product spaces. This paper provides supervised and unsupervised quantum machine learning algorithms for cluster assignment and cluster finding. Quantum machine learning can take time logarithmic in both the number of vectors and their dimension, an exponential speed-up over classical algorithms.

preprint2013arXiv

Quantum Cryptography Approaching the Classical Limit

We consider the security of continuous-variable quantum cryptography as we approach the classical-limit, i.e., when the unknown preparation noise at the sender's station becomes significantly noisy or thermal (even by as much as 10,000 times the variance of the vacuum mode). We show that, provided the channel transmission losses do not exceed 50%, the security of quantum cryptography is not dependent on the channel transmission, and is therefore, incredibly robust against significant amounts of excess preparation noise. We extend these results to consider for the first time quantum cryptography at wavelengths considerably longer than optical and find that regions of security still exist all the way down to the microwave.

preprint2013arXiv

Quantum enigma machines

Enigma machines are devices that perform cryptography using pseudo-random numbers. The original enigma machine code was broken by detecting hidden patterns in these pseudo-random numbers. This paper proposes a model for a quantum optical enigma machine and shows that the phenomenon of quantum data locking makes such quantum enigma machines provably secure even in the presence of noise and loss.

preprint2013arXiv

Quantum enigma machines and the locking capacity of a quantum channel

The locking effect is a phenomenon which is unique to quantum information theory and represents one of the strongest separations between the classical and quantum theories of information. The Fawzi-Hayden-Sen (FHS) locking protocol harnesses this effect in a cryptographic context, whereby one party can encode n bits into n qubits while using only a constant-size secret key. The encoded message is then secure against any measurement that an eavesdropper could perform in an attempt to recover the message, but the protocol does not necessarily meet the composability requirements needed in quantum key distribution applications. In any case, the locking effect represents an extreme violation of Shannon's classical theorem, which states that information-theoretic security holds in the classical case if and only if the secret key is the same size as the message. Given this intriguing phenomenon, it is of practical interest to study the effect in the presence of noise, which can occur in the systems of both the legitimate receiver and the eavesdropper. This paper formally defines the locking capacity of a quantum channel as the maximum amount of locked information that can be reliably transmitted to a legitimate receiver by exploiting many independent uses of a quantum channel and an amount of secret key sublinear in the number of channel uses. We provide general operational bounds on the locking capacity in terms of other well-known capacities from quantum Shannon theory. We also study the important case of bosonic channels, finding limitations on these channels' locking capacity when coherent-state encodings are employed and particular locking protocols for these channels that might be physically implementable.

preprint2013arXiv

Quantum principal component analysis

The usual way to reveal properties of an unknown quantum state, given many copies of a system in that state, is to perform measurements of different observables and to analyze the measurement results statistically. Here we show that the unknown quantum state can play an active role in its own analysis. In particular, given multiple copies of a quantum system with density matrix ρ, then it is possible to perform the unitary transformation e^{-iρt}. As a result, one can create quantum coherence among different copies of the system to perform quantum principal component analysis, revealing the eigenvectors corresponding to the large eigenvalues of the unknown state in time exponentially faster than any existing algorithm.

preprint2013arXiv

The universal path integral

Path integrals represent a powerful route to quantization: they calculate probabilities by summing over classical configurations of variables such as fields, assigning each configuration a phase equal to the action of that configuration. This paper defines a universal path integral, which sums over all computable structures. This path integral contains as sub-integrals all possible computable path integrals, including those of field theory, the standard model of elementary particles, discrete models of quantum gravity, string theory, etc. The universal path integral possesses a well-defined measure that guarantees its finiteness, together with a method for extracting probabilities for observable quantities. The universal path integral supports a quantum theory of the universe in which the world that we see around us arises out of the interference between all computable structures.

preprint2013arXiv

The universe as quantum computer

This article reviews the history of digital computation, and investigates just how far the concept of computation can be taken. In particular, I address the question of whether the universe itself is in fact a giant computer, and if so, just what kind of computer it is. I will show that the universe can be regarded as a giant quantum computer. The quantum computational model of the universe explains a variety of observed phenomena not encompassed by the ordinary laws of physics. In particular, the model shows that the the quantum computational universe automatically gives rise to a mix of randomness and order, and to both simple and complex systems.

preprint2013arXiv

Uncomputability and physical law

This article addresses the question of when physical laws and their consequences can be computed. If a physical system is capable of universal computation, then its energy gap can't be computed. At an even more fundamental level, the most concise, simply applicable formulation of the underlying laws of physics is uncomputable. That is, physicists are in the same boat as mathematicians: many quantities of interest can be computed, but not all.

preprint2012arXiv

Capacities of linear quantum optical systems

A wide variety of communication channels employ the quantized electromagnetic field to convey information. Their communication capacity crucially depends on losses associated to spatial characteristics of the channel such as diffraction and antenna design. Here we focus on the communication via a finite pupil, showing that diffraction is formally described as a memory channel. By exploiting this equivalence we then compute the communication capacity of an optical refocusing system, modeled as a converging lens. Even though loss of information originates from the finite pupil of the lens, we show that the presence of the refocusing system can substantially enhance the communication capacity. We mainly concentrate on communication of classical information, the extension to quantum information being straightforward.

preprint2012arXiv

Efficient estimation of energy transfer efficiency in light-harvesting complexes

The fundamental physical mechanisms of energy transfer in photosynthetic complexes is not yet fully understood. In particular, the degree of efficiency or sensitivity of these systems for energy transfer is not known given their non-perturbative and non-Markovian interactions with proteins backbone and surrounding photonic and phononic environments. One major problem in studying light-harvesting complexes has been the lack of an efficient method for simulation of their dynamics in biological environments. To this end, here we revisit the second-order time-convolution (TC2) master equation and examine its reliability beyond extreme Markovian and perturbative limits. In particular, we present a derivation of TC2 without making the usual weak system-bath coupling assumption. Using this equation, we explore the long time behaviour of exciton dynamics of Fenna-Matthews-Olson (FMO) protein complex. Moreover, we introduce a constructive error analysis to estimate the accuracy of TC2 equation in calculating energy transfer efficiency, exhibiting reliable performance for environments with weak and intermediate memory and strength. Furthermore, we numerically show that energy transfer efficiency is optimal and robust for the FMO protein complex of green sulphur bacteria with respect to variations in reorganization energy and bath correlation time-scales.

preprint2012arXiv

Electromagnetic channel capacity for practical purposes

We give analytic upper bounds to the channel capacity C for transmission of classical information in electromagnetic channels (bosonic channels with thermal noise). In the practically relevant regimes of high noise and low transmissivity, by comparison with know lower bounds on C, our inequalities determine the value of the capacity up to corrections which are irrelevant for all practical purposes. Examples of such channels are radio communication, infrared or visible-wavelength free space channels. We also provide bounds to active channels that include amplification.

preprint2012arXiv

Energy-scales convergence for optimal and robust quantum transport in photosynthetic complexes

Underlying physical principles for the high efficiency of excitation energy transfer in light-harvesting complexes are not fully understood. Notably, the degree of robustness of these systems for transporting energy is not known considering their realistic interactions with vibrational and radiative environments within the surrounding solvent and scaffold proteins. In this work, we employ an efficient technique to estimate energy transfer efficiency of such complex excitonic systems. We observe that the dynamics of the Fenna-Matthews-Olson (FMO) complex leads to optimal and robust energy transport due to a convergence of energy scales among all important internal and external parameters. In particular, we show that the FMO energy transfer efficiency is optimum and stable with respect to the relevant parameters of environmental interactions and Frenkel-exciton Hamiltonian including reorganization energy $λ$, bath frequency cutoff $γ$, temperature $T$, bath spatial correlations, initial excitations, dissipation rate, trapping rate, disorders, and dipole moments orientations. We identify the ratio of $λT/γ\*g$ as a single key parameter governing quantum transport efficiency, where g is the average excitonic energy gap.

preprint2012arXiv

Explicit capacity-achieving receivers for optical communication and quantum reading

An important practical open question has been to design explicit, structured optical receivers that achieve the Holevo limit in the contexts of optical communication and "quantum reading." The Holevo limit is an achievable rate that is higher than the Shannon limit of any known optical receiver. We demonstrate how a sequential decoding approach can achieve the Holevo limit for both of these settings. A crucial part of our scheme for both settings is a non-destructive "vacuum-or-not" measurement that projects an n-symbol modulated codeword onto the n-fold vacuum state or its orthogonal complement, such that the post-measurement state is either the n-fold vacuum or has the vacuum removed from the support of the n symbols' joint quantum state. The sequential decoder for optical communication requires the additional ability to perform multimode optical phase-space displacements---realizable using a beamsplitter and a laser, while the sequential decoder for quantum reading also requires the ability to perform phase-shifting (realizable using a phase plate) and online squeezing (a phase-sensitive amplifier).

preprint2012arXiv

Quantum Data Fitting

We provide a new quantum algorithm that efficiently determines the quality of a least-squares fit over an exponentially large data set by building upon an algorithm for solving systems of linear equations efficiently (Harrow et al., Phys. Rev. Lett. {\bf 103}, 150502 (2009)). In many cases, our algorithm can also efficiently find a concise function that approximates the data to be fitted and bound the approximation error. In cases where the input data is a pure quantum state, the algorithm can be used to provide an efficient parametric estimation of the quantum state and therefore can be applied as an alternative to full quantum state tomography given a fault tolerant quantum computer.

preprint2012arXiv

Quantum limits to the measurement of spacetime geometry

This letter analyzes the limits that quantum mechanics imposes on the accuracy to which spacetime geometry can be measured. By applying the physics of computation to ensembles of clocks, as in GPS, we present a covariant version of the quantum geometric limit, which states that the total number of ticks of clocks and clicks of detectors that can be contained in a four volume of spacetime of radius r and temporal extent t is less than or equal to rt/pi x_P t_P, where x_P, t_P are the Planck length and time. The quantum geometric bound limits the number of events or `ops' that can take place in a four-volume of spacetime and is consistent with and complementary to the holographic bound which limits the number of bits that can exist within a three-volume of spacetime.

preprint2012arXiv

The quantum geometric limit

In Einstein's gedankenexperiment for measuring space and time, an ensemble of clocks moving through curved spacetime measures geometry by sending signals back and forth, as in the global positioning system (GPS). Combining well-known quantum limits to measurement with the requirement that the energy density of clocks and signals be be no greater than the black hole density leads to the quantum geometric limit: the total number of ticks of clocks and clicks of detectors that can be contained in a four volume of spacetime of radius r and temporal extent t is less than or equal to rt/πl_P t_P, where l_P, t_P are the Planck length and time. The quantum geometric limit suggests that each event or `op' that takes place in a four-volume of spacetime is associated with a Planck-scale area. This paper shows that the quantum geometric limit can be used to derive general relativity: if each quantum event is associated with a Planck-scale area removed from two-dimensional surfaces in the volume in which the event takes place, then Einstein's equations must hold.

preprint2011arXiv

A reply to "Problems with modelling closed timelike curves as post-selected teleportation"

In arXiv:1107.4675 Ralph uses our post-selection model of closed timelike curves (P-CTC) to construct an "unproven-theorem" paradox, and claims that this voids our argument that P-CTCs are able to resolve such types of paradoxes. Here we point out that Ralph has not accounted for all the interactions needed for his construction. A more careful analysis confirms that indeed there is no paradox, contrary to his claims.

preprint2011arXiv

Advances in Quantum Metrology

In classical estimation theory, the central limit theorem implies that the statistical error in a measurement outcome can be reduced by an amount proportional to n^(-1/2) by repeating the measures n times and then averaging. Using quantum effects, such as entanglement, it is often possible to do better, decreasing the error by an amount proportional to 1/n. Quantum metrology is the study of those quantum techniques that allow one to gain advantages over purely classical approaches. In this review, we analyze some of the most promising recent developments in this research field. Specifically, we deal with the developments of the theory and point out some of the new experiments. Then we look at one of the main new trends of the field, the analysis of how the theory must take into account the presence of noise and experimental imperfections.

preprint2011arXiv

Enhanced Quantum Communication via Optical Refocusing

We consider the problem of quantum communication mediated by an optical refocusing system, which is schematized as a thin lens with a finite pupil. This model captures the basic features of all those situations in which a signal is either refocused by a repeater for long distance communication, or it is focused on a detector prior to the information decoding process. Introducing a general method for linear optical systems, we compute the communication capacity of the refocusing apparatus. Although the finite extension of the pupil may cause loss of information, we show that the presence of the refocusing system can substantially enhance the rate of reliable communication with respect to the free-space propagation.

preprint2011arXiv

Excitonic diffusion length in complex quantum systems: The effects of disorder and environmental fluctuations on symmetry-enhanced supertransfer

Symmetric couplings among aggregates of $n$ chromophores increase the transfer rate of excitons by a factor $n^2$, a quantum mechanical phenomenon called "supertransfer." In this work we demonstrate how supertransfer effects induced by geometrical symmetries can enhance the exciton diffusion length by a factor $n$ along cylindrically symmetric structures, consisting of arrays of rings of chromophores, and along spiral arrays. We analyse both closed system dynamics and open quantum dynamics, modelled by combining a random bosonic bath with static disorder. In the closed system case, we use the symmetries of the system within a short-time approximation to obtain a closed analytical expression for the diffusion length that explicitly reveals the supertransfer contribution. When subject to disorder, we show that supertransfer can enhance excitonic diffusion lengths for small disorders and characterize the crossover from coherent to incoherent motion. Owing to the quasi-1D nature of the model, disorder ultimately localizes the excitons, diminishing but not destroying the effects of supertransfer. When dephasing effects are included, we study the scaling of diffusion with both time and number of chromophores and observe that the transition from a coherent, ballistic regime to an incoherent, random-walk regime occurs at the same point as the change from supertransfer to classical scaling.

preprint2011arXiv

Gaussian Quantum Information

The science of quantum information has arisen over the last two decades centered on the manipulation of individual quanta of information, known as quantum bits or qubits. Quantum computers, quantum cryptography and quantum teleportation are among the most celebrated ideas that have emerged from this new field. It was realized later on that using continuous-variable quantum information carriers, instead of qubits, constitutes an extremely powerful alternative approach to quantum information processing. This review focuses on continuous-variable quantum information processes that rely on any combination of Gaussian states, Gaussian operations, and Gaussian measurements. Interestingly, such a restriction to the Gaussian realm comes with various benefits, since on the theoretical side, simple analytical tools are available and, on the experimental side, optical components effecting Gaussian processes are readily available in the laboratory. Yet, Gaussian quantum information processing opens the way to a wide variety of tasks and applications, including quantum communication, quantum cryptography, quantum computation, quantum teleportation, and quantum state and channel discrimination. This review reports on the state of the art in this field, ranging from the basic theoretical tools and landmark experimental realizations to the most recent successful developments.

preprint2011arXiv

Interplay between coherence and decoherence in LHCII photosynthetic complex

This paper investigates the dynamics of excitonic transport in photocomplex LHCII, the primary component of the photosynthetic apparatus in green plants. The dynamics exhibits a strong interplay between coherent processes mediated by the excitonic Hamiltonian, and incoherent processes due to interactions with the environment. The spreading of the exciton over a single monomer is well described by a proper measure of delocalization that allows one to identify two relevant time scales. An exciton initially localized in one chromophore first spreads coherently to neighboring chromophores. During this initial coherent spreading, quantum effects such as entanglement play a role. As the effects of a decohering environment come into play, coherence and decoherence interact to give rise to efficient and robust excitonic transport, reaching a maximum efficiency at the levels of decoherence found in physiological conditions. We analyze the efficiency for different possible topologies (monomer, dimer, trimer, tetramer) and show how the trimer has a particular role both in the antenna and the wire configuration.

preprint2011arXiv

Majorization theory approach to the Gaussian channel minimum entropy conjecture

A longstanding open problem in quantum information theory is to find the classical capacity of an optical communication link, modeled as a Gaussian bosonic channel. It has been conjectured that this capacity is achieved by a random coding of coherent states using an isotropic Gaussian distribution in phase space. We show that proving a Gaussian minimum entropy conjecture for a quantum-limited amplifier is actually sufficient to confirm this capacity conjecture, and we provide a strong argument towards this proof by exploiting a connection between quantum entanglement and majorization theory.

preprint2011arXiv

Quantum measurement bounds beyond the uncertainty relations

We give a bound to the precision in the estimation of a parameter in terms of the expectation value of an observable. It is an extension of the Cramer-Rao inequality and of the Heisenberg uncertainty relation, where the estimation precision is typically bounded in terms of the variance of an observable.

preprint2011arXiv

Sequential projective measurements for channel decoding

We study the transmission of classical information in quantum channels. We present a decoding procedure that is very simple but still achieves the channel capacity. It is used to give an alternative straightforward proof that the classical capacity is given by the regularized Holevo bound. This procedure uses only projective measurements and is based on successive "yes"/"no" tests only.

preprint2011arXiv

The quantum Goldilocks effect: on the convergence of timescales in quantum transport

Excitonic transport in photosynthesis exhibits a wide range of time scales. Absorption and initial relaxation takes place over tens of femtoseconds. Excitonic lifetimes are on the order of a nanosecond. Hopping rates, energy differences between chromophores, reorganization energies, and decoherence rates correspond to time scales on the order of picoseconds. The functional nature of the divergence of time scales is easily understood: strong coupling to the electromagnetic field over a broad band of frequencies yields rapid absorption, while long excitonic lifetimes increase the amount of energy that makes its way to the reaction center to be converted to chemical energy. The convergence of the remaining time scales to the centerpoint of the overall temporal range is harder to understand. In this paper we argue that the convergence of timescales in photosynthesis can be understood as an example of the `quantum Goldilocks effect': natural selection tends to drive quantum systems to the degree of quantum coherence that is `just right' for attaining maximum efficiency. We provide a general theory of optimal and robust, efficient transport in quantum systems, and show that it is governed by a single parameter.

preprint2010arXiv

A quantum Bose-Hubbard model with evolving graph as toy model for emergent spacetime

We present a toy model for interacting matter and geometry that explores quantum dynamics in a spin system as a precursor to a quantum theory of gravity. The model has no a priori geometric properties, instead, locality is inferred from the more fundamental notion of interaction between the matter degrees of freedom. The interaction terms are themselves quantum degrees of freedom so that the structure of interactions and hence the resulting local and causal structures are dynamical. The system is a Hubbard model where the graph of the interactions is a set of quantum evolving variables. We show entanglement between spatial and matter degrees of freedom. We study numerically the quantum system and analyze its entanglement dynamics. We analyze the asymptotic behavior of the classical model. Finally, we discuss analogues of trapped surfaces and gravitational attraction in this simple model.

preprint2010arXiv

Achieving the Holevo bound via sequential measurements

We present a new decoding procedure to transmit classical information in a quantum channel which, saturating asymptotically the Holevo bound, achieves the optimal rate of the communication line. Differently from previous proposals, it is based on performing a sequence of (projective) YES/NO measurements which in N steps determines which codeword was sent by the sender (N being the number of the codewords). Our analysis shows that as long as N is below the limit imposed by the Holevo bound the error probability can be sent to zero asymptotically in the length of the codewords.

preprint2010arXiv

Closed timelike curves via post-selection: theory and experimental demonstration

Closed timelike curves (CTCs) are trajectories in spacetime that effectively travel backwards in time: a test particle following a CTC can in principle interact with its former self in the past. CTCs appear in many solutions of Einstein's field equations and any future quantum version of general relativity will have to reconcile them with the requirements of quantum mechanics and of quantum field theory. A widely accepted quantum theory of CTCs was proposed by Deutsch. Here we explore an alternative quantum formulation of CTCs and show that it is physically inequivalent to Deutsch's. Because it is based on combining quantum teleportation with post-selection, the predictions/retrodictions of our theory are experimentally testable: we report the results of an experiment demonstrating our theory's resolution of the well-known `grandfather paradox.

preprint2010arXiv

Symmetry-enhanced supertransfer of delocalized quantum states

Coherent hopping of excitation rely on quantum coherence over physically extended states. In this work, we consider simple models to examine the effect of symmetries of delocalized multi-excitation states on the dynamical timescales, including hopping rates, radiative decay, and environmental interactions. While the decoherence (pure dephasing) rate of an extended state over N sites is comparable to that of a non-extended state, superradiance leads to a factor of N enhancement in decay and absorption rates. In addition to superradiance, we illustrate how the multi-excitonic states exhibit `supertransfer' in the far-field regime: hopping from a symmetrized state over N sites to a symmetrized state over M sites at a rate proportional to MN. We argue that such symmetries could play an operational role in physical systems based on the competition between symmetry-enhanced interactions and localized inhomogeneities and environmental interactions that destroy symmetry. As an example, we propose that supertransfer and coherent hopping play a role in recent observations of anomolously long diffusion lengths in nano-engineered assembly of light-harvesting complexes.

preprint2010arXiv

The quantum mechanics of time travel through post-selected teleportation

This paper discusses the quantum mechanics of closed timelike curves (CTC) and of other potential methods for time travel. We analyze a specific proposal for such quantum time travel, the quantum description of CTCs based on post-selected teleportation (P-CTCs). We compare the theory of P-CTCs to previously proposed quantum theories of time travel: the theory is physically inequivalent to Deutsch's theory of CTCs, but it is consistent with path-integral approaches (which are the best suited for analyzing quantum field theory in curved spacetime). We derive the dynamical equations that a chronology-respecting system interacting with a CTC will experience. We discuss the possibility of time travel in the absence of general relativistic closed timelike curves, and investigate the implications of P-CTCs for enhancing the power of computation.

preprint2009arXiv

Confidential direct communications: a quantum approach using continuous variables

We consider the problem of privacy in direct communications, showing how quantum mechanics can be useful to guarantee a certain level of confidentiality. In particular, we review a continuous variable approach recently proposed by us [S. Pirandola et al., Europhys. Lett. 84, 20013 (2008)]. Here, we analyze the degree of privacy of this technique against a broader class of attacks, which includes non-Gaussian eavesdropping.

preprint2009arXiv

Quantum illumination versus coherent-state target detection

Lloyd [1] proved that a large performance gain accrues from use of entanglement in single-photon target detection within a lossy, noisy environment when compared to what can be achieved with unentangled single-photon states. We show that the performance of Lloyd's "quantum illumination" system is, at best, equal to that of a coherent-state transmitter, and may be substantially worse. Nevertheless, as shown in [2], quantum illumination may offer a significant performance gain when operation is not limited to the single-photon regime.

preprint2009arXiv

Quantum state transfer through a qubit network with energy shifts and fluctuations

We study quantum state transfer through a qubit network modeled by spins with XY interaction, when relying on a single excitation. We show that it is possible to achieve perfect transfer by shifting (adding) energy to specific vertices. This technique appears to be a potentially powerful tool to change, and in some cases improve, transfer capabilities of quantum networks. Analytical results are presented for all-to-all networks and all-to-all networks with a missing link. Moreover, we evaluate the effect of random fluctuations on the transmission fidelity.

preprint2009arXiv

Reverse Coherent Information

In this letter we define a family of entanglement distribution protocols assisted by feedback classical communication that gives an operational interpretation to reverse coherent information, i.e., the symmetric counterpart of the well known coherent information. This lead to the definition of a new entanglement distribution capacity that exceeds the unassisted capacity for some interesting channels.

preprint2008arXiv

Landau-Zener Transitions in an Adiabatic Quantum Computer

We report an experimental measurement of Landau-Zener transitions on an individual flux qubit within a multi-qubit superconducting chip designed for adiabatic quantum computation. The method used isolates a single qubit, tunes its tunneling amplitude Delta into the limit where Delta is much less than both the temperature T and the decoherence-induced energy level broadening, and forces it to undergo a Landau-Zener transition. We find that the behavior of the qubit agrees to a high degree of accuracy with theoretical predictions for Landau-Zener transition probabilities for a double-well quantum system coupled to 1/f magnetic flux noise.

preprint2008arXiv

Quantum Private Queries: security analysis

We present a security analysis of the recently introduced Quantum Private Query (QPQ) protocol. It is a cheat sensitive quantum protocol to perform a private search on a classical database. It allows a user to retrieve an item from the database without revealing which item was retrieved, and at the same time it ensures data privacy of the database (the information that the user can retrieve in a query is bounded and does not depend on the size of the database). The security analysis is based on information-disturbance tradeoffs which show that whenever the provider tries to obtain information on the query, the query (encoded into a quantum system) is disturbed so that the person querying the database can detect the privacy violation.

preprint2006arXiv

Macroscopic Entanglement by Entanglement Swapping

We present a scheme for entangling two micromechanical oscillators. The scheme exploits the quantum effects of radiation pressure and it is based on a novel application of entanglement swapping, where standard optical measurements are used to generate purely mechanical entanglement. The scheme is presented by first solving the general problem of entanglement swapping between arbitrary bipartite Gaussian states, for which simple input-output formulas are provided.

preprint2003arXiv

Quantum tensor product structures are observable-induced

It is argued that the partition of a quantum system into subsystems is dictated by the set of operationally accessible interactions and measurements. The emergence of a multi-partite tensor product structure of the state-space and the associated notion of quantum entanglement are then relative and observable-induced. We develop a general algebraic framework aimed to formalize this concept. We discuss several cases relevant to quantum information processing and decoherence control.

preprint2003arXiv

Universal quantum control in irreducible state-space sectors: application to bosonic and spin-boson systems

We analyze the dynamical-algebraic approach to universal quantum control introduced in P. Zanardi, S. Lloyd, quant-ph/0305013. The quantum state-space $\cal H$ encoding information decomposes into irreducible sectors and subsystems associated to the group of available evolutions. If this group coincides with the unitary part of the group-algebra $\CC{\cal K}$ of some group $\cal K$ then universal control is achievable over the ${\cal K}$-irreducible components of $\cal H$. This general strategy is applied to different kind of bosonic systems. We first consider massive bosons in a double-well and show how to achieve universal control over all finite-dimensional Fock sectors. We then discuss a multi-mode massless case giving the conditions for generating the whole infinite-dimensional multi-mode Heisenberg-Weyl enveloping-algebra. Finally we show how to use an auxiliary bosonic mode coupled to finite-dimensional systems to generate high-order non-linearities needed for universal control.

preprint2000arXiv

Ultimate physical limits to computation

Computers are physical systems: what they can and cannot do is dictated by the laws of physics. In particular, the speed with which a physical device can process information is limited by its energy and the amount of information that it can process is limited by the number of degrees of freedom it possesses. This paper explores the physical limits of computation as determined by the speed of light $c$, the quantum scale $\hbar$ and the gravitational constant $G$. As an example, quantitative bounds are put to the computational power of an `ultimate laptop' with a mass of one kilogram confined to a volume of one liter.

preprint1999arXiv

Dynamical Decoupling of Open Quantum Systems

We propose a novel dynamical method for beating decoherence and dissipation in open quantum systems. We demonstrate the possibility of filtering out the effects of unwanted (not necessarily known) system-environment interactions and show that the noise-suppression procedure can be combined with the capability of retaining control over the effective dynamical evolution of the open quantum system. Implications for quantum information processing are discussed.

Seth Lloyd

What is connected

Connect this record

See the researcher in context

Building this map preview

92 published item(s)

Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis

Learning quantum data with the quantum Earth Mover's distance

Quantum advantage for differential equation analysis

Quantum algorithm for Petz recovery channels and pretty good measurements

Quantum algorithms for group convolution, cross-correlation, and equivariant transformations

Quantum Maxwell's Demon Assisted by Non-Markovian Effects

Resonant Quantum Principal Component Analysis

The Quantum Wasserstein Distance of Order 1

Learning Unitaries by Gradient Descent

Quantum Computer Systems for Scientific Discovery

Quantum embeddings for machine learning

Quantum Medical Imaging Algorithms

Quantum polar decomposition algorithm

Quantum transport simulations in a programmable nanophotonic processor

Quantum-inspired algorithms in practice

Dense coding capacity of a quantum channel

Optimization and learning of quantum programs

A Quantum Enigma Machine: Experimentally Demonstrating Quantum Data Locking

Chiral Quantum Walks

Decoherent histories approach to the cosmological measure problem

From clocks to cloners: Catalytic transformations under covariant operations and recoverability

Global coherence of quantum evolutions based on decoherent histories: theory and application to photosynthetic quantum energy transport

On the uncomputability of the spectral gap

Passive states as optimal inputs for single-jump lossy quantum channels

Quantum data hiding in the presence of noise

The power of one qumode for quantum computation

Time Independent Universal Computing with Spin Chains: Quantum Plinko Machine

Adiabatic and Hamiltonian computing on a 2D lattice with simple 2-qubit interactions

Any non-affine one-to-one binary gate suffices for computation

Continuous-variable quantum enigma machines for long-distance key distribution

Core-halo instability in dynamical systems

MDI-QKD: Continuous- versus discrete-variables at metropolitan distances

Quantum algorithms for topological and geometric analysis of big data

Quantum data locking for high-rate private communication

Quantum Time

The multi-mode quantum Entropy Power Inequality

Analysis of a work of quantum art

High-rate quantum cryptography in untrusted networks

Maximally strong entropic uncertainty relations and gauge invariance

Optimality of Gaussian Discord

Quantum brachistochrone curves as geodesics: obtaining accurate control protocols for time-optimal quantum gates

Quantum support vector machine for big data classification

Quantum-locked key distribution at nearly the classical capacity rate

Robust quantum data locking from phase modulation

Simplicial Ricci Flow: An Example of a Neck Pinch Singularity in 3D

Unitarity of black hole evaporation in final-state projection models

Universal quantum computation in integrable systems

A Turing test for free will

Marcus rate for electron transfer and the Goldilocks principle

Pure state quantum statistical mechanics and black holes

Quantum algorithms for supervised and unsupervised machine learning

Quantum Cryptography Approaching the Classical Limit

Quantum enigma machines

Quantum enigma machines and the locking capacity of a quantum channel

Quantum principal component analysis

The universal path integral

The universe as quantum computer

Uncomputability and physical law

Capacities of linear quantum optical systems

Efficient estimation of energy transfer efficiency in light-harvesting complexes

Electromagnetic channel capacity for practical purposes

Energy-scales convergence for optimal and robust quantum transport in photosynthetic complexes

Explicit capacity-achieving receivers for optical communication and quantum reading

Quantum Data Fitting

Quantum limits to the measurement of spacetime geometry

The quantum geometric limit

A reply to "Problems with modelling closed timelike curves as post-selected teleportation"

Advances in Quantum Metrology

Enhanced Quantum Communication via Optical Refocusing

Excitonic diffusion length in complex quantum systems: The effects of disorder and environmental fluctuations on symmetry-enhanced supertransfer

Gaussian Quantum Information

Interplay between coherence and decoherence in LHCII photosynthetic complex

Majorization theory approach to the Gaussian channel minimum entropy conjecture

Quantum measurement bounds beyond the uncertainty relations