ar
X

iv
:1

11
1.

54
25

v1
  [

qu
an

t-
ph

]  
23

 N
ov

 2
01

1

Are problems in Quantum Information Theory (un)decidable?

Michael M. Wolf∗, Toby S. Cubitt†, David Perez-Garcia‡

November 24, 2011

Abstract

This note is intended to foster a discussion about the ex-
tent to which typical problems arising in quantum infor-
mation 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 onen ∈ N, however, effective proce-
dures seem to be difficult if not impossible to find. We
review some of the main tools for (dis)proving decidabil-
ity and apply them to problems in quantum information
theory. We find that questions like ”can we overcome fi-
delity 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.

Contents

1 Introduction 1

2 Decidable problems 2
2.1 A general tool from Tarski and Seidenberg . 2
2.2 Entanglement . . . . . . . . . . . . . . . . 4
2.3 n-distillability . . . . . . . . . . . . . . . . 4
2.4 Existence of an(n,m)-hidden variable

model . . . . . . . . . . . . . . . . . . . . 4
2.5 Existence of ad−dimensional quantum

representation . . . . . . . . . . . . . . . . 4
2.6 Birkhoff property . . . . . . . . . . . . . . 4
2.7 n−shot zero-error capacity . . . . . . . . . 4
2.8 Additive minimal output entropy . . . . . . 5

∗Department of Mathematics, Technische Universität München,
Email: m.wolf@tum.de

†Departamento de Analisis Matematico, U. Complutense de Madrid
‡Departamento de Analisis Matematico, IMI, U. Complutense de

Madrid

3 Undecided problems 5
3.1 Distillability: . . . . . . . . . . . . . . . . 5
3.2 LHV models: . . . . . . . . . . . . . . . . 5
3.3 Quantum representation for correlations: . . 5
3.4 Birkhoff property: . . . . . . . . . . . . . . 6
3.5 Zero error-capacities: . . . . . . . . . . . . 6
3.6 (Non-)additivity of other capacities: . . . . 6
3.7 More problems . . . . . . . . . . . . . . . 6

4 Undecidable problems 6
4.1 Tools for proving undecidability . . . . . . 6

The halting problem. . . . . . . . . . . . 6
Post’s correspondence problem . . . . . 7
Diophantine equations. . . . . . . . . . . 7

4.2 Reachability of fidelity thresholds is unde-
cidable . . . . . . . . . . . . . . . . . . . . 7

5 Discussion 9

1 Introduction

The elementary objects of quantum information theory are
often rather simple small dimensional matrices—for in-
stance representing density matrices, quantum channels or
observables. In spite of their innocent looking mathemati-
cal description, their properties can be difficult to compute
quantitatively or even to decide qualitatively: Is a given
quantum state entangled? Is it distillable? Does it admit a
local hidden variable description? Is a quantum channel a
mixture of unitaries? Does it have non-zero quantum ca-
pacity? None of these questions seems to have a simple
answer.

From an abstract point of view, the difficulty in decid-
ing such questions arises from quantification over infinite
sets. That is, answering these questions requires taking for
instance all decompositions, protocols, models, codings,
etc. into account. Moreover, in particular information the-
oretic questions often involve asymptotic limits regarding

1

http://arxiv.org/abs/1111.5425v1


the numbers of copies, rounds within a protocol, measure-
ments, etc..

In the present work we analyse problems like the ones
mentioned above from the point of view of algorithmic de-
cidability. This means we don’t ask (at least not on the
following pages) whether there are resource-efficient algo-
rithms, we rather want to know whether there isany effec-
tive algorithm, irrespective of the scaling of resources.

One of our motivations—although the following work
is only a minor step in this direction—is to address the
(im)possibility of “single-letter” formulas/criteria, espe-
cially for asymptotically defined quantities. Clearly, those
arise not only in information theoretic contexts but rather
naturally also in statistical physics, where phases and their
properties are defined in the thermodynamic limit. In the
present paper we will, however, focus exclusively on prob-
lems occurring in quantum information theory.1 Moreover,
we will restrict ourselves to decidability problems and, for
the moment, leave closely related questions of (quantita-
tive) computability aside.2

We will go through three stages: decidable problems
(Sec.2), undecided problems (Sec.3), and undecidable
problems (Sec.4). The notion of decidability which we
have in mind is the one of recursive function theory rather
than, for instance, the one of real computation (as in
[BCSS97]).

Others have followed similar lines: decidability prob-
lems in quantum automata were for instance studied in
[BJKP05, DJK05, Hir08] and results on quantum impli-
cations and interpretations of the undecidable ’matrix mor-
tality’ problem are found in [JE].

2 Decidable problems

As already mentioned in the introduction, deciding proper-
ties of quantum information theory often involves taking
for instance all decompositions, protocols, models, cod-
ings, etc. into account. Mathematically this can be ex-
pressed in terms of quantification over the respective sets.
In this section we discuss a general tool for proving decid-
ability via elimination of all these quantifiers.

1Undecidablility of properties of quantum spin chains will be the con-
tent of a separate article [CPGW].

2Note that a quantity, e.g. some capacity, might be computable al-
though it is undecidable whether or not it is different from zero.

2.1 A general tool from Tarski and Seiden-
berg

Let us introduce the general idea via a simple example: if
a1 anda2 are real numbers, then the equationa1x2 > a2
has a real solution iffa2 is negative ora1 is positive. More
formally,

∃x a1x
2 > a2, (1)

⇔ a2 < 0 ∨ a1 > 0. (2)

That is, in Eq.(2) we have a quantifier-free expression
which has the same truth value as the initial formula in
Eq.(1).

