REVIEW
Quantum Separability and Entanglement Detection via Entanglement-Witness Search and Global Optimization
Quantum Physics · Submitted 27 Feb 2006 · 39 references
Pith's verdict: A clean geometric treatment of entanglement witnesses; the algorithm is a sound reduction that depends on an oracle nobody has, so the practical claim is speculative.
T0 · AI review
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
This paper reduces the separability question for partially measured quantum states to a global optimization problem, and proves the separable set is not a polytope.
The reading
What carries the argument
The polar of the projected separable set, $K^\star=\{c\in\mathbb{R}^j: c^Tx\le 1 \text{ for all } x\in K\}$, is the central object: it contains exactly the candidate entanglement witnesses, and a point $p$ is outside $K$ precisely when some $c\in K^\star$ has $p^Tc>1$. The paper shows that a global optimizer for $K$ doubles as a separation oracle for $K^\star$, which in turn drives a cutting-plane feasibility algorithm for $Q_p=K^\star\cap\{c:p^Tc\ge1\}$. The secondary mechanism is the spectral gap criterion of Theorem 3, which manufactures witnesses from eigenspaces free of product states and underlies the ambidextrous-witness constructions.
Extended reading notes
Core claim
The paper's central discovery is that the quantum separability problem with partial information is a convex separation problem, and that separation can be converted into optimization. Concretely, it proves Fact 1: the set $S_{M,N}$ of bipartite separable states, viewed in the real space $\mathbb{R}^{M^2N^2-1}$ of traceless Hermitian coordinates, is not a polytope, because its extreme points are exactly the product states and there are infinitely many of them. It proves Theorem 3: a Hermitian operator $A$ is a left or right entanglement witness exactly when, in the spectral decomposition of $A$, there is a gap $\lambda_k<\lambda_{k+1}$ such that the span of the corresponding lowest (or highest) eigenstates contains no product state; this yields ambidextrous witnesses that detect entangled states on opposite sides of $S_{M,N}$. The main algorithm result is an oracle-polynomial reduction of the weak separation problem $\mathrm{WSEP}(S_{M,N})$ to the weak optimization problem $\mathrm{WOPT}(S_{M,N})$: using the polar $K^\star$, an optimizer for $K$ gives a separation oracle for $K^\star$, and a cutting-plane feasibility algorithm on $Q_p=K^\star\cap\{c:p^Tc\ge1\}$ either finds an entanglement witness in the span of the measured observables or concludes that none exists.
Load-bearing premise
The load-bearing premise is that a subroutine exists which actually computes the global maximum of a linear functional over the separable set (or its projection) to the required accuracy; the paper notes this problem is NP-hard and offers no subroutine for it, only references to generic global-optimization methods.
Editorial extensions
If this is right
- No finite collection of entanglement witnesses can detect every entangled state; any complete detection scheme must search over an infinite family of witnesses or adapt to the state.
- The difficulty of separability testing with partial data is exactly the difficulty of global optimization over the projected separable set, so better convex optimizers directly improve entanglement detection.
- An experimentalist can stop gathering data as soon as the optimizer returns a witness: the algorithm converts classical computation time into savings in the number of measured copies of the state.
- In low-dimensional cases such as $2\otimes2$ or $3\otimes3$, where $a^\ast$ and $b^\ast$ can be computed, ambidextrous witnesses allow a single observable to certify entanglement for states on opposite sides of the separable set, as illustrated for noisy Bell states.
- The reduction is oracle-polynomial, so the number of calls to the optimization oracle grows polynomially with the dimension and the desired precision, even though each call may itself be hard.
Reading between the lines
- Inference: The polar/cutting-plane reduction is not specific to the separable set; the same construction applies to any full-dimensional convex body with the stated ball conditions, so the algorithm could equally detect states violating other convex constraints, such as fixed noise models or partial transposition bounds.
- Inference: If the oracle assumption is accepted, the practical bottleneck of entanglement detection shifts from tomography to global optimization; benchmarking the reduction on random $3\otimes3$ states against semidefinite relaxations and interval methods would be a direct test of the paper's small-instance promise.
- Inference: The spectral criterion suggests an automated witness-search heuristic: scan the span of measured observables for an operator whose extremal eigenspace avoids product states; because the separable set is not a polytope, such searches cannot be replaced by a fixed precomputed list.
Original abstract
We focus on determining the separability of an unknown bipartite quantum state $\rho$ 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).
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
We focus on determining the separability of an unknown bipartite quantum state $\rho$ 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).
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | We focus on determining the separability of an unknown bipartite quantum state $\rho$ 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. | contribution 0.59 | 0.65 | 0.14 | asserted 0.93 |
| s1 | 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. | contribution 0.54 | 0.76 | 0.09 | asserted 1.00 |
| s2 | 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. | method 0.77 | 0.47 | 0.13 | asserted 0.98 |
| s3 | 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). | background 0.84 | 0.18 | 0.14 | asserted 1.00 |
| s4 | 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. | method 0.61 | 0.28 | 0.07 | asserted 0.90 |
| s5 | 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). | limitation 0.76 | 0.13 | 0.42 | hedged possibility 0.78 |
What was examined, and what was not
- arXiv listing abstract v2
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
References
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.