arXiv:1111.5425

Are problems in Quantum Information Theory (un)decidable?

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

Published Nov 23, 2011• 32 citations

Abstract

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.

DOI: 10.48550/arxiv.1111.5425

Related papers

Quantum recursion theory

Karl Svozil

Incompleteness and undecidability theorems have to be revised in view of quantum information and computation theory. qrt.tex 1 As has already been pointed out in Gödel’s centennial paper on the incompleteness af arithmetic [1], the classical undecidability theorems of formal logic [2] and the theory of computable functions [4, 5] are based on semantical pardoxes such as the liar [6] or Richard’s paradox. The method of diagonalization, which was first applied by Cantor for a proof of the undenumerability of real numbers [7], has been applied by Turing for a proof of the recursive undecidability of the halting problem [8]. The halting problem is the problem of whether or not an arbitrary algorithm terminates or produces a particular output and terminates. Assume that the halting problem is decidable. Turing [8] proved that this assumption yields a contradiction. To construct the contradiction, consider

arXiv:hep-th/9412048Dec 6, 19944 citations

On the undecidability of quantum channel capacities

Archishna Bhattacharyya, Arthur Mehta, Yuming Zhao

An important distinction in our understanding of capacities of classical versus quantum channels is marked by the following question: is there an algorithm which can compute (or even efficiently compute) the capacity? While there is overwhelming evidence suggesting that quantum channel capacities may be uncomputable, a formal proof of any such statement is elusive. We initiate the study of the hardness of computing quantum channel capacities. We show that, for a general quantum channel, it is QMA-hard to compute its quantum capacity, and that the entanglement-assisted zero-error capacity under some restrictions is uncomputable; indicative of the fact that quantum channel capacities may generally be undecidable.

quant-pharXiv:2601.22471Feb 2, 20260 citations

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

Grzegorz Pastuszak, Adam Skowyrski, Andrzej Jamiołkowski

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.

arXiv:2003.07772Communications in Contemporary MathematicsNov 20, 20203 citations

A Quantum Gate as a Physical Model of an Universal Arithmetical Algorithm without Church's Undecidability and Godel's Incompleteness

Vladan Panković, Milan Predojević

In this work we define an universal arithmetical algorithm, by means of the standard quantum mechanical formalism, called universal qm-arithmetical algorithm. By universal qm-arithmetical algorithm any decidable arithmetical formula (operation) can be decided (realized, calculated. Arithmetic defined by universal qm-arithmetical algorithm called qm-arithmetic one-to-one corresponds to decidable part of the usual arithmetic. We prove that in the qm-arithmetic the undecidable arithmetical formulas (operations) cannot exist (cannot be consistently defined). Or, we prove that qm-arithmetic has no undecidable parts. In this way we show that qm-arithmetic, that holds neither Church's undecidability nor Godel's incompleteness, is decidable and complete. Finally, we suggest that problems of the foundation of the arithmetic, can be solved by qm-arithmetic.

arXiv:quant-ph/0602009Feb 1, 20060 citations

Five Open Problems in Quantum Information Theory

Paweł Horodecki, Łukasz Rudnicki, Karol Życzkowski

We identify five selected open problems in the theory of quantum information, which are rather simple to formulate, are well studied in the literature, but are technically not easy.As these problems enjoy diverse mathematical connections, they offer a huge breakthrough potential.The first four concern existence of certain objects relevant for quantum information, namely a family of symmetric informationally complete generalized measurements in an infinite sequence of dimensions, mutually unbiased bases in dimension six, measurements saturating multiparameter Cramér-Rao bound and bound entangled states with negative partial transpose.The fifth problem requires checking whether a certain state of a two-ququart system is two-copy distillable.

PRX QuantumMar 3, 202295 citations

How to transform graph states using single-qubit operations: computational complexity and algorithms

Axel Dahlberg, Jonas Helsen, Stephanie Wehner

Abstract Graph states are ubiquitous in quantum information with diverse applications ranging from quantum network protocols to measurement based quantum computing. Here we consider the question whether one graph (source) state can be transformed into another graph (target) state, using a specific set of quantum operations (LC + LPM + CC): single-qubit Clifford operations (LC), single-qubit Pauli measurements (LPM) and classical communication (CC) between sites holding the individual qubits. This question is of interest for effective routing or state preparation decisions in a quantum network or distributed quantum processor and also in the design of quantum repeater schemes and quantum error-correction codes. We first show that deciding whether a graph state |G⟩ can be transformed into another graph state |G′⟩ using LC + LPM + CC is N P -complete, which was previously not known. We also show that the problem remains NP-complete even if |G′⟩ is restricted to be the GHZ-state. However, we also provide efficient algorithms for two situations of practical interest. Our results make use of the insight that deciding whether a graph state |G⟩ can be transformed to another graph state |G′⟩ is equivalent to a known decision problem in graph theory, namely the problem of deciding whether a graph G′ is a vertex-minor of a graph G. The computational complexity of the vertex-minor problem was prior to this paper an open question in graph theory. We prove that the vertex-minor problem is N P -complete by relating it to a new decision problem on 4-regular graphs which we call the semi-ordered Eulerian tour problem.

arXiv:1805.05306Quantum Science and TechnologyJul 20, 20206 citations