Tarski [Tar51] and Seidenberg [Sei54] have shown that
such an elimination of both existential∃ and universal∀
quantifiers is possible in a more general context. Suf-
ficient requirements are that the initial formula (i) con-
tains real variables and parameters together with the ob-
jects and relations1, 0,+, ·, >,= of the ordered real field,
and (ii) is expressed in first-order logic. The latter means
that in addition to quantifiers over individual variables the
formula is allowed to involve Boolean operations∨,∧,¬
and brackets for unambiguous readability. Something like
∀n ∈ N . . . or quantification over sets, however, is not al-
lowed. A more precise formulation of the underlying theo-
rem is (cf.[Mar08]):

Theorem 1 (Tarski-Seidenberg, quantifier elimination)
LetR be a real closed field. Given a finite set{fi(x, a)}ki=1

of polynomial equalities and inequalities with variables
(x, a) ∈ Rn × Rm and coefficients inQ. Letφ(x, a) be a
Boolean combination of thef ′

is (using∨,∧,¬) and

Ψ(a) :=
(

Q1x1 . . . Qnxn : φ(x, a)
)

, Qj ∈ {∃, ∀}. (3)

Then there exists a formulaψ(a) which is (i) a quantifier-
free Boolean combination of finitely many polynomial (in-)
equalities with rational coefficients, and (ii) equivalentin
the sense

∀a :
(

ψ(a) ⇔ Ψ(a)
)

. (4)

Moreover, there exists an effective algorithm which con-
structs the quantifier-free equivalentψ of any such formula
Ψ.

A real closed fieldis an ordered field which satisfies the
intermediate value theorem for polynomials. Examples are
the fieldR of real numbers, the field of computable real
numbers and the fieldRA of algebraic real numbers. Algo-
rithms for quantifier elimination are effective but not gen-
erally efficient [BPR94]. For a comparison of some of the
implemented algorithms see [DSW98].

2



Suppose now we want to decide whether or not some
Ψ(a) is true for givena. Then we can use quantifier elim-
ination in order to obtain a simpler, quantifier-free expres-
sionψ(a), so that it remains to check a set of (in-)equalities
for polynomials in theai’s, like in Eq.(2) of our example.
In order for this to be feasible we need acomputable or-
dered fieldin which the basic operations·,+ as well as the
relations=, > are computable. The latter is not the case for
the fields of real or computable real numbers—being able
to compute an arbitrary number of decimals fora1 is not
sufficient for an effective procedure for decidinga1 > 0.

In the following we restrict the parametersa to any com-
putable ordered fieldRc which is real closed and con-
tains the field of algebraic numbersRalg. The latter forms
a computable ordered and real closed field on its own
[LM70] so that we may simply setRc = Ralg. With
some care, however, including (computable) transcenden-
tal numbers is possible: one can for instance start with
non-algebraic extension fields ofQ as in [O.L09] and then
use the fact that any real closure of a computable ordered
field is again a computable ordered field [Mad70]. By
Cc := Rc(

√
−1) we will denote the algebraic closure of

Rc. If for instanceRc = Ralg, thenCc is the field of
complex algebraic numbers.

In spite of all this, we will apply Thm.1 toR = R, since
the problems we will discuss involve quantification over
the reals.

Problems arising in quantum information theory often
involve quantification over matrices or linear maps, such
as unitaries, positive semidefinite matrices, positive or
completely positive maps, matrices with bounded rank or
bounded norm, etc. Moreover, relevant inequalities are of-
ten w.r.t. the semidefinite partial ordering of Hermitian ma-
trices.

Before discussing specific problems from quantum in-
formation theory, we will convince ourselves that the
Tarski-Seidenberg trick works as well if quantification is
over any of the sets just mentioned. We will denote by
Md(G) the set ofd× d matrices with entries inG.

Lemma 1 Let x ∈ R

2d2

be a vector containing the real
and imaginary parts of a matrixX ∈ Md(C). The mem-
bership relationX ∈ S is equivalent to a Boolean combi-
nation of polynomial (in-)equalities inx with integral co-
efficients, ifS ⊂ Md(C) is one of the following sets:

1. the setpositive semidefinitematrices,

2. the set ofdensity matrices,

3. the set ofunitaries,

4. the set of Hermitian matrices withbounded norm
||X ||p ≤ 1 for anyp ∈ N ∪ {∞},

5. the set of matrices withconstrained rankrank(X) = r
for anyr ≤ d.

Proof. 1. follows from the fact thatX ≥ 0 holds iffX =
X† and all the principal minors ofX are non-negative.

2. follows from 1. and the linear equationtr [X ] = 1.
3. follows from the quadratic equationX†X = 1.
4. since||X ||∞ ≤ 1 iff (1 − X†X) ≥ 0 we can use

1. For p ∈ N we obtain a polynomial inequality from
tr [Xp] ≤ 1.

5. follows from the fact that the rank is the size of the
largest non-vanishing minor.

In general, sets which can be characterized by means
of polynomial (in)-equalities in a finite-dimensional real
vector space are calledsemialgebraic.

We will call a relationF onMd1
(C) × . . .×MdK

(C)
a polynomial matrix equation with rational coefficientsiff
it can be expressed aŝF (M1, . . . ,MK) ⊲ 0, whereF̂ is a
matrix (possibly one-dimensional) whose entries are poly-
nomials in the entries of theMi’s with rational coefficients
and⊲ ∈ {>,≥,=}. The inequalities refer to the partial
order induced by the cone of positive semidefinite matri-
ces.

The above Lemma together with the Tarski-Seidenberg
theorem now leads to the following useful observation:

Corollary 1 LetA be a tuple of matrices with entries in
Cc and let {Fi(X,A)}ki=1 be a finite set of polynomial
matrix equations with rational coefficients and variables
X ∈ Md1

(C)× . . .×Mdn
(C). Given a Boolean combi-

nationφ(X,A) of theFi’s and

Ψ(A) :=
(

Q1(X1 ∈ S1) . . . Qn(Xn ∈ Sn) : φ(X,A)
)

,

