Identifying whether a state family admits an irreducible quantum advantage is a fundamental task in quantum resource theory and quantum information processing. Here we study classically simulable state families, namely those residing within the convex hull of pairwise commuting families and therefore admitting a classical explanation. We develop a complete semidefinite-programming (SDP) hierarchy characterizing the set of classically simulable state families in arbitrary finite dimension. The key step is to reformulate classical simulability as a feasibility problem over deterministic response functions and auxiliary positive-operator-valued measures (POVMs) simulable by rank-one projective measurements. We establish a complete SDP hierarchy for rank-one projectively simulable POVMs and transfer the resulting characterization to state families, yielding both primal feasibility tests and dual affine witnesses certifying failure of classical simulability. Applying the hierarchy to state families mixed with depolarizing noise gives computable upper bounds on the critical classical visibility, which are matched by explicit classical simulations in several symmetric examples. These results provide a systematic convex-optimization framework for certifying classical simulability of quantum state families.
Identifying whether a state family admits an irreducible quantum advantage is a fundamental task in quantum resource theory and quantum information processing. Here we study classically simulable state families, namely those residing within the convex hull of pairwise commuting families and therefore admitting a classical explanation. We develop a complete semidefinite-programming (SDP) hierarchy characterizing the set of classically simulable state families in arbitrary finite dimension. The key step is to reformulate classical simulability as a feasibility problem over deterministic response functions and auxiliary positive-operator-valued measures (POVMs) simulable by rank-one projective measurements. We establish a complete SDP hierarchy for rank-one projectively simulable POVMs and transfer the resulting characterization to state families, yielding both primal feasibility tests and dual affine witnesses certifying failure of classical simulability. Applying the hierarchy to state families mixed with depolarizing noise gives computable upper bounds on the critical classical visibility, which are matched by explicit classical simulations in several symmetric examples. These results provide a systematic convex-optimization framework for certifying classical simulability of quantum state families.
Determining the conditions under which positive operator-valued measures (POVMs), the most general class of quantum measurements, outperform projective measurements remains a challenging and largely unresolved problem. Of particular interest are projectively simulable POVMs, which can be realized through probabilistic mixtures of projective measurements, and therefore offer no advantage over projective schemes. Characterizing the boundary between simulable and non-simulable POVMs is, however, a difficult task, and existing tools either fail to scale efficiently, provide limited experimental feasibility or work only for specific POVMs. Here, we introduce and demonstrate a general method to certify non-simulability of a POVM by introducing a complete hierarchy of semidefinite programs. It provides upper bounds on the non-simulability measure of critical visibility of arbitrary POVMs which are tight in many cases and outperform previously known criteria. We experimentally certify the non-simulability of two- and three-dimensional POVMs using a trapped-ion qudit quantum processor by constructing non-simulability witnesses and introduce a modification of our framework that makes them robust against state preparation errors. Finally, we extend our results to the setting where an additional ancilla system is available.
The problem of reconstructing a quantum channel from a sample of classical data is considered. When the total fidelity can be represented as a ratio of two quadratic forms (e.g., in the case of mapping a mixed state to a pure state, projective operators, unitary learning, and others), Semidefinite Programming (SDP) can be applied to solve the fidelity optimization problem with respect to the Choi matrix. A remarkable feature of SDP is that the optimization is convex, which allows the problem to be efficiently solved by a variety of numerical algorithms. We have tested several commercially available SDP solvers, all of which allowed for the reconstruction of quantum channels of different forms. A notable feature is that the Kraus rank of the obtained quantum channel typically comprises less than a few percent of its maximal possible value. This suggests that a relatively small Kraus rank quantum channel is typically sufficient to describe experimentally observed classical data. The theory was also applied to the problem of reconstructing projective operators from data. Finally, we discuss a classical computational model based on quantum channel transformation, performed and calculated on a classical computer, possibly hardware-optimized.
Many problems in information theory can be reduced to optimizations over matrices, where the rank of the matrices is constrained.We establish a link between rank-constrained optimization and the theory of quantum entanglement.More precisely, we prove that a large class of rank-constrained semidefinite programs can be written as a convex optimization over separable quantum states and, consequently, we construct a complete hierarchy of semidefinite programs for solving the original problem.This hierarchy not only provides a sequence of certified bounds for the rank-constrained optimization problem, but also gives pretty good and often exact values in practice when the lowest level of the hierarchy is considered.We demonstrate that our approach can be used for relevant problems in quantum information processing, such as the optimization over pure states, the characterization of mixed unitary channels and faithful entanglement, and quantum contextuality, as well as in classical information theory including the maximum cut problem, pseudo-Boolean optimization, and the orthonormal representation of graphs.Finally, we show that our ideas can be extended to rank-constrained quadratic and higher-order programming.
The problem of deciding whether a set of quantum measurements is jointly measurable is known to be equivalent to determining whether a quantum assemblage is unsteerable. This problem can be formulated as a semidefinite program (SDP). However, the number of variables and constraints in such a formulation grows exponentially with the number of measurements, rendering it intractable for large measurement sets. In this work, we circumvent this problem by transforming the SDP into a hierarchy of linear programs that compute upper and lower bounds on the incompatibility robustness with a complexity that grows polynomially in the number of measurements. The hierarchy is guaranteed to converge and it can be applied to arbitrary measurements – including non-projective POVMs (Positive Operator-Valued Measures) – in arbitrary dimensions. While convergence becomes impractical in high dimensions, in the case of qubits our method reliably provides accurate upper and lower bounds for the incompatibility robustness of sets with several hundred measurements in a short time using a standard laptop. We also apply our methods to qutrits, obtaining non-trivial upper and lower bounds in scenarios that are otherwise intractable using the standard SDP approach, although such bounds are significantly looser than the ones obtained in the qubit case. Finally, we show how our methods can be used to construct local hidden state models for states (i.e., to prove that a state cannot lead to steering under any possible local measurements), or conversely, to certify that a given state exhibits steering; for two-qubit quantum states, our approach is comparable to, and in some cases outperforms, the current best methods.
In the heart of every physical theory lies measurement theory. While classical measurements are passive probes, QMs can be viewed as active physical processes that shape the available information. Depending on the measurement type, different aspects of the information about a system are retrieved. All possible measurements in quantum physics are described by mathematical objects called Positive Operator-Valued Measures (POVMs). The most familiar standard measurements are called Projective-Valued Measures (PVMs) and make up a subset of POVMs. The complementary subset of POVMs is non-projective. However, some non-projective POVMs can be expressed as a probabilistic mixture of PVMs. Such POVMs are called projectively simulable, while non-simulable POVMs are genuinely non-projective. These can be made projectively simulable by adding noise to the measurements. If a genuinely non-projective POVM requires a large amount of noise before it becomes projectively simulable, it is more non-projective than a POVM that requires less noise. Hence, the degree of non-projectiveness is determined by the required noise strength. The act of measuring a quantum system changes the quantum state. While quantum measurements only take into account the readable classical output value, quantum instruments account for both the classical outcome and the post-measurement state. Hence, instruments are associated with measurements, and in an analogous way, projective and projectively simulable instruments can be defined. For many purposes, non-projective POVMs are more useful than PVMs, and the more non-projective a POVM is, the greater the advantage of using them over PVMs. Therefore, the aim of the thesis is to investigate the genuinely non-projective POVMs. More precisely, the degree of non-projectiveness in qubit POVMs is studied. This is done by convex optimization, specifically by solving semidefinite programs. Furthermore, the thesis addresses the open problem of finding the most non-projective qubit quantum instrument by a witness-based see-saw algorithm.
This paper provides a semidefinite programming hierarchy based on state polynomial optimization to determine the existence of quantum codes with given parameters. The hierarchy is complete, in the sense that a ((n,K,δ))2 code exists if and only if every level of the hierarchy is feasible. It is not limited to stabilizer codes and thus is applicable generally. While the machinery is formally dimension-free, we restrict it to qubit codes through quasi-Clifford algebras. We derive the quantum analog of a range of classical results: first, from an intermediate level a Lovász bound for self-dual quantum codes is recovered. Second, a symmetrization of a minor variation of this Lovász bound recovers the quantum Delsarte bound. Third, a symmetry reduction using the Terwilliger algebra leads to semidefinite programming bounds of size O(n4). With this we give an alternative proof that there is no ((7,1,4))2 quantum code, and show that ((8,9,3))2 and ((10,5,4))2 codes do not exist.