-
Benchmarking bosonic and fermionic dynamics
Authors:
Jadwiga Wilkens,
Marios Ioannou,
Ellen Derbyshire,
Jens Eisert,
Dominik Hangleiter,
Ingo Roth,
Jonas Haferkamp
Abstract:
Analog quantum simulation allows for assessing static and dynamical properties of strongly correlated quantum systems to high precision. To perform simulations outside the reach of classical computers, accurate and reliable implementations of the anticipated Hamiltonians are required. To achieve those, characterization and benchmarking tools are a necessity. For digital quantum devices, randomized…
▽ More
Analog quantum simulation allows for assessing static and dynamical properties of strongly correlated quantum systems to high precision. To perform simulations outside the reach of classical computers, accurate and reliable implementations of the anticipated Hamiltonians are required. To achieve those, characterization and benchmarking tools are a necessity. For digital quantum devices, randomized benchmarking can provide a benchmark on the average quality of the implementation of a gate set. In this work, we introduce a versatile framework for randomized analog benchmarking of bosonic and fermionic quantum devices implementing particle number preserving dynamics. The scheme makes use of the restricted operations which are native to analog simulators and other continuous variable systems. Importantly, like randomized benchmarking, it is robust against state preparation and measurement errors. We discuss the scheme's efficiency, derive theoretical performance guarantees and showcase the protocol with numerical examples.
△ Less
Submitted 20 August, 2024;
originally announced August 2024.
-
Efficient distributed inner product estimation via Pauli sampling
Authors:
Marcel Hinsche,
Marios Ioannou,
Sofiene Jerbi,
Lorenzo Leone,
Jens Eisert,
Jose Carrasco
Abstract:
Cross-platform verification is the task of comparing the output states produced by different physical platforms using solely local quantum operations and classical communication. While protocols have previously been suggested for this task, their exponential sample complexity renders them unpractical even for intermediate-scale quantum systems. In this work, we propose a novel protocol for this ta…
▽ More
Cross-platform verification is the task of comparing the output states produced by different physical platforms using solely local quantum operations and classical communication. While protocols have previously been suggested for this task, their exponential sample complexity renders them unpractical even for intermediate-scale quantum systems. In this work, we propose a novel protocol for this task based on Pauli sampling, a subroutine which generates Paulis distributed according to their weight in the expansion of a quantum state in the Pauli basis. We show that our protocols for both Pauli sampling and cross-platform verification are efficient for quantum states with low magic and entanglement (i.e., of the order $O(\log n)$). Conversely, we show super-polynomial lower bounds on the complexity of both tasks for states with $ω(\log n)$ magic and entanglement. Interestingly, when considering states with real amplitudes the requirements of our protocol for cross-platform verification can be significantly weakened.
△ Less
Submitted 19 August, 2024; v1 submitted 10 May, 2024;
originally announced May 2024.
-
Joint-measurability and quantum communication with untrusted devices
Authors:
Michele Masini,
Marie Ioannou,
Nicolas Brunner,
Stefano Pironio,
Pavel Sekatski
Abstract:
Photon loss represents a major challenge for the implementation of quantum communication protocols with untrusted devices, e.g. in the device-independent (DI) or semi-DI approaches. Determining critical loss thresholds is usually done in case-by-case studies. In the present work, we develop a general framework for characterizing the admissible levels of loss and noise in a wide range of scenarios…
▽ More
Photon loss represents a major challenge for the implementation of quantum communication protocols with untrusted devices, e.g. in the device-independent (DI) or semi-DI approaches. Determining critical loss thresholds is usually done in case-by-case studies. In the present work, we develop a general framework for characterizing the admissible levels of loss and noise in a wide range of scenarios and protocols with untrusted measurement devices. In particular, we present general bounds that apply to prepare-and-measure protocols for the semi-DI approach, as well as to Bell tests for DI protocols. A key step in our work is to establish a general connection between quantum protocols with untrusted measurement devices and the fundamental notions of channel extendibility and joint-measurability, which capture essential aspects of the communication and measurement of quantum information. In particular, this leads us to introduce the notion of partial joint-measurability, which naturally arises within quantum cryptography.
△ Less
Submitted 21 March, 2024;
originally announced March 2024.
-
Noise-mitigated randomized measurements and self-calibrating shadow estimation
Authors:
E. Onorati,
J. Kitzinger,
J. Helsen,
M. Ioannou,
A. H. Werner,
I. Roth,
J. Eisert
Abstract:
Randomized measurements are increasingly appreciated as powerful tools to estimate properties of quantum systems, e.g., in the characterization of hybrid classical-quantum computation. On many platforms they constitute natively accessible measurements, serving as the building block of prominent schemes like shadow estimation. In the real world, however, the implementation of the random gates at th…
▽ More
Randomized measurements are increasingly appreciated as powerful tools to estimate properties of quantum systems, e.g., in the characterization of hybrid classical-quantum computation. On many platforms they constitute natively accessible measurements, serving as the building block of prominent schemes like shadow estimation. In the real world, however, the implementation of the random gates at the core of these schemes is susceptible to various sources of noise and imperfections, strongly limiting the applicability of protocols. To attenuate the impact of this shortcoming, in this work we introduce an error-mitigated method of randomized measurements, giving rise to a robust shadow estimation procedure. On the practical side, we show that error mitigation and shadow estimation can be carried out using the same session of quantum experiments, hence ensuring that we can address and mitigate the noise affecting the randomization measurements. Mathematically, we develop a picture derived from Fourier-transforms to connect randomized benchmarking and shadow estimation. We prove rigorous performance guarantees and show the functioning using comprehensive numerics. More conceptually, we demonstrate that, if properly used, easily accessible data from randomized benchmarking schemes already provide such valuable diagnostic information to inform about the noise dynamics and to assist in quantum learning procedures.
△ Less
Submitted 7 March, 2024;
originally announced March 2024.
-
Classical Verification of Quantum Learning
Authors:
Matthias C. Caro,
Marcel Hinsche,
Marios Ioannou,
Alexander Nietner,
Ryan Sweke
Abstract:
Quantum data access and quantum processing can make certain classically intractable learning tasks feasible. However, quantum capabilities will only be available to a select few in the near future. Thus, reliable schemes that allow classical clients to delegate learning to untrusted quantum servers are required to facilitate widespread access to quantum learning advantages. Building on a recently…
▽ More
Quantum data access and quantum processing can make certain classically intractable learning tasks feasible. However, quantum capabilities will only be available to a select few in the near future. Thus, reliable schemes that allow classical clients to delegate learning to untrusted quantum servers are required to facilitate widespread access to quantum learning advantages. Building on a recently introduced framework of interactive proof systems for classical machine learning, we develop a framework for classical verification of quantum learning. We exhibit learning problems that a classical learner cannot efficiently solve on their own, but that they can efficiently and reliably solve when interacting with an untrusted quantum prover. Concretely, we consider the problems of agnostic learning parities and Fourier-sparse functions with respect to distributions with uniform input marginal. We propose a new quantum data access model that we call "mixture-of-superpositions" quantum examples, based on which we give efficient quantum learning algorithms for these tasks. Moreover, we prove that agnostic quantum parity and Fourier-sparse learning can be efficiently verified by a classical verifier with only random example or statistical query access. Finally, we showcase two general scenarios in learning and verification in which quantum mixture-of-superpositions examples do not lead to sample complexity improvements over classical data. Our results demonstrate that the potential power of quantum data for learning tasks, while not unlimited, can be utilized by classical agents through interaction with untrusted quantum entities.
△ Less
Submitted 7 December, 2023; v1 submitted 7 June, 2023;
originally announced June 2023.
-
On the average-case complexity of learning output distributions of quantum circuits
Authors:
Alexander Nietner,
Marios Ioannou,
Ryan Sweke,
Richard Kueng,
Jens Eisert,
Marcel Hinsche,
Jonas Haferkamp
Abstract:
In this work, we show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model. This learning model is widely used as an abstract computational model for most generic learning algorithms. In particular, for brickwork random quantum circuits on $n$ qubits of depth $d$, we show three main results:
- At super logarithmic circuit…
▽ More
In this work, we show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model. This learning model is widely used as an abstract computational model for most generic learning algorithms. In particular, for brickwork random quantum circuits on $n$ qubits of depth $d$, we show three main results:
- At super logarithmic circuit depth $d=ω(\log(n))$, any learning algorithm requires super polynomially many queries to achieve a constant probability of success over the randomly drawn instance.
- There exists a $d=O(n)$, such that any learning algorithm requires $Ω(2^n)$ queries to achieve a $O(2^{-n})$ probability of success over the randomly drawn instance.
- At infinite circuit depth $d\to\infty$, any learning algorithm requires $2^{2^{Ω(n)}}$ many queries to achieve a $2^{-2^{Ω(n)}}$ probability of success over the randomly drawn instance.
As an auxiliary result of independent interest, we show that the output distribution of a brickwork random quantum circuit is constantly far from any fixed distribution in total variation distance with probability $1-O(2^{-n})$, which confirms a variant of a conjecture by Aaronson and Chen.
△ Less
Submitted 9 May, 2023;
originally announced May 2023.
-
Towards the device-independent certification of a quantum memory
Authors:
Pavel Sekatski,
Jean-Daniel Bancal,
Marie Ioannou,
Mikael Afzelius,
Nicolas Brunner
Abstract:
Quantum memories represent one of the main ingredients of future quantum communication networks. Their certification is therefore a key challenge. Here we develop efficient certification methods for quantum memories. Considering a device-independent approach, where no a priori characterisation of sources or measurement devices is required, we develop a robust self-testing method for quantum memori…
▽ More
Quantum memories represent one of the main ingredients of future quantum communication networks. Their certification is therefore a key challenge. Here we develop efficient certification methods for quantum memories. Considering a device-independent approach, where no a priori characterisation of sources or measurement devices is required, we develop a robust self-testing method for quantum memories. We then illustrate the practical relevance of our technique in a relaxed scenario by certifying a fidelity of 0.87 in a recent solid-state ensemble quantum memory experiment. More generally, our methods apply for the characterisation of any device implementing a qubit identity quantum channel.
△ Less
Submitted 25 April, 2023; v1 submitted 20 April, 2023;
originally announced April 2023.
-
Shallow shadows: Expectation estimation using low-depth random Clifford circuits
Authors:
Christian Bertoni,
Jonas Haferkamp,
Marcel Hinsche,
Marios Ioannou,
Jens Eisert,
Hakop Pashayan
Abstract:
We provide practical and powerful schemes for learning many properties of an unknown n-qubit quantum state using a sparing number of copies of the state. Specifically, we present a depth-modulated randomized measurement scheme that interpolates between two known classical shadows schemes based on random Pauli measurements and random Clifford measurements. These can be seen within our scheme as the…
▽ More
We provide practical and powerful schemes for learning many properties of an unknown n-qubit quantum state using a sparing number of copies of the state. Specifically, we present a depth-modulated randomized measurement scheme that interpolates between two known classical shadows schemes based on random Pauli measurements and random Clifford measurements. These can be seen within our scheme as the special cases of zero and infinite depth, respectively. We focus on the regime where depth scales logarithmically in n and provide evidence that this retains the desirable properties of both extremal schemes whilst, in contrast to the random Clifford scheme, also being experimentally feasible. We present methods for two key tasks; estimating expectation values of certain observables from generated classical shadows and, computing upper bounds on the depth-modulated shadow norm, thus providing rigorous guarantees on the accuracy of the output estimates. We consider observables that can be written as a linear combination of poly(n) Paulis and observables that can be written as a low bond dimension matrix product operator. For the former class of observables both tasks are solved efficiently in n. For the latter class, we do not guarantee efficiency but present a method that works in practice; by variationally computing a heralded approximate inverses of a tensor network that can then be used for efficiently executing both these tasks.
△ Less
Submitted 11 April, 2023; v1 submitted 26 September, 2022;
originally announced September 2022.
-
Equivalence between simulability of high-dimensional measurements and high-dimensional steering
Authors:
Benjamin D. M. Jones,
Roope Uola,
Thomas Cope,
Marie Ioannou,
Sébastien Designolle,
Pavel Sekatski,
Nicolas Brunner
Abstract:
The effect of quantum steering arises from the judicious combination of an entangled state with a set of incompatible measurements. Recently, it was shown that this form of quantum correlations can be quantified in terms of a dimension, leading to the notion of genuine high-dimensional steering. While this naturally connects to the dimensionality of entanglement (Schmidt number), we show that this…
▽ More
The effect of quantum steering arises from the judicious combination of an entangled state with a set of incompatible measurements. Recently, it was shown that this form of quantum correlations can be quantified in terms of a dimension, leading to the notion of genuine high-dimensional steering. While this naturally connects to the dimensionality of entanglement (Schmidt number), we show that this effect also directly connects to a notion of dimension for measurement incompatibility. More generally, we present a general connection between the concepts of steering and measurement incompatibility, when quantified in terms of dimension. From this connection, we propose a novel twist on the problem of simulating quantum correlations. Specifically, we show how the correlations of certain high-dimensional entangled states can be exactly recovered using only shared randomness and lower-dimensional entanglement. Finally, we derive criteria for testing the dimension of measurement incompatibility, and discuss the extension of these ideas to quantum channels.
△ Less
Submitted 8 July, 2022;
originally announced July 2022.
-
A single $T$-gate makes distribution learning hard
Authors:
Marcel Hinsche,
Marios Ioannou,
Alexander Nietner,
Jonas Haferkamp,
Yihui Quek,
Dominik Hangleiter,
Jean-Pierre Seifert,
Jens Eisert,
Ryan Sweke
Abstract:
The task of learning a probability distribution from samples is ubiquitous across the natural sciences. The output distributions of local quantum circuits form a particularly interesting class of distributions, of key importance both to quantum advantage proposals and a variety of quantum machine learning algorithms. In this work, we provide an extensive characterization of the learnability of the…
▽ More
The task of learning a probability distribution from samples is ubiquitous across the natural sciences. The output distributions of local quantum circuits form a particularly interesting class of distributions, of key importance both to quantum advantage proposals and a variety of quantum machine learning algorithms. In this work, we provide an extensive characterization of the learnability of the output distributions of local quantum circuits. Our first result yields insight into the relationship between the efficient learnability and the efficient simulatability of these distributions. Specifically, we prove that the density modelling problem associated with Clifford circuits can be efficiently solved, while for depth $d=n^{Ω(1)}$ circuits the injection of a single $T$-gate into the circuit renders this problem hard. This result shows that efficient simulatability does not imply efficient learnability. Our second set of results provides insight into the potential and limitations of quantum generative modelling algorithms. We first show that the generative modelling problem associated with depth $d=n^{Ω(1)}$ local quantum circuits is hard for any learning algorithm, classical or quantum. As a consequence, one cannot use a quantum algorithm to gain a practical advantage for this task. We then show that, for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=ω(\log(n))$ Clifford circuits is hard. This result places limitations on the applicability of near-term hybrid quantum-classical generative modelling algorithms.
△ Less
Submitted 7 July, 2022;
originally announced July 2022.
-
Simulability of high-dimensional quantum measurements
Authors:
Marie Ioannou,
Pavel Sekatski,
Sébastien Designolle,
Benjamin D. M. Jones,
Roope Uola,
Nicolas Brunner
Abstract:
We investigate the compression of quantum information with respect to a given set $\mathcal{M}$ of high-dimensional measurements. This leads to a notion of simulability, where we demand that the statistics obtained from $\mathcal{M}$ and an arbitrary quantum state $ρ$ are recovered exactly by first compressing $ρ$ into a lower dimensional space, followed by some quantum measurements. A full quantu…
▽ More
We investigate the compression of quantum information with respect to a given set $\mathcal{M}$ of high-dimensional measurements. This leads to a notion of simulability, where we demand that the statistics obtained from $\mathcal{M}$ and an arbitrary quantum state $ρ$ are recovered exactly by first compressing $ρ$ into a lower dimensional space, followed by some quantum measurements. A full quantum compression is possible, i.e., leaving only classical information, if and only if the set $\mathcal{M}$ is jointly measurable. Our notion of simulability can thus be seen as a quantification of measurement incompatibility in terms of dimension. After defining these concepts, we provide an illustrative examples involving mutually unbiased basis, and develop a method based on semi-definite programming for constructing simulation models. In turn we analytically construct optimal simulation models for all projective measurements subjected to white noise or losses. Finally, we discuss how our approach connects with other concepts introduced in the context of quantum channels and quantum correlations.
△ Less
Submitted 25 February, 2022;
originally announced February 2022.
-
Noncommutative polynomial optimization under symmetry
Authors:
Marie Ioannou,
Denis Rosset
Abstract:
We present a general framework to exploit the symmetries present in the Navascu{é}s-Pironio-Ac{í}n semidefinite relaxations that approximate invariant noncommutative polynomial optimization problems. We put equal emphasis on the moment and sum-of-squares dual approaches, and provide a pedagogical and formal introduction to the Navascu{é}s-Pironio-Ac{í}n technique before working out the impact of s…
▽ More
We present a general framework to exploit the symmetries present in the Navascu{é}s-Pironio-Ac{í}n semidefinite relaxations that approximate invariant noncommutative polynomial optimization problems. We put equal emphasis on the moment and sum-of-squares dual approaches, and provide a pedagogical and formal introduction to the Navascu{é}s-Pironio-Ac{í}n technique before working out the impact of symmetries present in the problem. Using our formalism, we compute analytical sum-of-square certificates for various Bell inequalities, and prove a long-standing conjecture about the exact maximal quantum violation of the CGLMP inequalities for dimension 3 and 4. We also apply our technique to the Sliwa inequalities in the Bell scenario with three parties with binary measurements settings/outcomes. Symmetry reduction is key to scale the applications of the NPA relaxation, and our formalism encompasses and generalizes the approaches found in the literature.
△ Less
Submitted 30 June, 2022; v1 submitted 20 December, 2021;
originally announced December 2021.
-
Steering-based randomness certification with squeezed states and homodyne measurements
Authors:
Marie Ioannou,
Bradley Longstaff,
Mikkel V. Larsen,
Jonas S. Neergaard-Nielsen,
Ulrik L. Andersen,
Daniel Cavalcanti,
Nicolas Brunner,
Jonatan Bohr Brask
Abstract:
We present a scheme for quantum randomness certification based on quantum steering. The protocol is one-sided device independent, providing high security, but requires only states and measurements that are simple to realise on quantum optics platforms - entangled squeezed vacuum states and homodyne detection. This ease of implementation is demonstrated by certifying randomness in existing experime…
▽ More
We present a scheme for quantum randomness certification based on quantum steering. The protocol is one-sided device independent, providing high security, but requires only states and measurements that are simple to realise on quantum optics platforms - entangled squeezed vacuum states and homodyne detection. This ease of implementation is demonstrated by certifying randomness in existing experimental data and implies that giga-hertz random bit rates should be attainable with current technology. Furthermore, the steering-based setting represents the closest to full device independence that can be achieved using purely Gaussian states and measurements.
△ Less
Submitted 24 November, 2022; v1 submitted 11 November, 2021;
originally announced November 2021.
-
Receiver-Device-Independent Quantum Key Distribution Protocols
Authors:
Marie Ioannou,
Pavel Sekatski,
Alastair A. Abbott,
Denis Rosset,
Jean-Daniel Bancal,
Nicolas Brunner
Abstract:
We discuss quantum key distribution protocols and their security analysis, considering a receiver-device-independent (RDI) model. The sender's (Alice's) device is partially characterized, in the sense that we assume bounds on the overlaps of the prepared quantum states. The receiver's (Bob's) device requires no characterisation and can be represented as a black-box. Our protocols are therefore rob…
▽ More
We discuss quantum key distribution protocols and their security analysis, considering a receiver-device-independent (RDI) model. The sender's (Alice's) device is partially characterized, in the sense that we assume bounds on the overlaps of the prepared quantum states. The receiver's (Bob's) device requires no characterisation and can be represented as a black-box. Our protocols are therefore robust to any attack on Bob, such as blinding attacks. In particular, we show that a secret key can be established even when the quantum channel has arbitrarily low transmission by considering RDI protocols exploiting sufficiently many states. Finally, we discuss how the hypothesis of bounded overlaps can be naturally applied to practical devices.
△ Less
Submitted 8 July, 2022; v1 submitted 8 November, 2021;
originally announced November 2021.
-
Estimating gate-set properties from random sequences
Authors:
J. Helsen,
M. Ioannou,
J. Kitzinger,
E. Onorati,
A. H. Werner,
J. Eisert,
I. Roth
Abstract:
With quantum computing devices increasing in scale and complexity, there is a growing need for tools that obtain precise diagnostic information about quantum operations. However, current quantum devices are only capable of short unstructured gate sequences followed by native measurements. We accept this limitation and turn it into a new paradigm for characterizing quantum gate-sets. A single exper…
▽ More
With quantum computing devices increasing in scale and complexity, there is a growing need for tools that obtain precise diagnostic information about quantum operations. However, current quantum devices are only capable of short unstructured gate sequences followed by native measurements. We accept this limitation and turn it into a new paradigm for characterizing quantum gate-sets. A single experiment - random sequence estimation - solves a wealth of estimation problems, with all complexity moved to classical post-processing. We derive robust channel variants of shadow estimation with close-to-optimal performance guarantees and use these as a primitive for partial, compressive and full process tomography as well as the learning of Pauli noise. We discuss applications to the quantum gate engineering cycle, and propose novel methods for the optimization of quantum gates and diagnosing cross-talk.
△ Less
Submitted 31 August, 2023; v1 submitted 25 October, 2021;
originally announced October 2021.
-
Learnability of the output distributions of local quantum circuits
Authors:
Marcel Hinsche,
Marios Ioannou,
Alexander Nietner,
Jonas Haferkamp,
Yihui Quek,
Dominik Hangleiter,
Jean-Pierre Seifert,
Jens Eisert,
Ryan Sweke
Abstract:
There is currently a large interest in understanding the potential advantages quantum devices can offer for probabilistic modelling. In this work we investigate, within two different oracle models, the probably approximately correct (PAC) learnability of quantum circuit Born machines, i.e., the output distributions of local quantum circuits. We first show a negative result, namely, that the output…
▽ More
There is currently a large interest in understanding the potential advantages quantum devices can offer for probabilistic modelling. In this work we investigate, within two different oracle models, the probably approximately correct (PAC) learnability of quantum circuit Born machines, i.e., the output distributions of local quantum circuits. We first show a negative result, namely, that the output distributions of super-logarithmic depth Clifford circuits are not sample-efficiently learnable in the statistical query model, i.e., when given query access to empirical expectation values of bounded functions over the sample space. This immediately implies the hardness, for both quantum and classical algorithms, of learning from statistical queries the output distributions of local quantum circuits using any gate set which includes the Clifford group. As many practical generative modelling algorithms use statistical queries -- including those for training quantum circuit Born machines -- our result is broadly applicable and strongly limits the possibility of a meaningful quantum advantage for learning the output distributions of local quantum circuits. As a positive result, we show that in a more powerful oracle model, namely when directly given access to samples, the output distributions of local Clifford circuits are computationally efficiently PAC learnable by a classical learner. Our results are equally applicable to the problems of learning an algorithm for generating samples from the target distribution (generative modelling) and learning an algorithm for evaluating its probabilities (density modelling). They provide the first rigorous insights into the learnability of output distributions of local quantum circuits from the probabilistic modelling perspective.
△ Less
Submitted 11 October, 2021;
originally announced October 2021.
-
Receiver-Device-Independent Quantum Key Distribution
Authors:
Marie Ioannou,
Maria Ana Pereira,
Davide Rusca,
Fadri Grünenfelder,
Alberto Boaron,
Matthieu Perrenoud,
Alastair A. Abbott,
Pavel Sekatski,
Jean-Daniel Bancal,
Nicolas Maring,
Hugo Zbinden,
Nicolas Brunner
Abstract:
We present protocols for quantum key distribution in a prepare-and-measure setup with an asymmetric level of trust. While the device of the sender (Alice) is partially characterized, the receiver's (Bob's) device is treated as a black-box. The security of the protocols is based on the assumption that Alice's prepared states have limited overlaps, but no explicit bound on the Hilbert space dimensio…
▽ More
We present protocols for quantum key distribution in a prepare-and-measure setup with an asymmetric level of trust. While the device of the sender (Alice) is partially characterized, the receiver's (Bob's) device is treated as a black-box. The security of the protocols is based on the assumption that Alice's prepared states have limited overlaps, but no explicit bound on the Hilbert space dimension is required. The protocols are immune to attacks on the receiver's device, such as blinding attacks. The users can establish a secret key while continuously monitoring the correct functioning of their devices through observed statistics. We report a proof-of-principle demonstration, involving mostly off-the-shelf equipment, as well as a high-efficiency superconducting nanowire detector. A positive key rate is demonstrated over a 4.8 km low-loss optical fiber with finite-key analysis. The prospects of implementing these protocols over longer distances is discussed.
△ Less
Submitted 18 May, 2022; v1 submitted 29 April, 2021;
originally announced April 2021.
-
Quantum Computational Advantage via High-Dimensional Gaussian Boson Sampling
Authors:
Abhinav Deshpande,
Arthur Mehta,
Trevor Vincent,
Nicolas Quesada,
Marcel Hinsche,
Marios Ioannou,
Lars Madsen,
Jonathan Lavoie,
Haoyu Qi,
Jens Eisert,
Dominik Hangleiter,
Bill Fefferman,
Ish Dhand
Abstract:
Photonics is a promising platform for demonstrating a quantum computational advantage (QCA) by outperforming the most powerful classical supercomputers on a well-defined computational task. Despite this promise, existing proposals and demonstrations face challenges. Experimentally, current implementations of Gaussian boson sampling (GBS) lack programmability or have prohibitive loss rates. Theoret…
▽ More
Photonics is a promising platform for demonstrating a quantum computational advantage (QCA) by outperforming the most powerful classical supercomputers on a well-defined computational task. Despite this promise, existing proposals and demonstrations face challenges. Experimentally, current implementations of Gaussian boson sampling (GBS) lack programmability or have prohibitive loss rates. Theoretically, there is a comparative lack of rigorous evidence for the classical hardness of GBS. In this work, we make progress in improving both the theoretical evidence and experimental prospects. We provide evidence for the hardness of GBS, comparable to the strongest theoretical proposals for QCA. We also propose a new QCA architecture we call high-dimensional GBS, which is programmable and can be implemented with low loss using few optical components. We show that particular algorithms for simulating GBS are outperformed by high-dimensional GBS experiments at modest system sizes. This work thus opens the path to demonstrating QCA with programmable photonic processors.
△ Less
Submitted 28 January, 2022; v1 submitted 24 February, 2021;
originally announced February 2021.
-
Termwise versus globally stoquastic local Hamiltonians: questions of complexity and sign-curing
Authors:
Marios Ioannou,
Stephen Piddock,
Milad Marvian,
Joel Klassen,
Barbara M. Terhal
Abstract:
We elucidate the distinction between global and termwise stoquasticity for local Hamiltonians and prove several complexity results. We show that the stoquastic local Hamiltonian problem is $\textbf{StoqMA}$-complete even for globally stoquastic Hamiltonians. We study the complexity of deciding whether a local Hamiltonian is globally stoquastic or not. In particular, we prove $\textbf{coNP}$-hardne…
▽ More
We elucidate the distinction between global and termwise stoquasticity for local Hamiltonians and prove several complexity results. We show that the stoquastic local Hamiltonian problem is $\textbf{StoqMA}$-complete even for globally stoquastic Hamiltonians. We study the complexity of deciding whether a local Hamiltonian is globally stoquastic or not. In particular, we prove $\textbf{coNP}$-hardness of deciding global stoquasticity in a fixed basis and $Σ_2^p$-hardness of deciding global stoquasticity under single-qubit transformations. As a last result, we expand the class of sign-curing transformations by showing how Clifford transformations can sign-cure a class of disordered 1D $XYZ$ Hamiltonians.
△ Less
Submitted 27 April, 2022; v1 submitted 23 July, 2020;
originally announced July 2020.
-
Hardness and Ease of Curing the Sign Problem for Two-Local Qubit Hamiltonians
Authors:
Joel Klassen,
Milad Marvian,
Stephen Piddock,
Marios Ioannou,
Itay Hen,
Barbara Terhal
Abstract:
We examine the problem of determining whether a multi-qubit two-local Hamiltonian can be made stoquastic by single-qubit unitary transformations. We prove that when such a Hamiltonian contains one-local terms, then this task can be NP-hard. This is shown by constructing a class of Hamiltonians for which performing this task is equivalent to deciding $3$-SAT. In contrast, we show that when such a H…
▽ More
We examine the problem of determining whether a multi-qubit two-local Hamiltonian can be made stoquastic by single-qubit unitary transformations. We prove that when such a Hamiltonian contains one-local terms, then this task can be NP-hard. This is shown by constructing a class of Hamiltonians for which performing this task is equivalent to deciding $3$-SAT. In contrast, we show that when such a Hamiltonian contains no one-local terms then this task is easy, namely we present an algorithm which decides, in a number of arithmetic operations over $\mathbb{R}$ which is polynomial in the number of qubits, whether the sign problem of the Hamiltonian can be cured by single-qubit rotations.
△ Less
Submitted 4 April, 2020; v1 submitted 20 June, 2019;
originally announced June 2019.
-
How much randomness can be generated from a quantum black-box device?
Authors:
Marie Ioannou,
Jonatan Bohr Brask,
Nicolas Brunner
Abstract:
Quantum theory allows for randomness generation in a device-independent setting, where no detailed description of the experimental device is required. Here we derive a general upper bound on the amount of randomness that can be generated in such a setting. Our bound applies to any black-box scenario, thus covering a wide range of scenarios from partially characterised to completely uncharacterised…
▽ More
Quantum theory allows for randomness generation in a device-independent setting, where no detailed description of the experimental device is required. Here we derive a general upper bound on the amount of randomness that can be generated in such a setting. Our bound applies to any black-box scenario, thus covering a wide range of scenarios from partially characterised to completely uncharacterised devices. Specifically, we prove that the number of random bits that can be generated is limited by the number of different input states that enter the measurement device. We show explicitly that our bound is tight in the simplest case. More generally, our work indicates that the prospects of generating a large amount of randomness by using high-dimensional (or even continuous variable) systems will be extremely challenging in practice.
△ Less
Submitted 20 November, 2018; v1 submitted 6 November, 2018;
originally announced November 2018.
-
Floquet dynamics in quantum measurement of mechanical motion
Authors:
Liu Qiu,
Itay Shomroni,
Marie A. Ioannou,
Nicolas Piro,
Daniel Malz,
Andreas Nunnenkamp,
Tobias J. Kippenberg
Abstract:
The radiation-pressure interaction between one or more laser fields and a mechanical oscillator gives rise to a wide range of phenomena: from sideband cooling and backaction-evading measurements to pondermotive and mechanical squeezing to entanglement and motional sideband asymmetry. In many protocols, such as dissipative mechanical squeezing, multiple lasers are utilized, giving rise to periodica…
▽ More
The radiation-pressure interaction between one or more laser fields and a mechanical oscillator gives rise to a wide range of phenomena: from sideband cooling and backaction-evading measurements to pondermotive and mechanical squeezing to entanglement and motional sideband asymmetry. In many protocols, such as dissipative mechanical squeezing, multiple lasers are utilized, giving rise to periodically driven optomechanical systems. Here we show that in this case, Floquet dynamics can arise due to presence of Kerr-type nonlinearities, which are ubiqitious in optomechanical systems. Specifically, employing multiple probe tones, we perform sideband asymmetry measurements, a macroscopic quantum effect, on a silicon optomechanical crystal sideband-cooled to 40% ground-state occupation. We show that the Floquet dynamics, resulting from the presence of multiple pump tones, gives rise to an artificially modified motional sideband asymmetry by redistributing thermal and quantum fluctuations among the initially independently scattered thermomechanical sidebands. For pump tones exhibiting large frequency separation, the dynamics is suppressed and accurate quantum noise thermometry demonstrated. We develop a theoretical model based on Floquet theory that accurately describes our observations. The resulting dynamics can be understood as resulting from a synthetic gauge field among the Fourier modes, which is created by the phase lag of the Kerr-type response. This novel phenomenon has wide-ranging implications for schemes utilizing several pumping tones, as commonly employed in backaction-evading measurements, dissipative optical squeezing, dissipative mechanical squeezing and quantum noise thermometry. Our observation may equally well be used for optomechanical Floquet engineering, e.g. generation of topological phases of sound by periodic time-modulation.
△ Less
Submitted 18 August, 2019; v1 submitted 31 May, 2018;
originally announced May 2018.
-
Nonreciprocal reconfigurable microwave optomechanical circuit
Authors:
N. R. Bernier,
L. D. Tóth,
A. Koottandavida,
M. Ioannou,
D. Malz,
A. Nunnenkamp,
A. K. Feofanov,
T. J. Kippenberg
Abstract:
Devices that achieve nonreciprocal microwave transmission are ubiquitous in radar and radio-frequency communication systems, and commonly rely on magnetically biased ferrite materials. Such devices are also indispensable in the readout chains of superconducting quantum circuits as they protect sensitive quantum systems from the noise emitted by readout electronics. Since ferrite-based nonreciproca…
▽ More
Devices that achieve nonreciprocal microwave transmission are ubiquitous in radar and radio-frequency communication systems, and commonly rely on magnetically biased ferrite materials. Such devices are also indispensable in the readout chains of superconducting quantum circuits as they protect sensitive quantum systems from the noise emitted by readout electronics. Since ferrite-based nonreciprocal devices are bulky, lossy, and require large magnetic fields, there has been significant interest in magnetic-field-free on-chip alternatives, such as those recently implemented using Josephson junctions. Here we realise reconfigurable nonreciprocal transmission between two microwave modes using purely optomechanical interactions in a superconducting electromechanical circuit. We analyse the transmission as well as the noise properties of this nonreciprocal circuit. The scheme relies on the interference in two mechanical modes that mediate coupling between microwave cavities. Finally, we show how quantum-limited circulators can be realized with the same principle. The technology can be built on-chip without any external magnetic field, and is hence fully compatible with superconducting quantum circuits. All-optomechanically-mediated nonreciprocity demonstrated here can also be extended to implement directional amplifiers, and it forms the basis towards realising topological states of light and sound.
△ Less
Submitted 1 June, 2017; v1 submitted 24 December, 2016;
originally announced December 2016.
-
A new spin on quantum cryptography: Avoiding trapdoors and embracing public keys
Authors:
Lawrence M. Ioannou,
Michele Mosca
Abstract:
We give new arguments in support of \emph{signed quantum key establishment}, where quantum cryptography is used in a public-key infrastructure that provides the required authentication. We also analyze more thoroughly than previous works the benefits that quantum key establishment protocols have over certain classical protocols, motivated in part by the various objections to quantum key establishm…
▽ More
We give new arguments in support of \emph{signed quantum key establishment}, where quantum cryptography is used in a public-key infrastructure that provides the required authentication. We also analyze more thoroughly than previous works the benefits that quantum key establishment protocols have over certain classical protocols, motivated in part by the various objections to quantum key establishment that are sometimes raised. Previous knowledge of quantum cryptography on the reader's part is not required for this article, as the definition of "quantum key establishment" that we use is an entirely classical and black-box characterization (one need only trust that protocols satisfying the definition exist).
△ Less
Submitted 14 September, 2011;
originally announced September 2011.
-
Unconditionally-secure and reusable public-key authentication
Authors:
Lawrence M. Ioannou,
Michele Mosca
Abstract:
We present a quantum-public-key identification protocol and show that it is secure against a computationally-unbounded adversary. This demonstrates for the first time that unconditionally-secure and reusable public-key authentication is possible in principle with (pure-state) public keys.
We present a quantum-public-key identification protocol and show that it is secure against a computationally-unbounded adversary. This demonstrates for the first time that unconditionally-secure and reusable public-key authentication is possible in principle with (pure-state) public keys.
△ Less
Submitted 14 August, 2011;
originally announced August 2011.
-
Public-key cryptography based on bounded quantum reference frames
Authors:
Lawrence M. Ioannou,
Michele Mosca
Abstract:
We demonstrate that the framework of bounded quantum reference frames has application to building quantum-public-key cryptographic protocols and proving their security. Thus, the framework we introduce can be seen as a public-key analogue of the framework of Bartlett et al. (Phys. Rev. A 70, 032307), where a private shared reference frame is shown to have cryptographic application. The protocol we…
▽ More
We demonstrate that the framework of bounded quantum reference frames has application to building quantum-public-key cryptographic protocols and proving their security. Thus, the framework we introduce can be seen as a public-key analogue of the framework of Bartlett et al. (Phys. Rev. A 70, 032307), where a private shared reference frame is shown to have cryptographic application. The protocol we present in this paper is an identification scheme, which, like a digital signature scheme, is a type of authentication scheme. We prove that our protocol is both reusable and secure under the honest-verifier assumption. Thus, we also demonstrate that secure reusable quantum-public-key authentication is possible to some extent.
△ Less
Submitted 14 August, 2011; v1 submitted 30 March, 2009;
originally announced March 2009.
-
Deterministic quantum-public-key encryption: forward search attack and randomization
Authors:
Georgios M. Nikolopoulos,
Lawrence M. Ioannou
Abstract:
In the classical setting, public-key encryption requires randomness in order to be secure against a forward search attack, whereby an adversary compares the encryption of a guess of the secret message with that of the actual secret message. We show that this is also true in the information-theoretic setting -- where the public keys are quantum systems -- by defining and giving an example of a fo…
▽ More
In the classical setting, public-key encryption requires randomness in order to be secure against a forward search attack, whereby an adversary compares the encryption of a guess of the secret message with that of the actual secret message. We show that this is also true in the information-theoretic setting -- where the public keys are quantum systems -- by defining and giving an example of a forward search attack for any deterministic quantum-public-key bit-encryption scheme. However, unlike in the classical setting, we show that any such deterministic scheme can be used as a black box to build a randomized bit-encryption scheme that is no longer susceptible to this attack.
△ Less
Submitted 27 March, 2009;
originally announced March 2009.
-
Universal quantum computation in a hidden basis
Authors:
Lawrence M. Ioannou,
Michele Mosca
Abstract:
Let $\ket{\0}$ and $\ket{\1}$ be two states that are promised to come from known subsets of orthogonal subspaces, but are otherwise unknown. Our paper probes the question of what can be achieved with respect to the basis $\{\ket{\0},\ket{\1}}^{\otimes n}$ of $n$ logical qubits, given only a few copies of the unknown states $\ket{\0}$ and $\ket{\1}$. A phase-invariant operator is one that is unchan…
▽ More
Let $\ket{\0}$ and $\ket{\1}$ be two states that are promised to come from known subsets of orthogonal subspaces, but are otherwise unknown. Our paper probes the question of what can be achieved with respect to the basis $\{\ket{\0},\ket{\1}}^{\otimes n}$ of $n$ logical qubits, given only a few copies of the unknown states $\ket{\0}$ and $\ket{\1}$. A phase-invariant operator is one that is unchanged under the relative phase-shift $\ket{\1} \mapsto e^{i θ}\ket{\1}$, for any $θ$, of all of the $n$ qubits. We show that phase-invariant unitary operators can be implemented exactly with no copies and that phase-invariant states can be prepared exactly with at most $n$ copies each of $\ket{\0}$ and $\ket{\1}$; we give an explicit algorithm for state preparation that is efficient for some classes of states (e.g. symmetric states). We conjecture that certain non-phase-invariant operations are impossible to perform accurately without many copies. Motivated by optical implementations of quantum computers, we define ``quantum computation in a hidden basis'' to mean executing a quantum algorithm with respect to the phase-shifted hidden basis $\{\ket{\0}, e^{iθ}\ket{\1}\}$, for some potentially unknown $θ$; we give an efficient approximation algorithm for this task, for which we introduce an analogue of a coherent state of light, which serves as a bounded quantum phase reference frame encoding $θ$. Our motivation was quantum-public-key cryptography, however the techniques are general. We apply our results to quantum-public-key authentication protocols, by showing that a natural class of digital signature schemes for classical messages is insecure. We also give a protocol for identification that uses many of the ideas discussed and whose security relates to our conjecture (but we do not know if it is secure).
△ Less
Submitted 19 August, 2010; v1 submitted 15 October, 2008;
originally announced October 2008.
-
Limitations of some simple adiabatic quantum algorithms
Authors:
Lawrence M. Ioannou,
Michele Mosca
Abstract:
Let $H(t)=(1-t/T)H_0 + (t/T)H_1$, $t\in [0,T]$, be the Hamiltonian governing an adiabatic quantum algorithm, where $H_0$ is diagonal in the Hadamard basis and $H_1$ is diagonal in the computational basis. We prove that $H_0$ and $H_1$ must each have at least two large mutually-orthogonal eigenspaces if the algorithm's running time is to be subexponential in the number of qubits. We also reproduc…
▽ More
Let $H(t)=(1-t/T)H_0 + (t/T)H_1$, $t\in [0,T]$, be the Hamiltonian governing an adiabatic quantum algorithm, where $H_0$ is diagonal in the Hadamard basis and $H_1$ is diagonal in the computational basis. We prove that $H_0$ and $H_1$ must each have at least two large mutually-orthogonal eigenspaces if the algorithm's running time is to be subexponential in the number of qubits. We also reproduce the optimality proof of Farhi and Gutmann's search algorithm in the context of this adiabatic scheme; because we only consider initial Hamiltonians that are diagonal in the Hadamard basis, our result is slightly stronger than the original.
△ Less
Submitted 2 June, 2008; v1 submitted 26 February, 2007;
originally announced February 2007.
-
Computational complexity of the quantum separability problem
Authors:
Lawrence M. Ioannou
Abstract:
Ever since entanglement was identified as a computational and cryptographic resource, researchers have sought efficient ways to tell whether a given density matrix represents an unentangled, or separable, state. This paper gives the first systematic and comprehensive treatment of this (bipartite) quantum separability problem, focusing on its deterministic (as opposed to randomized) computational…
▽ More
Ever since entanglement was identified as a computational and cryptographic resource, researchers have sought efficient ways to tell whether a given density matrix represents an unentangled, or separable, state. This paper gives the first systematic and comprehensive treatment of this (bipartite) quantum separability problem, focusing on its deterministic (as opposed to randomized) computational complexity. First, I review the one-sided tests for separability, paying particular attention to the semidefinite programming methods. Then, I discuss various ways of formulating the quantum separability problem, from exact to approximate formulations, the latter of which are the paper's main focus. I then give a thorough treatment of the problem's relationship with the complexity classes NP, NP-complete, and co-NP. I also discuss extensions of Gurvits' NP-hardness result to strong NP-hardness of certain related problems. A major open question is whether the NP-contained formulation (QSEP) of the quantum separability problem is Karp-NP-complete; QSEP may be the first natural example of a problem that is Turing-NP-complete but not Karp-NP-complete. Finally, I survey all the proposed (deterministic) algorithms for the quantum separability problem, including the bounded search for symmetric extensions (via semidefinite programming), based on the recent quantum de Finetti theorem; and the entanglement-witness search (via interior-point algorithms and global optimization). These two algorithms have the lowest complexity, with the latter being the best under advice of asymptotically optimal point-coverings of the sphere.
△ Less
Submitted 31 January, 2007; v1 submitted 22 March, 2006;
originally announced March 2006.
-
Convex Separation from Optimization via Heuristics
Authors:
Lawrence M. Ioannou,
Benjamin C. Travaglione,
Donny Cheung
Abstract:
Let $K$ be a full-dimensional convex subset of $\mathbb{R}^n$. We describe a new polynomial-time Turing reduction from the weak separation problem for $K$ to the weak optimization problem for $K$ that is based on a geometric heuristic. We compare our reduction, which relies on analytic centers, with the standard, more general reduction.
Let $K$ be a full-dimensional convex subset of $\mathbb{R}^n$. We describe a new polynomial-time Turing reduction from the weak separation problem for $K$ to the weak optimization problem for $K$ that is based on a geometric heuristic. We compare our reduction, which relies on analytic centers, with the standard, more general reduction.
△ Less
Submitted 22 March, 2006;
originally announced March 2006.
-
Quantum Separability and Entanglement Detection via Entanglement-Witness Search and Global Optimization
Authors:
Lawrence M. Ioannou,
Benjamin C. Travaglione
Abstract:
We focus on determining the separability of an unknown bipartite quantum state $ρ$ by invoking a sufficiently large subset of all possible entanglement witnesses given the expected value of each element of a set of mutually orthogonal observables. We review the concept of an entanglement witness from the geometrical point of view and use this geometry to show that the set of separable states is…
▽ More
We focus on determining the separability of an unknown bipartite quantum state $ρ$ by invoking a sufficiently large subset of all possible entanglement witnesses given the expected value of each element of a set of mutually orthogonal observables. We review the concept of an entanglement witness from the geometrical point of view and use this geometry to show that the set of separable states is not a polytope and to characterize the class of entanglement witnesses (observables) that detect entangled states on opposite sides of the set of separable states. All this serves to motivate a classical algorithm which, given the expected values of a subset of an orthogonal basis of observables of an otherwise unknown quantum state, searches for an entanglement witness in the span of the subset of observables. The idea of such an algorithm, which is an efficient reduction of the quantum separability problem to a global optimization problem, was introduced in PRA 70 060303(R), where it was shown to be an improvement on the naive approach for the quantum separability problem (exhaustive search for a decomposition of the given state into a convex combination of separable states). The last section of the paper discusses in more generality such algorithms, which, in our case, assume a subroutine that computes the global maximum of a real function of several variables. Despite this, we anticipate that such algorithms will perform sufficiently well on small instances that they will render a feasible test for separability in some cases of interest (e.g. in 3-by-3 dimensional systems).
△ Less
Submitted 29 June, 2006; v1 submitted 27 February, 2006;
originally announced February 2006.
-
Perturbative renormalization in parton distribution functions using Overlap fermions and Symanzik improved gluons
Authors:
M. Ioannou,
H. Panagopoulos
Abstract:
We calculate the 1-loop renormalization of the fermion self-energy, all local fermion bilinears, as well as a set of extended bilinears which form a basis corresponding to moments of the parton distribution functions.
We use the overlap action for fermions and Symanzik improved action for gluons.
Our results are presented as a function of the overlap parameter rho and the parameters entering…
▽ More
We calculate the 1-loop renormalization of the fermion self-energy, all local fermion bilinears, as well as a set of extended bilinears which form a basis corresponding to moments of the parton distribution functions.
We use the overlap action for fermions and Symanzik improved action for gluons.
Our results are presented as a function of the overlap parameter rho and the parameters entering the Symanzik action.
△ Less
Submitted 2 March, 2006; v1 submitted 17 January, 2006;
originally announced January 2006.
-
Perturbative renormalization in parton distribution functions using improved actions
Authors:
M. Ioannou,
H. Panagopoulos
Abstract:
We calculate the 1-loop renormalization of a set of extended fermionic bilinears which form a basis corresponding to moments of the parton distribution functions.
We use the overlap action for fermions and Luescher-Weisz (LW) action for gluons.
Our results are presented as a function of the overlap parameter rho and the parameters entering the LW action.
We calculate the 1-loop renormalization of a set of extended fermionic bilinears which form a basis corresponding to moments of the parton distribution functions.
We use the overlap action for fermions and Luescher-Weisz (LW) action for gluons.
Our results are presented as a function of the overlap parameter rho and the parameters entering the LW action.
△ Less
Submitted 27 December, 2005;
originally announced December 2005.
-
Computing finite-dimensional bipartite quantum separability
Authors:
Lawrence M. Ioannou
Abstract:
Ever since entanglement was identified as a computational and cryptographic resource, effort has been made to find an efficient way to tell whether a given density matrix represents an unentangled, or separable, state. Essentially, this is the quantum separability problem.
Chapters 1 to 3 motivate a new interior-point algorithm which, given the expected values of a subset of an orthogonal basi…
▽ More
Ever since entanglement was identified as a computational and cryptographic resource, effort has been made to find an efficient way to tell whether a given density matrix represents an unentangled, or separable, state. Essentially, this is the quantum separability problem.
Chapters 1 to 3 motivate a new interior-point algorithm which, given the expected values of a subset of an orthogonal basis of observables of an otherwise unknown quantum state, searches for an entanglement witness in the span of the subset of observables. When all the expected values are known, the algorithm solves the separability problem. In Chapter 4, I give the motivation for the algorithm and show how it can be used in a particular physical scenario to detect entanglement (or decide separability) of an unknown quantum state using as few quantum resources as possible. I then explain the intuitive idea behind the algorithm and relate it to the standard algorithms of its kind. I end the chapter with a comparison of the complexities of the algorithms surveyed in Chapter 3. Finally, in Chapter 5, I present the details of the algorithm and discuss its performance relative to standard methods.
△ Less
Submitted 15 February, 2006; v1 submitted 29 April, 2005;
originally announced April 2005.
-
Improved algorithm for quantum separability and entanglement detection
Authors:
L. M. Ioannou,
B. C. Travaglione,
D. Cheung,
A. K. Ekert
Abstract:
Determining whether a quantum state is separable or entangled is a problem of fundamental importance in quantum information science. It has recently been shown that this problem is NP-hard. There is a highly inefficient `basic algorithm' for solving the quantum separability problem which follows from the definition of a separable state. By exploiting specific properties of the set of separable s…
▽ More
Determining whether a quantum state is separable or entangled is a problem of fundamental importance in quantum information science. It has recently been shown that this problem is NP-hard. There is a highly inefficient `basic algorithm' for solving the quantum separability problem which follows from the definition of a separable state. By exploiting specific properties of the set of separable states, we introduce a new classical algorithm that solves the problem significantly faster than the `basic algorithm', allowing a feasible separability test where none previously existed e.g. in 3-by-3-dimensional systems. Our algorithm also provides a novel tool in the experimental detection of entanglement.
△ Less
Submitted 15 July, 2005; v1 submitted 4 March, 2004;
originally announced March 2004.
-
A Note on Quantum Separability
Authors:
L. M. Ioannou,
B. C. Travaglione
Abstract:
This short note describes a method to tackle the (bipartite) quantum separability problem. The method can be used for solving the separability problem in an experimental setting as well as in the purely mathematical setting. The idea is to invoke the following characterization of entangled states: A state is entangled if and only if there exists an entanglement witness that detects it. The metho…
▽ More
This short note describes a method to tackle the (bipartite) quantum separability problem. The method can be used for solving the separability problem in an experimental setting as well as in the purely mathematical setting. The idea is to invoke the following characterization of entangled states: A state is entangled if and only if there exists an entanglement witness that detects it. The method is basically a search for an entanglement witness that detects the given state.
△ Less
Submitted 26 November, 2003;
originally announced November 2003.