(5)
whereQj ∈ {∃, ∀} and theSi’s are semialgebraic sets
(e.g. those specified in Lemma 1). Then there exists an
effective algorithm which decidesΨ(A).

This corollary uses Thm.1 after we have expressed every-
thing in terms of the real and imaginary parts of the ma-
trix entries, used Lemma 1 and brought the equation into
prenex normal form. After the quantifier elimination we
then exploit thatA is specified over a computable ordered
field which finally admits an effective algorithm.

Let us apply this observation to some standard problems
in the context of entanglement and quantum channels. All
the problems discussed in the remainder of this section are

3



such that they involve quantification (∃, ∀) over semialge-
braic sets, like the ones in Lemma 1, and a semialgebraic
equation to be checked. Consequently, Cor.1 applies to all
of them.

2.2 Entanglement

A density matrixρ ∈ Md(C)
⊗n is calledclassically cor-

relatedor unentangled[Wer89] iff there exist sets of den-
sity matrices{ρ(α)i ∈ Md(C)}d

2n

i=1 for α = 1, . . . , n and a
probability vectorλ ∈ Rd2n

such that3

ρ =
∑

i

λiρ
(1)
i ⊗ · · · ⊗ ρ

(n)
i . (6)

If the entries ofρ are taken fromCc, then the question
whether or notρ is entangled is of the form in Cor.1 and
can thus be effectively decided.

2.3 n-distillability

A density matrixρ ∈ Md(Cc)
⊗2 is n−distillable iff there

exists a rank-2 matrixY ∈ Mdn(C) such that

〈y|
(

ρ⊗n
)T1 |y〉 < 0, (7)

where |y〉 =
∑

k,l Yk,l|k, l〉 and T1 denotes the partial
transposition (both understood w.r.t. the bipartite rather
than then-partite partitioning). For fixedn ∈ N this is
again such that Cor.1 implies an effective decision proce-
dure.

2.4 Existence of an(n,m)-hidden variable
model

Let P (i, j|k, l) be a conditional probability distribution
so that

∑m

i,j=1 P (i, j|k, l) = 1 for all k, l = 1, . . . , n.

P ∈ R

m2n2

admits a local hidden variable(LHV)
model [WW01] iff there exists a non-negative matrixΛ ∈
Mmn(R) satisfying

∑

a,b Λa,b = 1 such that for all
i, j, k, l it holds that

P (i, j|k, l) =
∑

a,b

Λa,b δa(k),i δb(l),j , (8)

wherea, b ∈ {1, . . . ,m}n. We say that a bipartite density
matrix ρ ∈ Md(Cc)

⊗2 admits an(n,m)-hidden variable
description iff the distribution

P (i, j|k, l) := tr
[

ρ
(

Q
(k)
i ⊗ P

(l)
j

)

]

(9)

3The bound on the range ofi, which is not part of the definition, fol-
lows from Caratheodory’s theorem.

admits a LHV model for all sets of POVMs{Q(k)
i ∈

Md(C)} and {P (l)
j ∈ Md(C)}, where i, j label the

m effect operators of each of the2n POVMs. Since
the latter are again characterized by semialgebraic means,
the question whether or not a quantum state admits an
(n,m)-hidden variable description is effectively decidable
by Cor.1. Note that the quantifier structure of this prob-
lem involves also universal quantifiers as it is of the form
∀Q∀P∃Λ . . ..

2.5 Existence of ad−dimensional quantum
representation

Conversely, we may ask whether a probability distribu-
tion P ∈ R

m2n2

c admits ad−dimensional quantum rep-
resentation in the sense that there exists a density matrix
ρ ∈ Md(C)

⊗2 and sets of POVMs{Q(k)
i ∈ Md(C)} and

{P (l)
j ∈ Md(C)} such that Eq.(9) holds for alli, j, k, l.

Again Cor.1 applies.

2.6 Birkhoff property

Let us turn to quantum channelsT : Md(C) → Md(C),
i.e., completely positive, trace-preserving linear maps.For
a unital quantum channel, i.e., one which satisfiesT (1) =
1 in addition, there may exist ann ∈ N, unitaries{Ui ∈
Mdn(C)} and a probability vectorλ such that

T⊗n(ρ) =
∑

i

λiUiρU
†
i for all ρ. (10)

For d = 2 this holds in fact for all unital quantum chan-
nels (even forn = 1). However, it fails to be generally
true if d ≥ 3 [HM11]. Since we can bound the range
of the index by Caratheodory’s convex hull theorem to
i = {1, . . . , d4n} the problem of deciding whether a uni-
tal quantum channel can be represented as in Eq.(10) again
falls into the field of activity of Cor.1 ifn is fixed and the
channel’s Choi matrix or its Kraus operators are overCc.

2.7 n−shot zero-error capacity

A quantum channelT : Md(C) → Md(C) has a non-
vanishingn−shot classical zero-error capacity, iff there
exist density matricesρ, σ ∈ Mdn(C) such that

tr
[

T⊗n(ρ)T⊗n(σ)
]

= 0. (11)

One more time, since the quantification is over the set
of density matrices and all equations are (semi-)algebraic,
Cor.1 applies for any fixedn ∈ N.

4



More generally, then−shot classical zero-error capacity
is greater thanlogm/n iff there existm density matrices
ρi ∈ Mdn(C) (i = 1 . . .m) such that

tr
[

T⊗n(ρi)T
⊗n(ρj)

]

= 0 (12)

for all i 6= j and Cor.1 applies once again for any fixed
n,m ∈ N.

2.8 Additive minimal output entropy

For anyp ∈ N ∪ {∞} define a functionalνp on the set of
quantum channels by

νp(T ) := sup
{

||T (ρ)||p
∣

∣ρ ≥ 0 ∧ tr [ρ] = 1
}

, (13)

and consider the decision problem whether or not

νp
(

T ⊗ T ′
)

= νp(T )νp(T
′), (14)

