Computable entanglement cost
- URL: http://arxiv.org/abs/2405.09613v1
- Date: Wed, 15 May 2024 18:00:01 GMT
- Title: Computable entanglement cost
- Authors: Ludovico Lami, Francesco Anna Mele, Bartosz Regula,
- Abstract summary: We consider the problem of computing the entanglement cost of preparing noisy quantum states under quantum operations with positive partial transpose (PPT)
A previously claimed solution to this problem is shown to be incorrect. We construct instead an alternative solution in the form of two hierarchies of semi-definite programs that converge to the true value of the entanglement cost from above and from below.
Our main result establishes that this convergence happens exponentially fast, thus yielding an efficient algorithm that approximates the cost up to an additive error $varepsilon$ in time.
- Score: 4.642647756403864
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum information theory is plagued by the problem of regularisations, which require the evaluation of formidable asymptotic quantities. This makes it computationally intractable to gain a precise quantitative understanding of the ultimate efficiency of key operational tasks such as entanglement manipulation. Here we consider the problem of computing the asymptotic entanglement cost of preparing noisy quantum states under quantum operations with positive partial transpose (PPT). A previously claimed solution to this problem is shown to be incorrect. We construct instead an alternative solution in the form of two hierarchies of semi-definite programs that converge to the true asymptotic value of the entanglement cost from above and from below. Our main result establishes that this convergence happens exponentially fast, thus yielding an efficient algorithm that approximates the cost up to an additive error $\varepsilon$ in time $\mathrm{poly}\big(D,\,\log(1/\varepsilon)\big)$, where $D$ is the underlying Hilbert space dimension. To our knowledge, this is the first time that an asymptotic entanglement measure is shown to be efficiently computable despite no closed-form formula being available.
Related papers
- Quantum Realization of the Finite Element Method [0.0]
This paper presents a quantum algorithm for the solution of second-order linear elliptic partial differential equations discretized by $d$-linear finite elements.
A BPX preconditioner transforms the linear system into a sufficiently well-conditioned one, making it amenable to quantum computation.
We detail the design and implementation of a quantum circuit capable of executing our algorithm, and present simulator results that support the quantum feasibility of the finite element method.
arXiv Detail & Related papers (2024-03-28T15:44:20Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$.
We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
arXiv Detail & Related papers (2024-01-17T18:59:38Z) - Non-Linear Transformations of Quantum Amplitudes: Exponential
Improvement, Generalization, and Applications [0.0]
Quantum algorithms manipulate the amplitudes of quantum states to find solutions to computational problems.
We present a framework for applying a general class of non-linear functions to the amplitudes of quantum states.
Our work provides an important and efficient building block with potentially numerous applications in areas such as optimization, state preparation, quantum chemistry, and machine learning.
arXiv Detail & Related papers (2023-09-18T14:57:21Z) - Efficient quantum linear solver algorithm with detailed running costs [0.0]
We introduce a quantum linear solver algorithm combining ideasdiabatic quantum computing with filtering techniques based on quantum signal processing.
Our protocol reduces the cost of quantum linear solvers over state-of-the-art close to an order of magnitude for early implementations.
arXiv Detail & Related papers (2023-05-19T00:07:32Z) - A Newton-CG based barrier-augmented Lagrangian method for general
nonconvex conic optimization [77.8485863487028]
In this paper we consider finding an approximate second-order stationary point (SOSP) that minimizes a twice different subject general non conic optimization.
In particular, we propose a Newton-CG based-augmentedconjugate method for finding an approximate SOSP.
arXiv Detail & Related papers (2023-01-10T20:43:29Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach.
We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers.
We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
arXiv Detail & Related papers (2022-09-28T17:53:25Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits.
Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit.
We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
arXiv Detail & Related papers (2022-06-30T03:15:23Z) - Quantum algorithms for approximate function loading [0.0]
We introduce two approximate quantum-state preparation methods for the NISQ era inspired by the Grover-Rudolph algorithm.
A variational algorithm capable of loading functions beyond the aforementioned smoothness conditions is proposed.
arXiv Detail & Related papers (2021-11-15T17:36:13Z) - Average-case Speedup for Product Formulas [69.68937033275746]
Product formulas, or Trotterization, are the oldest and still remain an appealing method to simulate quantum systems.
We prove that the Trotter error exhibits a qualitatively better scaling for the vast majority of input states.
Our results open doors to the study of quantum algorithms in the average case.
arXiv Detail & Related papers (2021-11-09T18:49:48Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
We propose a new algorithm -- the Momentum- Single-timescale Approximation (MSTSA) -- for tackling problems.
MSTSA allows us to control the error in iterations due to inaccurate solution to the lower level subproblem.
arXiv Detail & Related papers (2021-02-15T07:10:33Z) - Quasi-polynomial time algorithms for free quantum games in bounded
dimension [11.56707165033]
We give a semidefinite program of size $exp(mathcalObig(T12(log2(AT)+log(Q)log(AT))/epsilon2big)) to compute additive $epsilon$-approximations on the values of two-player free games.
We make a connection to the quantum separability problem and employ improved multipartite quantum de Finetti theorems with linear constraints.
arXiv Detail & Related papers (2020-05-18T16:55:08Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.