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
- Entanglement theory with limited computational resources [0.29998889086656577]
We show that computational entanglement measures diverge significantly from information-theoretic counterparts.
While the von Neumann entropy captures information-theoretic rates for pure-state transformations, we show that under computational constraints, the min-entropy governs optimal entanglement distillation.
Our results establish a stark, maximal separation of $tildeOmega(n)$ vs. $o(1)$ between computational and information-theoretic entanglement measures.
arXiv Detail & Related papers (2025-02-17T19:43:59Z) - Pathwise optimization for bridge-type estimators and its applications [49.1574468325115]
Pathwise methods allow to efficiently compute the full path for penalized estimators.
We apply these algorithms to the penalized estimation of processes observed at discrete times.
arXiv Detail & Related papers (2024-12-05T10:38:29Z) - Unstructured Adiabatic Quantum Optimization: Optimality with Limitations [0.06022769903412461]
We show that adiabatic quantum optimization using an unstructured search approach results in a running time that matches a lower bound for a class of classical local spin Hamiltonians.
We show that the position of the avoided crossing is approximately given by a quantity that depends on the degeneracies and inverse gaps of the problem Hamiltonian and is NP-hard to compute even within a low additive precision.
arXiv Detail & Related papers (2024-11-08T17:51:18Z) - Improved quantum algorithm for calculating eigenvalues of differential operators and its application to estimating the decay rate of the perturbation distribution tail in stochastic inflation [0.0]
We propose a quantum algorithm for estimating the first eigenvalue of a differential operator $mathcalL$ on $mathbbRd$.
We then consider the application of our method to a problem in a theoretical framework for cosmic inflation known as quantum inflation.
arXiv Detail & Related papers (2024-10-03T07:56:20Z) - Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP)
We generalize the SDP-inspired quantum algorithm to sum-of-squares.
Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
arXiv Detail & Related papers (2024-08-14T19:04:13Z) - 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) - 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 [53.044526424637866]
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)
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.