holds for all quantum channelsT ′ : Md(C) → Md(C)
of a fixed dimension. Since the l.h.s. in Eq.(14) is always
lower bounded by the r.h.s., this problem can be phrased
using quantifiers (over the respective sets) in the following
way:

∃ρ1∀T ′∃ρ2∀ρ12 : ||(T⊗T ′)(ρ12)||p ≤ ||T (ρ1)||p||T ′(ρ2)||p.
(15)

Note that all sets and equations are semialgebraic. Hence,
for fixedp andd, Cor.1 implies the existence of an effective
algorithm which, upon input of a finite-dimensional chan-
nelT which is defined overCc, determines the truth-value
of Eq.(15).

3 Undecided problems

Consider the problems discussed in 2.2 to 2.8 of the last
section again. Apart from 2.2, all problems share the
appearance of one or more integers whose quantification
leads to a more fundamental problem. However, adding
such a “∃n ∈ N” or “ ∀n ∈ N” disables the Tarski-
Seidenberg tool and leaves us with problems for which, to
the best of our knowledge, no effective procedure is cur-
rently known. The catch is, that for everyn ∈ N we have
an effective procedure, but as long as there is no upper
bound on the “largest relevant”n, these cannot be com-
bined to a universal effective algorithm. Of course, for
some of the discussed problems quantification over the re-
maining integer(s) may eventually again lead to a semial-
gebraic set for which membership can be decided using
Tarski-Seidenberg.

Let us have a closer look, problem by problem.

3.1 Distillability:

A bipartite quantum state is calleddistillable iff there ex-
ists ann ∈ N such that it isn−distillable. In this case, it
was shown in [Wat04] that there is indeed no dimension-
dependent upper bound: for anyn there exist a density
matrix acting onC9 ⊗ C9 such that the state is distill-
able but notn−distillable. At present it is not known
whether or not being not distillable coincides with the
property of the density matrix having a positive partial
transpose. If this would be true, then distillability would
be decidable since, as we’ve seen in Lemma1, positive
semi-definiteness is a semialgebraic relation. Conversely,
this means that undecidability of distillability would im-
ply the existence of undistillable states whose partial trans-
pose is not positive—with all its puzzling consequences
[SST01, VW02].

3.2 LHV models:

Regarding the existence of a universal hidden variable
model (one which holds for alln,m ∈ N) for a given den-
sity matrix, not much seems to be known. There are quan-
tum states which are entangled and nevertheless admit such
a universal LHV model [Wer89, Bar02]. However, it is also
clear that there are states which admit a LHV description
for n = m = 2 but fail to do so for largern orm.

3.3 Quantum representation for correla-
tions:

The relevant integral parameter in the problem raised in 2.5
is d ∈ N, so that the underlying question is: given a proba-
bility distributionP (i, j|k, l) is there anyd ∈ N for which
there exists a quantum representation. To the best of our
knowledge, this question is still open. There is some evi-
dence [PV10] that already forn = 3,m = 2 the dimension
d might be generally unbounded or even infinite. The re-
cent connection between Tsirelson’s problem and the long
standing Connes’ embedding problem [JNP+11, Fri] also
points in this direction. This could explain why attempts
to find a characterization of the set of quantum correla-
tions, like the hierarchy of semidefinite relaxations given
in [NPA07], lead in the worst case scenario to infinite run-
ning times.

5



3.4 Birkhoff property:

For d = 3 there are unital quantum channels known for
which Eq.(10) does not hold forn = 1 but becomes true
for n = 2 [MW09]. It is also known that the set of channels
for which there exists such ann ∈ N is a subset of the so-
calledfactorizablechannels [HM11].

3.5 Zero error-capacities:

Already in the case of the zero-error capacity ofclassical
channels, it is known that there is no upper bound on the
block-lengthn required to achive the capacity (see [KO98]
and references therein). Since classical channels are a spe-
cial case of quantum channels, this carries over immedi-
ately to the classical zero-error capacity of quantum chan-
nels.

In the important case of deciding whether the zero-error
capacity vanishes, classical channels are no longer any use,
since it is trivial to see that then−shot zero-error capacity
of a classical channel vanishes iff it vanishes forn = 1.
Thanks to entanglement, this isnot true for quantum chan-
nels. A simple implication of the superactivation results of
[CCH, Dua] is that there exist quantum channels for which
the1−shot capacity vanishes but the2−shot capacity does
not, but it is not known at present whether this extends to
arbitraryn.

3.6 (Non-)additivity of other capacities:

The maximal outputp−norm is known not to be multi-
plicative in general [HW02, WH08, Has09]. Channels for
which multiplicativity of the formνp(T

⊗2) = νp(T )
2

has been proven, are often such thatνp(T ⊗ T ′) =
νp(T )νp(T

′) holds for anyT ′ irrespective of its dimension.
The failure of additivity of various single-shot quanti-

ties (such as the minimal output entropy corresponding to
νp for p → 1) leads to the fact that we do currently nei-
ther have a single-letter formula for the classical capacity
of quantum channels nor for its quantum capacity. The lat-
ter is known to be itself non-additive in the strong sense
that 0 + 0 > 0 [SY08]. Questions like “is the quantum
capacity zero?” or, if it is, “can it be activated by another
zero-capacity channel” also seem undecided.

3.7 More problems

The above list can easily be extended as there are numerous
problems which involve quantification over one or several
integers. Further examples would be: is a quantum channel

implementable by means of LOCC (for which there is no
a priori bound on the number of required rounds)? Can a
source or a channel asymptotically simulate another one at
a pre-given rate and under given constraints? Etc.

4 Undecidable problems

4.1 Tools for proving undecidability

Before we briefly review some tools for proving that a
problem isalgorithmically undecidable, let us recall what
this means and implies. The reader familiar with the basic
notions of computability theory may skip this subsection.
The reader not satisfied by it may consult [Cut80, Bar77].

