Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2003.07772 · Communications in Contemporary Mathematics

On maps which preserve semipositivity and quantifier elimination theory for real numbers

Grzegorz Pastuszak, Adam Skowyrski, Andrzej Jamiołkowski

Published Nov 20, 2020• 3 citations
arXivHTMLPDF

Abstract

Assume that [Formula: see text] is a superoperator which preserves hermiticity. We give an algorithm determining whether [Formula: see text] preserves semipositivity (we call [Formula: see text] positive in this case). Our approach to the problem has a model-theoretic nature, namely, we apply techniques of quantifier elimination theory for real numbers. An approach based on these techniques seems to be the only one that allows to decide whether an arbitrary hermiticity-preserving [Formula: see text] is positive. Before we go to detailed analysis of the problem, we argue that quantifier elimination for real numbers (and also for complex numbers) can play a significant role in quantum information theory and other areas as well.

DOI
10.1142/s0219199720500923

Related papers

On One-Parameter Families of Hermiticity-Preserving Superoperators which Are Not Positive

Grzegorz Pastuszak, Alicja Jaworska-Pastuszak, Takeo Kamizawa

A one-parameter family of hermiticity-preserving superoperators is a time-dependent family [Formula: see text] of hermiticity-preserving superoperators determined, in a certain sense, by real and complex polynomial functions in the variable [Formula: see text]. The paper studies sufficient computable criteria for nonpositivity of superoperators in one-parameter families. More precisely, we give sufficient conditions for the following assertions to hold: [Formula: see text] every [Formula: see text] is not positive, [Formula: see text] [Formula: see text] is not positive for [Formula: see text] in some [Formula: see text] and [Formula: see text] there is some [Formula: see text] which is not positive. We show that [Formula: see text] implies [Formula: see text]. Our approach to the problem is based on the Descartes rule of signs and the Sturm-Tarski theorem. In order to apply these facts, we introduce the sign variation formulas. These formulas are first order logical formulas in one variable [Formula: see text], generalising sign sequences of polynomials used in Descartes rule of signs.

arXiv:2411.11035•Open Systems & Information Dynamics•Mar 1, 2025•0 citations

Quantifier elimination theory and maps which preserve semipositivity

Grzegorz Pastuszak, Adam Skowyrski, Andrzej Jamiołkowski

arXiv:2003.09081•Quantum Information Processing•Mar 1, 2021•2 citations

Are problems in Quantum Information Theory (un)decidable?

Michael M. Wolf, Toby S. Cubitt, David Pérez-Garcı́a

This note is intended to foster a discussion about the extent to which typical problems arising in quantum information theory are algorithmically decidable (in principle rather than in practice). Various problems in the context of entanglement theory and quantum channels turn out to be decidable via quantifier elimination as long as they admit a compact formulation without quantification over integers. For many asymptotically defined properties which have to hold for all or for one integer N, however, effective procedures seem to be difficult if not impossible to find. We review some of the main tools for (dis)proving decidability and apply them to problems in quantum information theory. We find that questions like "can we overcome fidelity 1/2 w.r.t. a two-qubit singlet state?" easily become undecidable. A closer look at such questions might rule out some of the "single-letter" formulas sought in quantum information theory.

arXiv:1111.5425•Nov 23, 2011•32 citations

Complete Graphical Language for Hermiticity-Preserving Superoperators

Titouan Carette, Timothée Hoffreumon, Émile Larroque +1 more

Universal and complete graphical languages have been successfully designed for pure state quantum mechanics, corresponding to linear maps between Hilbert spaces, and mixed states quantum mechanics, corresponding to completely positive superoperators. In this paper, we go one step further and present a universal and complete graphical language for Hermiticity-preserving superoperators. Such a language opens the possibility of diagrammatic compositional investigations of antilinear transformations featured in various physical situations, such as the Choi-Jamiołkowski isomorphism, spin-flip, or entanglement witnesses. Our construction relies on an extension of the ZW-calculus exhibiting a normal form for Hermitian matrices.

arXiv:2302.04212•ACM/IEEE Symposium on Logic in Computer Science (LICS)•Jun 26, 2023•1 citation

Open system quantum evolution and the assumption of complete positivity (A Tutorial)

Mark Byrd, Russell R. Ceballos, Eric Chitambar

Quantum systems which interact with an unknown environment cannot be described in terms of a unitary evolution on the system alone. For such evolution one can use a map from one density operator to another and use any other known information to model the system. Such maps are required to be positive (at least on their domain) — they take positive density operators to positive density operators — so as to be physically reasonable. A map [Formula: see text] which is positive but not completely positive (CP) is one which takes positive operators to positive operators, but when extended by the identity [Formula: see text], i.e. [Formula: see text] does not give a positive map for some [Formula: see text]. The map is CP if and only if the extension is positive for all [Formula: see text]. Recently some effort has been put forth to try to understand if, and/or, under what circumstances one might utilize a non-CP map. Here, after a tutorial-type introduction to maps from one density operator to another, some examples which do not fit the standard prescription (SP) for deriving a CP map are given. In cases where the physical system is constrained by some knowledge of the interaction, it is possible that the SP cannot be used directly. Our example is robust to changes in the initial and final conditions.

International Journal of Quantum Information•Aug 18, 2016•2 citations

k-Positive Maps: New Characterizations and a Generation Method

Frederik vom Ende, Sumeet Khatri, Sergey Denisov