Informally, analgorithmis an effective procedure based
on finitely many instructions which can be carried out in
a stepwise fashion. Crucial for this notion is that there
has to be a finite description. Any formal definition has
to specifywho is carrying outwhat kind of instructions.
The two historically first frameworks which made this pre-
cise wereTuring machinesandrecursive function theory.
However, any other reasonable framework people came up
with turned out to be no more powerful than those. That
this will continue to hold in the future is the content of the
Church-Turing thesis.

For a decision problem to be algorithmically undecid-
able, an infinite domain is necessary. Suppose there were
only finitely many, sayN , distinct inputs for which we
want a yes-no question to be decided. Then we may write
one algorithm for each of the2N truth-value assignments
and since this exhausts all possibilities one of the algo-
rithms will return the correct answer for all the inputs.4

Finite problems are thus decidable which, for the problems
we have discussed, implies that introducing “ǫ-balls” will
make them algorithmically decidable (although we still
wouldn’t know the algorithm). An infinite domain, on the
other hand, should be countable infinite, since otherwise
the inputs have no finite description.

Requiring algorithms to have a finite description and
considering decision problems with countable infinite do-
mains already implies that there are undecidable problems
(viewed as subsets ofN) since algorithms are countable but
decision problems aren’t, i.e.,|N| < |2N|.

The halting problem is the mother of all undecidable
problems. This is not only true historically, but also techni-
cally: most problems which are known to be undecidable

4We tacitly assume thetertium non datur.

6



are proven to be so by showing that the halting problem
can (directly or indirectly) be reduced to them. The halting
problem asks whether a Turing machine halts upon a given
input. If we identify the inputs with natural numbers, then
the subset ofN upon which a fixed Turing machine halts
is calledrecursively enumerable—a notion we will come
back to later. Clearly, membership in a recursively enu-
merable set cannot generally be decidable since otherwise
the halting problem would be decidable.

Post’s correspondence problem (PCP) is an example
of an undecidable problem to which the halting problem
can be reduced. It is frequently used as an intermediate
step in undecidability proofs by reducing it in turn to the
problem under consideration.

LetA be a finite alphabet for which we consider the set
of wordsA∗ as a monoid with respect to whichX,Y :
K → A∗ are two homomorphisms fromK = {1, . . . , k}.
Post‘s correspondence problem is then to decide whether
or not there is a non-empty wordw ∈ A∗ such that
X(w) = Y (w). An equivalent, possibly more intuitive,
depiction of the problem is to think aboutk types of domi-
nos and ask whether they admit a finite chain in which the
upper row coincides with the lower row.

While PCP is decidable ifk = 2, it’s known to be un-
decidable fork ≥ 7 [MS05]. In fact, it is undecidable
whether there is a so-calledClaus instancesolution of the
form 1w7 with w ∈ {2, . . . , 6}∗ (cf. [Har09]).

The main reason why we emphasize PCP, is that it can
be reduced to problems involving products of matrices—
something we will make use of in the next subsection. The
main tool in this context is a monoid morphism due to Pa-
terson [Pat70]: takeA = {1, . . . ,m} and define an in-
jection σ : A∗ → N as them−adic representation of
words, i.e.,σ(w) =

∑|w|
j=1 wjm

|w|−j where|w| denotes
the length of the word andσ maps the empty word onto
0. Note thatσ(uw) = m|w|σ(u) + σ(w). The map
γ : A∗ ×A∗ → M3(N0)

γ(u,w) :=





m|u| 0 0

0 m|w| 0
σ(u) σ(w) 1



 , (16)

is then a monoid monomorphism, i.e., it holds that
γ(uu′, ww′) = γ(u,w)γ(u′, w′). Defining vectors|x〉 :=
(1,−1, 0)T and〈y| := (0, 0, 1) this implies thatu = w, as
required by a PCP solution, holds iff〈y|γ(u,w)|x〉 = 0. If
one wants to have a non-negative expression of this type (as
in the following subsection), one can take the square, ex-
press it in terms ofγ ⊗ γ and restrict to the anti-symmetric

subspace—Lemma 3 is based on such a representation (cf.
[BC01, Hir07] for more details).

One of the problems to which PCP can be reduced is
the matrix mortality problem. This asks whether a set of
matricesM := {Mi ∈ Md(Z)}ki=1 admits a finite string
of products for whichMi1 · · ·Min = 0. M is then called
’mortal’. In [JE] this has been applied to quantum informa-
tion problems by constructing a setM ′ ⊂ Md′(Q) which
is mortal iffM is, and which in addition can be interpreted
as a set of ’Kraus operators’ for which

∑

j M
′
jM

′†
j = 1.

Note that by allowing algebraic entries, one can simply
achieve this by settingM ′

i := X−1MiX/
√
λ using a pos-

itive eigenvector
∑

iMiX
2M †

i = λX2 which is always
guaranteed to exist.5

Diophantine equations. A subsetD ∈ N is called
diophantineiff for some n ∈ N there is a polynomial
p : Nn+1 → N with integer coefficients, such that

D = {x|∃y ∈ Nn : p(x, y) = 0}. (17)

W.l.o.g. one can bound the degree of the polynomial by
4 and, at the same time, the number of variablesn ≤ 56.
A remarkable theorem [DMR76], which eventually proved
the undecidability of Hilbert’s 10th problem, states that a
set is diophantine if and only if it is recursively enumerable.
Since membership is generally undecidable for the latter,
the same has to hold for the former. This result should
be compared with the earlier mentioned Tarski-Seidenberg
theorem. While Thm.1 implies that the existence of roots
of a system of polynomial equations with integer coeffi-
cients can be decided overR, the same problem becomes
undecidable overN. Whether it is decidable overQ is still
an open problem.

So much for general undecidability in a nutshell. Let’s
have a look at a specific problem and apply some of the
mentioned results.

4.2 Reachability of fidelity thresholds is un-
decidable

As an example which naturally occurs in the context of
quantum information theory, we will discuss the problem
of deciding whether a small set of “noisy gates” allows

5If there is no positive definite eigenvectorX2, one can replace the
Mi’s by a direct sum of their irreducible blocks, for which the correspond-
ing positive map then has a positive definite eigenvector. The advantage
of usingRalg instead ofQ is that the number of matrices and their size
doesn’t change when going fromM toM ′. In this way the argumentation
in [JE] then holds for(d, k) = (3, 7) rather than only for(15, 9).

7



to create a state which overcomes some pre-given fidelity
threshold w.r.t. a given target state. The latter might for
instance be a two-qubit singlet state and the aim, motivated
by the requirements of entanglement distillation protocols,
to achieve an overlap strictly larger than one half.

In the following we will for simplicity letR andC de-
note the fields of real and complex algebraic numbers re-
spectively.

Theorem 2 Let (k, d) be a pair of integers which is ei-
ther (2, 5) or (5, 3) (or pointwise larger than either) and
take any real number0 < λ < 1 and normalized vec-
tor |φ〉 ∈ Cd. Then, there is no algorithm which upon
input of a density matrixρ ∈ Md(C) and of a set of

quantum channels
{

Ti : Md(C) → Md(C)
}k

i=1
decides

whether or not there is an integern ≥ 1 and a sequence
(i1, . . . , in) ∈ {1, . . . , k}n for which

〈φ| Ti1 · · ·Tin(ρ) |φ〉 > λ. (18)

The proof of this theorem is decomposed into two steps:
(i) we establish a mapping from unconstrained matrices
to quantum channels in such a way that concatenations of
channels are closely linked to products of matrices, and
(ii) we exploit known undecidability results for problems
which are expressed in terms of products of matrices.

Let {Hi ∈ Md(C)}d
2

i=1 be any Hermitian operator basis
which is orthonormal in the sense thattr [HiHj ] = δi,j and
satisfiesH1 = 1/

√
d. Note that the latter impliestr [Hi] =

0 for all i > 1.
We represent any linear mapT : Md(C) → Md(C)

in terms of a d2 × d2 matrix with entries T̂i,j :=

tr [HiT (Hj)]. T is Hermiticity preserving iffT̂ is real,
and trace-preserving iff the first row of̂T is (1, 0, . . . , 0).

Lemma 2 Let d ≥ 2 andH2 := (1 − dψ)/(
√
d2 − d)

for any one-dimensional projectorψ = |ψ〉〈ψ| ∈
Md(C). For everyM ∈ Md2−2(R) and everyν ∈
(−

√
d− 1, 1/

√
d− 1) there exists anǫ > 0 such that

T̂ :=

(

1 0
ν 0

)

⊕ ǫM (19)

represents a completely positive, trace-preserving linear
map.

Proof. By constructionT̂ represents a trace-preserving
and Hermiticity preserving linear map. First note that for
ǫ = 0 the matrixT̂ corresponds to the map

T (X) =
tr [X ]

d

(

1+
ν√
d− 1

(1− dψ)

)

. (20)

The Choi matrix of this map is positive definite iff

1+
ν√
d− 1

(1− dψ) > 0, (21)

which holds in turn iffν ∈ (−
√
d− 1, 1/

√
d− 1). Within

this range, full support of the Choi matrix then allows us to
add a sufficiently small multiple of any other Hermiticity
preserving map without violating complete positivity.

Proposition 1 Let d ≥ 2, λ ∈ (0, 1) and let φ =
|φ〉〈φ| be a one-dimensional projector acting onCd. For
any x, y ∈ R

d2−2 and any set of matrices{Mi ∈
Md2−2(R)}ki=1, one can construct a set of quantum chan-
nels {Ti : Md(C) → Md(C)}ki=1, a density matrix
ρ ∈ Md(C) and positive numbersǫ, δ > 0 such that for
all natural numbersn ≥ 1

tr [φTi1 · · ·Tin(ρ)] = λ+ δǫn〈x|Mi1 · · ·Min |y〉 (22)

holds for all sequences(i1 . . . in) ∈ {1, . . . , k}n.

Proof. First of all, we exploit the freedom in the choice
of the Hermitian and orthonormal operator basis{Hi}.
As indicated above, we fixH1 := 1/

√
d,H2 := (1 −

dψ)/(
√
d2 − d), with ψ 6= φ to be chosen later, and we

chooseH3, . . . , Hd2 such that up to some factorδ1 > 0 we
havetr [φHi+2] = δ1xi for all i = 1, . . . d2 − 2.

We defineρ ∈ Md(C) in this basis as being represented
by the vector

(

1/
√
d, 0, δ2y

)

. In this way,ρ = ρ†, tr [ρ] =
1 and we can chooseδ2 > 0 sufficiently small, so that
ρ ≥ 0.

To every matrixMi we assign a quantum channelTi of
the form in Eq.(19) where a commonǫ > 0 is chosen such
all theTi’s are completely positive. In this way, we obtain

tr [φTi1 · · ·Tin(ρ)] =
1

d

(

1 + ν
1− d|〈ψ|φ〉|2√

d− 1

)

(23)

+δǫn〈x|Mi1 · · ·Min |y〉, (24)

where we have setδ := δ1δ2. By choosing appropriateν ∈
(−

√
d− 1, 1/

√
d− 1) andψ 6= φ, the r.h.s. of Eq.(23) can

be set to any value in the open interval(0, 1) and Lemma 2
guarantees that theTi’s are completely positive and trace-
preserving as requested.

The following Lemma is distilled from [Hir07] where
it has been proven by reduction from PCP with Claus in-
stances:

Lemma 3 Let (k,m) be either(5, 6) or (2, 21). There is
no algorithm which upon input of vectorsx, y ∈ Zm and