We study [Formula: see text]-positive linear maps on matrix algebras and address two problems, (i) characterizations of [Formula: see text]-positivity and (ii) generation of nondecomposable [Formula: see text]-positive maps. On the characterization side, we derive optimization-based conditions equivalent to [Formula: see text]-positivity that (a) reduce to a simple check when [Formula: see text], (b) reveal a direct link to the spectral norm of certain order-3 tensors (aligning with known NP-hardness barriers for [Formula: see text]), and (c) recast [Formula: see text]-positivity as a novel optimization problem over separable states, thereby connecting it explicitly to separability testing. On the generation side, we introduce a Lie-semigroup-based method that, starting from a single [Formula: see text]-positive map, produces one-parameter families that remain [Formula: see text]-positive and nondecomposable for small enough times. We illustrate this by generating such families for [Formula: see text] and [Formula: see text]. We also formulate a semidefinite program (SDP) to test an equivalent form of the positive partial transpose (PPT) square conjecture (and do not find any violation of the latter). Our results provide practical computational tools for certifying [Formula: see text]-positivity and a systematic way to sample [Formula: see text]-positive nondecomposable maps.

arXiv:2508.21348•Open Systems & Information Dynamics•Dec 1, 2025•1 citation
Assume that [Formula: see text] is a superoperator which preserves hermiticity. We give an algorithm determining whether [Formula: see text] preserves semipositivity (we call [Formula: see text] positive in this case). Our approach to the problem has a model-theoretic nature, namely, we apply techniques of quantifier elimination theory for real numbers. An approach based on these techniques seems to be the only one that allows to decide whether an arbitrary hermiticity-preserving [Formula: see text] is positive. Before we go to detailed analysis of the problem, we argue that quantifier elimination for real numbers (and also for complex numbers) can play a significant role in quantum information theory and other areas as well.
A one-parameter family of hermiticity-preserving superoperators is a time-dependent family [Formula: see text] of hermiticity-preserving superoperators determined, in a certain sense, by real and complex polynomial functions in the variable [Formula: see text]. The paper studies sufficient computable criteria for nonpositivity of superoperators in one-parameter families. More precisely, we give sufficient conditions for the following assertions to hold: [Formula: see text] every [Formula: see text] is not positive, [Formula: see text] [Formula: see text] is not positive for [Formula: see text] in some [Formula: see text] and [Formula: see text] there is some [Formula: see text] which is not positive. We show that [Formula: see text] implies [Formula: see text]. Our approach to the problem is based on the Descartes rule of signs and the Sturm-Tarski theorem. In order to apply these facts, we introduce the sign variation formulas. These formulas are first order logical formulas in one variable [Formula: see text], generalising sign sequences of polynomials used in Descartes rule of signs.
This note is intended to foster a discussion about the extent to which typical problems arising in quantum information theory are algorithmically decidable (in principle rather than in practice). Various problems in the context of entanglement theory and quantum channels turn out to be decidable via quantifier elimination as long as they admit a compact formulation without quantification over integers. For many asymptotically defined properties which have to hold for all or for one integer N, however, effective procedures seem to be difficult if not impossible to find. We review some of the main tools for (dis)proving decidability and apply them to problems in quantum information theory. We find that questions like "can we overcome fidelity 1/2 w.r.t. a two-qubit singlet state?" easily become undecidable. A closer look at such questions might rule out some of the "single-letter" formulas sought in quantum information theory.
Universal and complete graphical languages have been successfully designed for pure state quantum mechanics, corresponding to linear maps between Hilbert spaces, and mixed states quantum mechanics, corresponding to completely positive superoperators. In this paper, we go one step further and present a universal and complete graphical language for Hermiticity-preserving superoperators. Such a language opens the possibility of diagrammatic compositional investigations of antilinear transformations featured in various physical situations, such as the Choi-Jamiołkowski isomorphism, spin-flip, or entanglement witnesses. Our construction relies on an extension of the ZW-calculus exhibiting a normal form for Hermitian matrices.
Quantum systems which interact with an unknown environment cannot be described in terms of a unitary evolution on the system alone. For such evolution one can use a map from one density operator to another and use any other known information to model the system. Such maps are required to be positive (at least on their domain) — they take positive density operators to positive density operators — so as to be physically reasonable. A map [Formula: see text] which is positive but not completely positive (CP) is one which takes positive operators to positive operators, but when extended by the identity [Formula: see text], i.e. [Formula: see text] does not give a positive map for some [Formula: see text]. The map is CP if and only if the extension is positive for all [Formula: see text]. Recently some effort has been put forth to try to understand if, and/or, under what circumstances one might utilize a non-CP map. Here, after a tutorial-type introduction to maps from one density operator to another, some examples which do not fit the standard prescription (SP) for deriving a CP map are given. In cases where the physical system is constrained by some knowledge of the interaction, it is possible that the SP cannot be used directly. Our example is robust to changes in the initial and final conditions.
We study [Formula: see text]-positive linear maps on matrix algebras and address two problems, (i) characterizations of [Formula: see text]-positivity and (ii) generation of nondecomposable [Formula: see text]-positive maps. On the characterization side, we derive optimization-based conditions equivalent to [Formula: see text]-positivity that (a) reduce to a simple check when [Formula: see text], (b) reveal a direct link to the spectral norm of certain order-3 tensors (aligning with known NP-hardness barriers for [Formula: see text]), and (c) recast [Formula: see text]-positivity as a novel optimization problem over separable states, thereby connecting it explicitly to separability testing. On the generation side, we introduce a Lie-semigroup-based method that, starting from a single [Formula: see text]-positive map, produces one-parameter families that remain [Formula: see text]-positive and nondecomposable for small enough times. We illustrate this by generating such families for [Formula: see text] and [Formula: see text]. We also formulate a semidefinite program (SDP) to test an equivalent form of the positive partial transpose (PPT) square conjecture (and do not find any violation of the latter). Our results provide practical computational tools for certifying [Formula: see text]-positivity and a systematic way to sample [Formula: see text]-positive nondecomposable maps.