8



of matrices{Mi ∈ Mm(Z)}ki=1 decides whether or not
there is an integern ≥ 1 and a sequence(i1, . . . , in) ∈
{1, . . . , k}n so that

〈x|Mi1 · · ·Min |y〉 > 0. (25)

Together with the previous proposition this Lemma now
proves Thm.2. Inserting a different classical result [BC01,
Hir07] into Prop.1 we obtain an analogous result in which
> is replaced by≥ in Eq.(18). Variation on the theme of
Prop.1 also allows to use targets other than the overlap with
a given pure state such as the expectation value of some
observable or the overlap with a given quantum channel.

5 Discussion

Loosely speaking: while semi-algebraic problems are de-
cidable, word problems are typically not. We have dis-
cussed to what extent this fact separates quantum informa-
tion problems into decidable and undecidable ones. Many
of the interesting problems, however, remain undecided.

In the direction of proving decidability of some of them,
one approach might be to look into tools which extend
Tarski-Seidenberg in various directions. In [DMM94] it
has for instance been shown that quantifier elimination is
possible for the real field augmented by exponentiation and
all restricted analytic functions. Needless to say, there are
also limitations on the possibility of quantifier elimination,
which are discussed for instance in [GAB07]. Also tools
for deciding specific second-order theories might be worth-
while looking at [Rab69].

In the other direction, most of the known undecidable
problems are, in one way or the other, word problems. It
would therefore be interesting to see a word problem struc-
ture identified in one of the undecided problems we have
discussed. Is there an undecidable word problem where
strings are formed by tensor products rather than by ordi-
nary products?

Acknowledgements:We acknowledge financial sup-
port from the European projects COQUIT and QUE-
VADIS, the CHIST-ERA/BMBF project CQC, the Alfried
Krupp von Bohlen und Halbach-Stiftung and the Spanish
grants I-MATH, MTM2008-01366, S2009/ESP-159 and
QUITEMAD.

References

[Bar77] Jon Barwise, editor.Handbook of mathematical
logic. Elsevier, Amsterdam, 1977.

[Bar02] Jonathan Barrett. Nonsequential positive-
operator-valued measurements on entangled
mixed states do not always violate a bell in-
equality.Phys. Rev. A, 65:042302, 2002.

[BC01] Vincent Blondel and Vincent Canterini. Unde-
cidable problems for probabilistic automata of
fixed dimension.Theory of Computing Systems,
36:231–245, 2001.

[BCSS97] Leonore Blum, Felipe Cucker, Michael Shub,
and Steve Smale.Complexity and real compu-
tation. Springer, 1997.

[BJKP05] Vincent D. Blondel, Emmanuel Jeandel, Pascal
Koiran, and Natacha Portier. Decidable and un-
decidable problems about quantum automata.
SIAM J. Comput., 34:1464–1473, June 2005.

[BPR94] S. Basu, R. Pollack, and M.-F. Roy. On
the combinatorial and algebraic complexity of
quantifier elimination. Foundations of Com-
puter Science, 1994 Proceedings., pages 632 –
641, 1994.

[CCH] Toby S. Cubitt, Jianxin Chen, and Aram W.
Harrow. Superactivation of the asymptotic
zero-error classical capacity of a quantum chan-
nel. arXiv:0906.2547, to appear in IEEE Trans.
Inform. Theory.

[CPGW] Toby S. Cubitt, David Perez-Garcia, and
Michael M. Wolf. to be published.

[Cut80] Nigel J. Cutland.Computability, an introduc-
tion to recursive function theory. Cambridge
University Press, Cambridge, 1980.

[DJK05] Harm Derksen, Emmanuel Jeandel, and Pas-
cal Koiran. Quantum automata and algebraic
groups. Journal of Symbolic Computation,
39(3-4):357 – 371, 2005.

[DMM94] Lou van den Dries, Angus Macintyre, and
David Marker. The elementary theory of re-
stricted analytic fields with exponentiation.The
Annals of Mathematics, 140(1):pp. 183–205,
1994.

9



[DMR76] M. Davis, Yu. Matijacevic, and J. Robinson.
Hilbert’s tenth problem. Diophantine equations:
positive aspects of a negative solution.Proc.
Symposia Pure Math., 28:223–378, 1976.

[DSW98] Andreas Dolzmann, Thomas Sturm, and Volker
Weispfenning. Real quantifier elimination in
practice. InAlgorithmic Algebra and Number
Theory, pages 221–247. Springer, 1998.

[Dua] Runyao Duan. Super-activation of zero-
error capacity of noisy quantum channels.
arXiv:0906.2527.

[Fri] Tobias Fritz. Tsirelson’s problem and Kirch-
berg’s conjecture. arXiv:1008.1168.

[GAB07] ANDREI GABRIELO. Counterexamples to
quantifier elimination for fewnomial and expo-
nential expression.MOSCOW MATHEMATI-
CAL JOURNAL, 7:453–460, 2007.

[Har09] Tero Harju. Post correspondence problem and
small dimensional matrices. In Volker Diek-
ert and Dirk Nowotka, editors,Developments
in Language Theory, volume 5583 ofLec-
ture Notes in Computer Science, pages 39–46.
Springer Berlin / Heidelberg, 2009.

[Has09] M. B. Hastings. A counterexample to additivity
of minimum output entropy.Nature Physics,
5:255, 2009. (arXiv:0809.3972 [quant-ph]).

[Hir07] Mika Hirvensalo. Improved undecidability re-
sults on the emptiness problem of probabilis-
tic and quantum cut-point languages. In Jan
van Leeuwen, Giuseppe Italiano, Wiebe van der
Hoek, Christoph Meinel, Harald Sack, and
Frantiek Plil, editors,SOFSEM 2007: The-
ory and Practice of Computer Science, volume
4362 of Lecture Notes in Computer Science,
pages 309–319. Springer Berlin / Heidelberg,
2007.

[Hir08] Mika Hirvensalo. Various aspects of finite
quantum automata. In Masami Ito and Masa-
fumi Toyama, editors,Developments in Lan-
guage Theory, volume 5257 ofLecture Notes
in Computer Science, pages 21–33. Springer
Berlin / Heidelberg, 2008.

[HM11] Uffe Haagerup and Magdalena Musat. Fac-
torization and dilation problems for com-
pletely positive maps on von neumann al-
gebras. Communications in Mathematical
Physics, 303:555–594, 2011.

[HW02] A. S. Holevo and R. F. Werner. Counterexample
to an additivity conjecture for output purity of
quantum channels.J. Math. Phys., 43:4353–
4357, 2002. arXiv:quant-ph/0203003.

[JE] J. Eisert, M.P. Mueller, C. Gogolin. Quan-
tum measurement occurence is undecidable.
arXiv:1111.3965.

[JNP+11] M. Junge, M. Navascues, C. Palazuelos,
D. Perez-Garcia, V. B. Scholz, and R. F.
Werner. Connes’ embedding problem and
Tsirelson’s problem.Journal of Mathematical
Physics, 52(1):012102, 2011.

[KO98] J. Körner and A. Orlitsky. Zero-error infor-
mation theory. IEEE Trans. Inform. Theory,
44(6):2207, 1998.

[LM70] A.H. Lachlan and E.W. Madison. Com-
putable fields and arithmetically definable or-
dered fields.Proc. Amer. Math. Soc., 24:803–
807, 1970.

[Mad70] E. W. Madison. A note on computable real
fields.The Journal of Symbolic Logic, 35(2):pp.
239–241, 1970.

[Mar08] Murray Marshall. Positive polynomials and
sums of squares. AMS, 2008.

[MS05] Yuri Matiyasevich and Géraud Sénizergues.
Decision problems for semi-Thue systems with
a few rules.Theor. Comput. Sci., 330:145–169,
January 2005.

[MW09] Christian Mendl and Michael Wolf. Unital
quantum channels: convex structure and re-
vivals of Birkhoff’s theorem. Communica-
tions in Mathematical Physics, 289:1057–1086,
2009.

[NPA07] Miguel Navascués, Stefano Pironio, and Anto-
nio Acı́n. Bounding the set of quantum correla-
tions. Phys. Rev. Lett., 98:010401, Jan 2007.

10

http://arxiv.org/abs/0906.2527
http://arxiv.org/abs/1008.1168
http://arxiv.org/abs/0809.3972
http://arxiv.org/abs/quant-ph/0203003
http://arxiv.org/abs/1111.3965


[O.L09] O.Levin.Computability Theory, Reverse Math-
ematics, and Ordered Fields. PhD thesis, Uni-
versity of Connecticut, Storrs, CT, 2009.

[Pat70] M.S. Paterson. Unsolvability in3× 3 matrices.
Stud. Appl. Math., 49:105–107, 1970.

[PV10] Károly F. Pál and Tamás Vértesi. Max-
imal violation of a bipartite three-setting,
two-outcome Bell inequality using infinite-
dimensional quantum systems.Phys. Rev. A,
82:022116, Aug 2010.

[Rab69] Michael O. Rabin. Decidability of second-order
theories and automata on infinite trees.Trans-
actions of the American Mathematical Society,
141:pp. 1–35, 1969.

[Sei54] A. Seidenberg. A new decision method for
elementary algebra.Annals of Mathematics,
60:365–374, 1954.

[SST01] P. W. Shor, J. A. Smolin, and B. M. Terhal.
Nonadditivity of bipartite distillable entangle-
ment follows from conjecture on bound entan-
gled Werner states.Phys. Rev. Lett., 86:2681,
2001.

[SY08] Graeme Smith and Jon Yard. Quantum commu-
nication with zero-capacity channels.Science,
321:1812–1815, 2008.

[Tar51] A. Tarski. A decision method for elementary
algebra and geometry. University of California
Press, 1951.

[VW02] Karl Gerd H. Vollbrecht and Michael M. Wolf.
Activating distillation with an infinitesimal
amount of bound entanglement.Phys. Rev.
Lett., 88:247901, May 2002.

[Wat04] John Watrous. Many copies may be required
for entanglement distillation.Phys. Rev. Lett.,
93:010502, 2004.

[Wer89] R. F. Werner. Quantum states with Einstein-
Podolsky-Rosen correlations admitting a
hidden-variable model.Phys. Rev. A, 40:4277,
1989.

[WH08] A. J. Winter and P. Hayden. Counterexam-
ples to the maximal p-norm multiplicativity
conjecture for allp > 1. Commun. Math.
Phys., 284(1):263, 2008. (arXiv:0807.4753
[quant-ph]).

[WW01] R. F. Werner and M. M. Wolf. Bell inequalities
and entanglement.J. Quant. Inf. Comp., 1(3):1,
2001.

11

http://arxiv.org/abs/0807.4753

	1 Introduction
	2 Decidable problems
	2.1 A general tool from Tarski and Seidenberg
	2.2 Entanglement
	2.3 n-distillability
	2.4 Existence of an (n,m)-hidden variable model
	2.5 Existence of a d-dimensional quantum representation
	2.6 Birkhoff property
	2.7 n-shot zero-error capacity
	2.8 Additive minimal output entropy

	3 Undecided problems
	3.1 Distillability:
	3.2 LHV models:
	3.3 Quantum representation for correlations:
	3.4 Birkhoff property:
	3.5 Zero error-capacities:
	3.6 (Non-)additivity of other capacities:
	3.7 More problems

	4 Undecidable problems
	4.1 Tools for proving undecidability
	The halting problem
	Post's correspondence problem 
	Diophantine equations.



	4.2 Reachability of fidelity thresholds is undecidable

	5 Discussion