How to make unforgeable money in
generalised probabilistic theories
John H. Selby and Jamie Sikora
Perimeter Institute for Theoretical Physics, Waterloo, Ontario, Canada, N2L 2Y5
October 1, 2018
We discuss the possibility of creating money that is physically
impossible to counterfeit. Of course, “physically impossible” is de-
pendent on the theory that is a faithful description of nature. Cur-
rently there are several proposals for quantum money which have
their security based on the validity of quantum mechanics. In this
work, we examine Wiesner’s money scheme in the framework of
generalised probabilistic theories. This framework is broad enough
to allow for essentially any potential theory of nature, provided that
it admits an operational description. We prove that under a quan-
tifiable version of the no-cloning theorem, one can create physical
money which has an exponentially small chance of being counter-
feited. Our proof relies on cone programming, a natural generali-
sation of semidefinite programming. Moreover, we discuss some of
the difficulties that arise when considering non-quantum theories.
1 Introduction
Since the discovery of quantum physics, there has been an ongoing effort to un-
derstand the technological impact it may have. For example, it has been used
to develop new technologies through a better control and understanding of mi-
croscopic systems, and, moreover, we are still trying to understand all of the
information-theoretic advantages. That is, we strive to better understand how
the ‘weirdness’ of the theory can be exploited for practical purposes. There are
countless examples found in the studies of quantum computation, information
processing, and cryptography, and more are being discovered every day. In this
work, we focus on the important cryptographic task of creating money which
is physically unforgeable.
The money we use in our day to day lives only has value because it is dif-
ficult to counterfeit. If we could easily duplicate it in some way then it would
not take long before people were indeed taking advantage of this fact. Indeed,
despite the best government efforts, it was estimated that around 3% of certain
John H. Selby: jselby@perimeterinstitute.ca
Jamie Sikora: jsikora@perimeterinstitute.ca
Accepted in Quantum 2018-09-21, click title to verify 1
arXiv:1803.10279v2 [quant-ph] 28 Sep 2018
coins in the UK, for example, were counterfeits. As it stands it is a constant bat-
tle between those that design the coins and those that try to counterfeit them.
There are numerous protocols for creating quantum money, [1, 15, 25, 33]
to name a few. In fact, the very first cryptographic task using quantum infor-
mation was a money scheme in Wiesner’s seminal paper [33]. The key idea be-
hind Wiesner’s protocol, and those that followed, is that quantum theory could
promise security based on the impossibility of cloning an unknown quantum
state, and not on any technological limitations. In other words, security based
on the laws of physics rather than the limited resources of the counterfeiters.
This however is not the strongest form of security that one could imagine: it
is contingent on our current best guess regarding the underlying physics which
describes the world. A more reliable form of security would be independent
of a specific physical theory, and instead, be based on primitive physical prin-
ciples that we may expect to hold regardless of the ultimate theory of nature.
The framework of Generalised Probabilistic Theories (GPTs) provides an oper-
ational framework in which we can address such problems. For example the
possibility of key distribution [6] and impossibility of bit commitment [8, 31]
have been demonstrated for a wide range of physical theories.
In this paper we explore the possibility of unforgeable money in the GPT
framework. Not only does this offer the potential for a much stronger founda-
tion on which to base cryptographic security, but, it allows us to gain insight
into quantum protocols by highlighting the key features of quantum theory
necessary for security.
To prove our main result, we rely on the use of cone programming, also
called linear conic optimisation. Cone programming is a generalisation of semidef-
inite programming which is another class of optimisation problems which has
seen many uses in quantum theory. The generalisation of semidefinite pro-
gramming to cone programming mirrors that of quantum theory to GPTs. For
this reason, cone programming is a natural tool to have handy when studying
post-quantum theories. Although cone programming is a well-studied area of
optimisation theory, it has only had a small number of applications in quan-
tum theory [3, 16, 22, 26, 32] and in GPTs [2, 14, 19, 21, 31]. We hope this work
will inspire future applications of cone programming in the study of GPTs and
solidify it as an indispensable mathematical tool.
2 Unforgeable money: the idea
The idea behind the first quantum scheme for unforgeable money is quite sim-
ple: if a banknote contains unknown physical states, then the no-cloning theo-
rem proves that the money cannot be duplicated. However, even within quan-
tum theory there are some caveats. Due to the uncertainty principle, one cannot
ascertain the exact state of a quantum system. Thus, one could imagine a per-
fect copy is not needed to counterfeit money, only the ability to cheat someone
who might be testing if counterfeiting occurred (with a reasonable probability
of success).
Accepted in Quantum 2018-09-21, click title to verify 2
In Wiesner’s original scheme [33], the bank randomly selects one of the fol-
lowing four qubits |0i, |1i, |+i, |−i and embeds it into the banknote. When the
holder of the banknote wants to verify the banknote is authentic, they tell the
bank the serial number, then the bank looks up what the state should be, then
measures to see if the state is intact. Indeed, there is a less-than-perfect chance
of creating two banknotes which will each pass this verification. Intuitively,
the more qubits the bank puts into the banknote, the harder it is to counterfeit.
This intuition was later proven to be true in [25] through the use of semidefinite
programming.
In this paper, we wish to see if something like the above holds in GPTs.
Of course, one needs to define what the physical states are, and how the bank
verifies them. Without going into detail yet, we just assume the bank embeds
a physical state into the banknote, and independently verifies each copy indi-
vidually. The bank’s verification must be a physical process, and we desire it
to be secure against all physically-realisable counterfeiting machines. Roughly
speaking, let C represent the bank’s entire strategy of creating and verifying a
banknote, and let P be the set of all physical counterfeiting machines (not nec-
essarily perfect ones). Then we would like to design a money scheme such that
the following quantity is as small as possible:
sup{C(X) : X P} (1)
where C(X) denotes the probability that the two copies of the counterfeiter
each pass the bank’s verification procedure.
We shortly introduce the physics required to establish meaningful defini-
tions of C and P.
3 Background: Generalised probabilistic theories
We now introduce the mathematics of the framework for generalised proba-
bilistic theories that we use in this paper (those familiar with this topic can skim
this section for notation and proceed to Section 5). For simplicity we present the
mathematical bare bones of the framework, but note that this can be derived
from the basic operational ideas regarding the classical interface for a theory
[29, 30]. The framework we present here is closely related to many other ap-
proaches to generalised probabilistic theories (e.g., [5, 12, 17, 23, 24, 27, 28]),
but, in particular to the work of [8] and [18] which also take a diagrammatic
framework as a foundation.
The starting point for our framework is the notion of a process theory [10,
11, 29]. The key feature of a process theory is that it provides a diagrammatic
representation of the theory. There are two primitive components of a process
theory, physical systems, denoted by labeled wires, and physical processes which
can have input and output systems, denoted as a labeled box with input wires at
the bottom and output wires at the top. These processes can be ‘wired together
Accepted in Quantum 2018-09-21, click title to verify 3
to form diagrams, for example,
a
A
B
C
b
c
d
C
D
E
. (2)
Such diagrams are themselves valid processes in the theory; in this case with a
composite system AC as an input and BE as an output. Simply put, processes
are closed under being wired together. Processes with no inputs (such as c in
the above diagram) are called states, those with no outputs (such as b above)
are called effects, and those with neither are simply called numbers. Numbers
can be, for example, obtained when composing a state with an effect, and so,
as we are interested in probabilistic theories, these numbers are taken to be the
non-negative reals, R
+
.
Equality of processes can then be characterised in terms of these numbers,
the idea being that if two processes give the same probabilities in all situations
then the are the equal. This defines the notion of tomography, which formally
can be expressed as f, g : A B are equal if and only if
f
A
B
C
s
e
=
g
A
B
C
s
e
C, s, e. (3)
We consider process theories that come with a way to discard (or simply
ignore) systems. For this purpose we introduce a discarding effect for each
system A denoted as:
A
. (4)
Moreover we require that the composite of discarding effects is the discarding
effect for the composite system
AB
=
A B
. (5)
In particular, discarding “nothing”, i.e., the trivial system, is just the number 1.
These discarding effects then allow us to define a notion of causality for pro-
cesses [8, 9, 20]. Specifically, a process f is causal if and only if
B
f
A
=
A
. (6)
Accepted in Quantum 2018-09-21, click title to verify 4
The reason for naming these ‘causal’ is not immediately apparent, however it
can be shown that restricting to the causal processes of a theory ensures com-
patibility with the causal structure of relativity [20]. For example, this ensures
that there is no signalling back in time [8] or faster than the speed of light [9].
On the other hand, restricting to just the causal processes is a step too far.
Indeed, the only causal number is 1 and so such processes only describe deter-
ministic situations. We want to discuss probabilistic scenarios where the num-
bers correspond to the probability that some event occurs. To deal with this we
therefore also work with subcausal processes, that is, processes which can oc-
cur as some probabilistic ‘branch’ of a deterministic process. To formalise this
branching structure we introduce diagrammatic sums, i.e., a sum of processes
that distributes over diagrams:
P
i
f
i
=
ξ
f
i
P
i
ξ (7)
where ξ is shorthand notation for an arbitrary diagram of the form
ξ
:=
y
x
. (8)
An important consequence of this sum is that it allows us to define a partial
order for processes:
x
A
B
y
A
B
z
A
B
s.t.
=
B
yx
B
AAA
+
B
z
(9)
where z is another process in the theory. In particular, given this partial order
we can define the subcausal processes as those for which the following holds:
B
f
A
A
. (10)
Importantly, the set of subcausal processes is closed under composition and the
subcausal numbers are given by the interval [0, 1] so this faithfully captures the
probabilistic part of the process theory as we required.
In the definition of this ordering we have assumed that z is a physical pro-
cess. Later we consider the case when z is not a physical process, but belongs
to some set K, and denote such an ordering by
K
’. Note that such an or-
dering may not have any physical meaning, but it will have a mathematical
Accepted in Quantum 2018-09-21, click title to verify 5
meaning once we set up the mathematical structure behind the sets of different
processes. It is understood that the ‘absence of explicitly mentioning such a set’
means that K is the set of processes. For example, in Eq. (9), is shorthand
for K being the set of processes from A to B and in Eq. (10) it is shorthand for
K being the set of effects on B.
Given this structure one can observe that the set of processes {f
i
} with a
given (potentially composite) input A and (potentially composite) output B has
a rich linear structure. Specifically, using the sum defined in Eq. (7), we can
form (non-negative) linear combinations as
f
i
A
B
X
i
r
i
, for r
i
R
+
(11)
which is itself a valid process. These processes therefore form a convex cone,
denoted as K
B
A
, which naturally extends to a vector space V
B
A
which is spanned
by the cone. Note that this also holds for states and effects as they are just
special instances of processes, i.e., we obtain a cone of states K
A
(which have
no input) and a cone of effects K
A
(which have no output). The causal processes
form a convex set inside this cone, that is, if f and g are causal then it is simple
to check that
f
A
B
p
g
B
A
+(1 p) (12)
is causal as well for any p [0, 1]. This convex set can be characterised by
those processes in K
B
A
that satisfy Eq. (6). Importantly for our result, it can
then be shown that there are causal processes in the interior of the cone K
B
A
.
Additionally, we will make the assumption that the cones are closed (as in prac-
tice a theory should be operationally indistinguishable from its closure) and
finite-dimensional (as it is impossible in practice to do an infinite number of ex-
periments to characterise processes).
We illustrate these concepts with three specific examples of processes, be-
low.
States: In general this can be an arbitrary convex cone, the causal states are
given by the intersection of this cone with a single hyperplane and the sub-
causal states lie between this hyperplane and the zero vector (i.e. the point), as
Accepted in Quantum 2018-09-21, click title to verify 6
depicted below.
State cone
Hyperplane
Causal states
Subcausal states
(13)
Effects: We have only a single causal effect, the discarding effect itself. The
subcausal effects lie between the discarding effect and the zero vector.
Eect cone
Discarding eect
Subcausal eects
(14)
Transformations: The set of causal processes is a more complicated set, but
importantly, it is still an affine constraint, namely Eq. (6), on the transformation
cone. The subcausal transformations lie between this affine constraint and the
zero vector.
Transformation cone
Ane constraint
Subcausal transformations
Causal transformations
(15)
Accepted in Quantum 2018-09-21, click title to verify 7
4 Background: Cone programming
Cone programming is the study of optimization problems of the form
γ = sup
hC, Xi : b φ(X) K, X K
0
(16)
where K and K
0
are finite-dimensional convex cones, C and b are vectors, φ is
a linear function, and X is the variable over which we wish to optimize.
Before continuing, we must introduce the notion of a dual cone.
Definition 1. Given a convex cone K, we define its dual cone as
K
:= {v : hv, si 0, s K}. (17)
In this section, we study the cone program of the form below:
γ = sup {hC, Xi : b φ(X) K
1
, X K
2
} (18)
where K
1
and K
2
are closed convex cones. The first step in understanding a cone
program is to examine its dual cone program, which is another cone program
related to the original. In this case, the dual is given as
β = inf {hb, yi : φ
(y) C K
2
, y K
1
} (19)
where φ
is the adjoint of φ.
Suppose there exists an X satisfying
X int(K
2
) and b φ(X) int(K
1
) (20)
and a y satisfying
y int(K
1
) and φ
(y) C int(K
2
). (21)
Then we have γ = β and both problems attain an optimal solution. This is
known as strong duality, the proof of which is beyond the scope of this section.
We refer the interested reader to the book [7] for a proof.
All of the results relying on cone programming in this paper only use strong
duality. The dual yields a new perspective on studying a cone program while
strong duality proves that it is very useful, especially when we want a new way
to write the optimal value.
5 GPT Money: the scheme and measuring its security
We now describe the physical process of creating the banknote, its verification,
and what counterfeiting machines a counterfeiter can use.
Preparation: The bank selects a causal state s
i
of some system A from the en-
semble ε
A
= {(p
1
, s
1
), . . . , (p
n
, s
n
)} with p
1
, . . . , p
n
> 0 and
P
n
i=1
p
i
= 1. There-
fore, for all i we have
s
i
A
= 1 . (22)
Accepted in Quantum 2018-09-21, click title to verify 8
The bank puts the state into the banknote and records its serial number as well
as the state selected.
Verification (of a single copy): The bank uses the effect e
i
to verify the state s
i
where e
i
is subcausal and always accepts s
i
, i.e., for each i, we have
e
i
A
A
(23)
and
e
i
s
i
= 1 . (24)
This way the verification always passes when the state is untampered. Note
that one could consider more general bank strategies, but, as we are interested
in proving the impossibility of counterfeiting, allowing for more general strate-
gies could only make the counterfeiters job more difficult.
Definition 2 (Bank strategy). For the ensemble ε
A
= {(p
1
, s
1
), . . . , (p
n
, s
n
)}
and corresponding verification effects {e
1
, . . . , e
n
}, satisfying Eqs. (23) and (24),
we call the set
S
A
= {(p
1
, s
1
, e
1
), . . . , (p
n
, s
n
, e
n
)} (25)
a bank strategy. Note that this fully describes what the bank does to prepare and
verify a banknote.
Counterfeiting machines: We now flesh out the details of the set of physical
counterfeiting machines P. The counterfeiters strategy is simple to define, it
is a physical process which takes in the state of system A given by bank, and
outputs some state of system AA which is intended to be two copies of the
original
1
. Mathematically, it can be represented by some subcausal χ K
AA
A
,
i.e.,
χ
A
A A
A
. (26)
Thus, the set of physical counterfeiting machines is given as
P
A
=
χ
A
A A
A
,
χ
K
AA
A
. (27)
Security: Suppose the bank is independently given each output system and so
independently tests each of them with the relevant effect
2
. The overall bank
1
One could consider a more elaborate scenario in which the counterfeiter has access to n
banknotes and just aims to produce m > n at the end, we however leave this and other such
elaborations to future work.
2
One could also consider more elaborate bank strategies, but our work here is a proof of
principle and so we will leave these developments to future work.
Accepted in Quantum 2018-09-21, click title to verify 9
verification process is therefore given by the following diagram:
C
A
A A
:=
e
i
e
i
s
i
n
X
i=1
p
i
. (28)
With these definitions in hand, the quantity we use to measure the security of
the money scheme is given by
α
A
:= sup
C
χ
χ P
A
. (29)
In the rest of the paper, we study this quantity.
6 Designing secure GPT money schemes (and when it is not
possible)
We now study the optimization problem (29) with the hopes of finding bank
strategies S
A
which make α
A
as small as possible. We start with a very weak
condition which we call Weak No-Counterfeiting which roughly states that a
counterfeiter cannot cheat perfectly. This is of course not useful for crypto-
graphic purposes. Therefore, we later discuss how to start with this condition
and strengthen it by driving the maximum success probability of a counterfeiter
down to a negligible amount. We therefore prove that all GPTs fall into one of
two categories: there is either perfect counterfeiting (this is the case for classical
theory) or practical security (this is the case for quantum theory). Interestingly,
there is no middle ground.
6.1 Perfect counterfeiting
In order to understand what we need to achieve security we first consider the
converse problem: what does it mean for perfect counterfeiting to be possible?
This seems closely related to the clonability or broadcastability of the ensemble
ε
A
= {(p
1
, s
1
), . . . , (p
n
, s
n
)}. Specifically, if one could perfectly clone the states
then this would immediately provide a perfect counterfeiting strategy. That is,
given a channel such that, for all s
i
:
s
i
=
s
i
s
i
(30)
Accepted in Quantum 2018-09-21, click title to verify 10
then if the counterfeiter used this channel we would find that
C
=
e
i
e
i
s
i
X
i
p
i
=
e
i
e
i
s
i
X
i
p
i
s
i
= 1 . (31)
This implies α
A
= 1 and so counterfeiting can be achieved perfectly. This is
exactly what happens in the case of classical theory. Moreover, it was shown in
[4] that the possibility of cloning arbitrary ensembles singles out classical theory
from a wide class of GPTs
3
.
However, there are other ways in which one could find that perfect counter-
feiting is possible. One way is if the bank strategy is too restricted. For example,
if we take
e
i
A
=
A
, (32)
for all i, then the bank is learning nothing about the returned banknotes. Obvi-
ously, the counterfeiter would always pass the verification irrespective of what
counterfeiting procedure they used.
Therefore, the task of finding a secure money scheme for the bank does not
only require a non-cloneable ensemble ε
A
= {(p
1
, s
1
), . . . , (p
n
, s
n
)}, but also a
decent choice of each verification effect e
i
. To this end, we now consider differ-
ent security notions for the entire bank strategy S
A
= {(p
1
, s
1
, e
1
), . . . , (p
n
, s
n
, e
n
)}.
6.2 Weak security
We start with a definition.
Definition 3 (Weak No-Counterfeiting (WNC)). A theory satisfies WNC if
there exists a bank strategy S
A
= {(p
1
, s
1
, e
1
), . . . , (p
n
, s
n
, e
n
)} such that α
A
< 1.
This is mathematically the weakest condition that can be used to rule out
perfect counterfeiting. However, it is not the most physically motivated as-
sumption. We therefore address how it can be derived from an assumption
regarding the bank strategy.
Definition 4 (Verification Sharpness (VS)). The bank strategy
S
A
= {(p
1
, s
1
, e
1
), . . . , (p
n
, s
n
, e
n
)}
satisfies VS if and only if the effects uniquely pick out the states in the ensemble.
I.e., for all i, we have:
e
i
s
= 1
s
=
s
i
. (33)
where s is an arbitrary subcausal state.
3
Namely, those satisfying the No-Restriction Hypothesis [8] and Tomographic Locality [17].
Accepted in Quantum 2018-09-21, click title to verify 11
Verification Sharpness is defined to rule out the case discussed in the previ-
ous subsection where the bank’s measurements were too restricted, e.g., each e
i
is just the discarding effect. The effects in the Verification Sharpness condition
are idealised in the sense that any deviation from the honest state will be caught
by the bank with non-zero probability. In quantum theory, if the states are pure,
then the effect can be chosen to be the rank-1 projection onto that state. Thus,
in quantum theory, VS holds when the states in the ensemble are pure.
Definition 5 (Broadcasting Map). A broadcasting map, B, for a set of states
{s
i
} is any subcausal map satisfying:
s
i
B
=
s
i
B
=
s
i
, i . (34)
We now show that under the VS condition, a violation of WNC is equiva-
lent to being able to broadcast the ensemble.
Lemma 1. Suppose a bank strategy S
A
= {(p
1
, s
1
, e
1
), . . . , (p
n
, s
n
, e
n
)} satisfies
VS. Then perfect counterfeiting is equivalent to the broadcastability of the states
{s
1
, . . . , s
n
}.
We postpone a proof to Appendix A since it follows easily from (indepen-
dent) analysis later in the paper.
In [4] it was shown that broadcastability (or the special case of clonabil-
ity) of an ensemble implies it must be classical (at least in their framework
which assumes the No-Restriction Hypothesis [8] and Tomographic Locality
[17]). Hence, we obtain the following corollary by restricting our consideration
to the class of GPTs that they consider.
Corollary 1. In any non-classical GPT satisfying the No-Restriction Hypothesis
[8] and Tomographic Locality [17], VS implies that the strategy must satisfy
WNC.
Clearly, the WNC condition is not good enough on its own to have secure
money as the counterfeiter could still cheat with very large probability. In the
next subsection, we introduce a variant which is more meaningful for cryp-
tographic security. For this purpose, we prove that bank strategies satisfying
WNC can be modified such that the states span the vector space V
A
.
Definition 6. A bank strategy S
A
= {(p
1
, s
1
, e
1
), . . . , (p
n
, s
n
, e
n
)} is said to be
spanning if {s
1
, . . . , s
n
} span the vector space V
A
.
We have the following lemma.
Lemma 2. If WNC holds, then there is a spanning bank strategy S
A
such that
α
A
< 1.
Accepted in Quantum 2018-09-21, click title to verify 12
Proof. Suppose we have a bank strategy S
0
A
with security parameter α
0
A
< 1
(which exists since WNC holds. Then given a basis of causal states
4
{b
j
}
m
j=1
of V
A
, we can construct the bank strategy S
00
A
= {(1/m, b
j
, )}. The security
parameter for the strategy S
00
A
is denoted α
00
A
(which clearly equals 1). Let S
A
be
the bank strategy which uses S
0
A
or S
00
A
chosen uniformly at random. As S
00
A
is a
spanning bank strategy, we see that S
A
is as well. The proof now follows since
α
A
1
2
α
0
A
+ α
00
A
< 1 (35)
as α
0
A
< 1 and α
00
A
= 1.
Thus, for the rest of the paper, we may restrict our attention to spanning
bank strategies when requiring WNC to hold.
6.3 Practical security
We start by defining a condition which allows for a practical level of security.
Definition 7 (Strong No-Counterfeiting (SNC)). A theory satisfies SNC if for
any δ > 0 there exists a bank strategy S
A
such that α
A
δ.
Assuming SNC, the bank can therefore choose a value for δ with which it
is comfortable, then proceed to use the appropriate ensemble in the banknote
and the corresponding effects in its verification. Note also that there is no hope
of doing better than this, i.e., we cannot take δ = 0 as there is always some
probability that the counterfeiter could make a lucky guess and prepare a new
note in exactly the right state. In particular, if p
i
= max{p
1
, . . . , p
n
}, then the
counterfeiter can always use the counterfeiting machine
s
i
s
i
(36)
which succeeds with probability at least p
i
> 0. (Even if a counterfeiter did not
know the bank’s strategy, they could use the strategy (36) but instead of s
i
, use
a state in the interior of the cone to show that α
A
> 0.)
In this subsection we assume that the theory satisfies WNC (i.e., there is
a bank strategy in the theory which satisfies WNC) and ask if this can be ex-
tended to a proof of SNC. Specifically we consider boosting the security by
having multiple independent copies of a bank strategy on each banknote. For
example, let S
A
and S
B
be two bank strategies. We now study the case if the
bank were to use both S
A
and S
B
by sampling a state from one, then the other
independently, and including both sampled states on the banknote. Let S
AB
be
the new (product) bank strategy and let α
AB
be the optimal probability that a
counterfeiter can successfully cheat S
AB
. It seems like it should be true that
α
AB
= α
A
α
B
. Indeed this is the case for quantum theory [25]. However,
4
Which exists since the vector space is spanned by the set of causal states.
Accepted in Quantum 2018-09-21, click title to verify 13
there are examples, even in classical theory, where similar tasks do not have
such a product theorem (one example can be found in the study of nonlocal
games [13]). Therefore, such a result is not so forthcoming.
Indeed, the fact that α
AB
may not equal α
A
α
B
is a big difference between
the setting of GPTs and quantum theory. We could impose certain physical
principles (each of which hold in quantum theory) in order to enforce α
AB
=
α
A
α
B
, but we will show how to circumvent this problem entirely without the
need to assume these extra physical principles.
Let us consider a counterfeiting strategy χ
AB
K
AABB
AB
as illustrated dia-
grammatically, below
χ
AB
C
A
C
B
A A
A
B B
B
. (37)
Clearly it is possible to achieve
5
success probability α
A
α
B
by the counter-
feiter by simply doing his optimal procedure on A and B independently:
χ
op
A
C
A
C
B
χ
op
B
. (38)
Ideally we would like to show that they cannot do any better than this, but
as mentioned above, this may not always be the case.
We now show that although α
AB
might be greater than α
A
α
B
, it cannot be
too much greater. To this end, we relax α
A
to a new quantity
e
α
A
> 0 (defined
in the next subsection) which satisfies the following two properties:
α
A
< 1 =
e
α
A
< 1 for all spanning bank strategies S
A
; (39)
α
A
n
(
e
α
A
)
n
for all (not necessarily spanning) bank strategies S
A
. (40)
We see that (39) together with Lemma 2 says that if WNC holds for any bank
strategy, then this new quantity is bounded away from 1 for some spanning
bank strategy. Combining this with (40), we have that the success probability
of cheating the bank decreases exponentially using the n-fold repetition of this
spanning bank strategy. This is summarised in the following lemma.
Lemma 3. If there exists a quantity
e
α > 0 satisfying Eqs. (39) and (40), then
WNC implies SNC.
In the following subsection we define a relaxation from α to
e
α and demon-
strate that it satisfies Eqs. (39) and (40). Thus the weakest form of security
possible implies the promise of practical security.
5
We did not prove attainment of an optimal solution in this work, but the same argument
holds if one takes limits.
Accepted in Quantum 2018-09-21, click title to verify 14
6.3.1 A helpful, possibly non-physical, quantity
e
α
Recall the definition of a dual cone (Definition 1). The dual cones K
B
A
do not
have an immediate interpretation within the GPT. However, it is clear that a
diagram of the form
A
B
C
s
e
(41)
must be within K
B
A
as it necessarily must evaluate to a non-negative real num-
ber on any f K
B
A
. In particular, this implies that K
A
K
A
and K
A
K
A
,
that is, the state cone lives inside the dual of the effect cone, and vice versa.
To define
e
α, we relax the set of physical counterfeiting machines P to
e
P,
where
e
P is a set of “counterfeiting machines” which are possibly not physi-
cally realizable. However, whilst a counterfeiter may not be able to physically
perform ˜χ
e
P, it is nonetheless useful to consider.
Recall we have P defined as
P
A
=
χ
K
A
,
χ
K
AA
A
(42)
where we have now explicitly denoted that the set defining the ordering is the
effect cone for A. This is the cone that we will extend for the relaxation. Specifi-
cally, we replace K
A
with K
A
which, as mentioned above, contains K
A
. There-
fore, we define the relaxation
e
P
A
=
χ
K
A
,
χ
K
AA
A
(43)
which may contain non-physical counterfeiting machines. They must still, by
assumption, be in the process cone. But, there is no guarantee that they are
causal or even subcausal, therefore they could lead to obtaining ‘probabilities’
greater than 1.
This is clearly a relaxation as for any GPT, we have K
A
K
A
. However,
certain GPTs satisfy a property known as the No-Restriction Hypothesis [8], which
states that K
A
= K
A
. For such theories we have
e
P
A
= P
A
and so the relaxation
is trivial. In particular this is the case for quantum theory. Therefore, the proof
of our main result greatly simplifies in the case of quantum theory and any
other theory satisfying the No-Restriction Hypothesis.
Define the quantity
e
α to be
e
α
A
= sup
C
˜χ
˜χ
e
P
A
(44)
Accepted in Quantum 2018-09-21, click title to verify 15
which is defined to be optimizing the same quantity as α, i.e., the same C pro-
cess. Also, we have 0 < α
e
α since P
e
P. Here, we use tildes to denote
something that may not be physical to make the distinction clear.
Below is the main technical result of this paper. The proof of this theorem re-
lies crucially on the duality theory of cone programming. The interested reader
is referred to the book [7].
Theorem 1. For all bank strategies S
A
, we have
e
α
A
= min
y
y
C
K
AA
A
, y K
A
. (45)
Moreover, (44) and (45) attain an optimal solution (hence the use of “min
instead of “inf above). For notational simplicity, we will denote
y
=:
˜
Y
. (46)
We call the original formulation (44) the primal, and the above formulation (45)
the dual.
Before showing a proof, we need the lemma below (whose proof can be
found in Appendix B).
Lemma 4. For y int(K
A
), we have
y
int(K
AA
A
).
We now prove Theorem 1.
Proof. We begin by transforming the optimization problem (44) into a statement
about vectors in the finite-dimensional vector space V
AA
A
. We make the vector-
diagram associations
˜χ
X,
C
C, φ and b (47)
such that
hC, Xi =
C
˜χ
, b φ(X) =
˜χ
and φ
(y) =
y
.
(48)
Accepted in Quantum 2018-09-21, click title to verify 16
Note these exist by the Riesz-Fr´echet Representation Theorem. Thus, (44) can
be written in vector form as in (18) and its dual (45) as in (19) when K
1
= K
A
and K
2
= K
AA
A
.
We now show that strong duality holds. As discussed in the paragraph
following (11), there are subcausal processes in the interior of the cone. That is,
there exists χ int(K
AA
A
) satisfying
χ
. (49)
Since int(K
A
), we know that
λ
ν
int(K
A
)
for any ν V
A
and sufficiently small λ > 0. Thus, there exists a λ > 0 such that
λχ int(K
AA
A
) and
λ
χ
int(K
A
) int(K
A
). (50)
Here, we can think of λ as a scaling factor to pull the processes into the interior
of the necessary cones.
On the other hand, By Lemma 4, we can take y int(K
A
) to get that
y
int(K
AA
A
).
We can repeat the argument above to scale C down (say, by µ > 0) to get that
y
µ
C
int(K
AA
A
). (51)
Define λ
0
= 1 to get
λ
0
y
int(K
A
) and λ
0
y
C
int(K
AA
A
). (52)
This proves that strong duality holds (recall the definition from Section 4)
implying that the primal and dual have the same optimal value and both prob-
lems attain an optimal solution.
Accepted in Quantum 2018-09-21, click title to verify 17
Remark 1. From the proof above, we see that the value α (recall (29)) is attained
as well. This is because the above proof easily generalizes to the case where we
replace K
A
with K
A
(even the interior points are the same).
We now prove
e
α satisfies the properties required for Lemma 3.
Lemma 5. For all spanning bank strategies S
A
, we have
e
α
A
= 1 implies that
α
A
= 1, i.e. (39) is satisfied.
Proof. Notice we have
C
˜χ
X
i
p
i
˜χ
s
i
X
i
p
i
= 1 (53)
for all ˜χ
e
P. Thus we have
e
α
A
1. Let ˜χ
e
P be an optimal solution to (44)
and suppose
e
α
A
= 1. We see from (53) that
˜χ
s
i
= 1 , (54)
for all i. As the states s
i
are assumed to span V
A
this implies for all states s
(and indeed for any vector s) that
˜χ
s
=
s
and hence, via tomography (3), that
˜χ
= .
In other words ˜χ is causal and thus must be in P as well. Since there exists
χ P such that
C
χ
= 1 , (55)
we have α
A
= 1 as desired.
We now consider the dual problem. Consider an optimal solution to the dual
problem y K
A
, such that
e
α =
y
. (56)
Accepted in Quantum 2018-09-21, click title to verify 18
Notice that Y :=
1
e
α
˜
Y , given diagrammatically as
1
e
α
y
(57)
is a physical, causal, operation as
1
e
α
y
=
1
y
y
(58)
is a physical, i.e. normalised, state.
Remark 2. The entire point of relaxing α to
e
α was so that y is in K
A
, thus
implying that Y is a physical, or causal, operation. We soon show that this is
the keystone to our proof of SNC holding.
Note that the constraint
e
α
Y
C
=
˜
Y
C
K
AA
A
(59)
implies that
e
α
Y
ξ
C
ξ , ξ K
AA
A
. (60)
Now let us consider appending a new system B and a new counterfeiting
machine which maps AB to the space AABB. Diagrammatically, it would look
like this
χ
A A
A
B B
B
. (61)
Note that for any χ
AB
P
AB
, we have that
χ
AB
A A
A
B B
B
D
(62)
is in P
A
for any physical map D. This is because it is physically possible for
a counterfeiter to do this, and thus must be captured by the set of physical
processes P. We use two different choices for D, the bank’s strategy C, and the
alternative strategy Y , above.
With these ideas in hand, we can prove the following lemma.
Accepted in Quantum 2018-09-21, click title to verify 19
Lemma 6. α
A
1
···A
m
Π
m
i=1
e
α
A
i
, for all bank strategies S
A
1
, . . . , S
A
m
. In par-
ticular, (40) is satisfied.
Proof. We prove the m = 2 case for clarity, but the general case follows by
repeating the same argument. We consider a pair of bank strategies, S
A
and S
B
and show that α
AB
e
α
A
e
α
B
. Consider
α
AB
=
χ
AB
C
A
C
B
(63)
where χ
AB
P is an optimal solution to (29) (which exists by Remark 1). By
a trivial diagrammatic rewrite, this is equivalent to
α
AB
=
χ
AB
C
A
C
B
. (64)
As discussed previously, we have the dotted part in the diagram above is in K
AA
A
.
Therefore, from (60), we have
α
AB
e
α
A
χ
AB
Y
A
C
B
. (65)
By another diagrammatic rewrite, we have
α
AB
e
α
A
χ
AB
Y
A
C
B
. (66)
By repeating the same argument noting the dotted part above is physical, we
have
α
AB
e
α
A
e
α
B
χ
AB
Y
A
Y
B
. (67)
From the definition of Y , it is clear that
χ
AB
Y
A
Y
B
=
1
e
α
A
e
α
B
χ
AB
y
A
y
B
1
e
α
A
e
α
B
y
A
y
B
= 1 , (68)
since χ
AB
is subcausal. This finishes the proof.
Accepted in Quantum 2018-09-21, click title to verify 20
The intuition behind this proof is that a counterfeiter could implement the
Y
B
or C
B
strategy him/herself, and this should not allow him/her to pass the
verification on A with higher probability. Also, a counterfeiter trying to cheat
the Y strategies is pointless since the Y strategy simply discards the output of
any counterfeiting machine.
One thing to note in the proof of Lemma 6 is that we used χ P and not a
˜χ
e
P. This is because the combination of χ and a physical map D must be in
the cone K
AA
A
(see (62)). One can show that this is the case for any ˜χ
e
P, as
˜χ can be rescaled to belong to P, hence we can repeat the proof to show that
e
α is multiplicative over the theory. This is a stronger claim than the one in the
lemma but is not necessary for our main result.
By combining Lemmas 3, 5, and 6, we have the following theorem.
Theorem 2. If WNC holds, then SNC holds. In other words, WNC is nec-
essary and sufficient to make unforgeable money.
By combining this with Corollary 1 we have the following corollary.
Corollary 2. In any non-classical GPT satisfying the No-Restriction Hypothesis
[8] and Tomographic Locality [17], VS is sufficient to make unforgeable money.
7 Conclusion
In this paper we have considered Wiesner’s quantum money scheme in the gener-
alised probabilistic theory framework. We first defined the class of GPTs in which
there is potential for unforgeable money, that is, those satisfying the WNC as-
sumption. We then demonstrate that under an assumption of Verification Sharp-
ness, this is equivalent to the inability to broadcast arbitrary causal states a
general feature of non-classical GPTs, for example, those in [4].
To obtain meaningful security however, we require that the probability of
successfully counterfeiting can be made arbitrarily close to zero, that is, the as-
sumption of SNC. Demonstrating that this is indeed possible for arbitrary GPTs
satisfying WNC is the main result of this paper. That is, we have a dichotomy:
for any theory, either practical security is possible or perfect counterfeiting is
possible.
It would be interesting to see if this work could be extended in a way similar to
the quantum schemes that have been developed in recent years. For example, is it
possible to have a purely classical verification scheme in the GPT setting? Would
it be possible to have a store merchant be able to verify the money without the
need of involving the bank? Both of these are possible in the quantum setting,
see [15] and [1], respectively. These scenarios are interesting, but add to the
complexity of the problem considerably. As this work shows that GPT money
is indeed physically possible in many theories, it paves the way to look at these
more elaborate scenarios which are more convenient for the bank.
Accepted in Quantum 2018-09-21, click title to verify 21
Acknowledgments
This research was supported in part by Perimeter Institute for Theoretical
Physics. Research at Perimeter Institute is supported by the Government of
Canada through the Department of Innovation, Science and Economic Develop-
ment Canada and by the Province of Ontario through the Ministry of Research,
Innovation and Science.
References
[1] Scott Aaronson and Paul Christiano. Quantum money from hidden sub-
spaces. In Proceedings of the forty-fourth annual ACM symposium on The-
ory of computing, pages 41–60. ACM, 2012. DOI: 10.1145/2213977.2213983.
[2] Joonwoo Bae, Dai-Gyoung Kim, and Leong-Chuan Kwek. Structure of
optimal state discrimination in generalized probabilistic theories. Entropy,
18(2):39, 2016. DOI: 10.3390/e18020039.
[3] Somshubhro Bandyopadhyay, Alessandro Cosentino, Nathaniel Johnston,
Vincent Russo, John Watrous, and Nengkun Yu. Limitations on separable
measurements by convex optimization. IEEE Transactions on Information
Theory, 61(6):3593–3604, 2015. DOI: 10.1109/TIT.2015.2417755.
[4] Howard Barnum, Jonathan Barrett, Matthew Leifer, and Alexander Wilce.
Generalized no-broadcasting theorem. Physical review letters, 99(24):
240501, 2007. DOI: 10.1103/PhysRevLett.99.240501.
[5] Jonathan Barrett. Information processing in generalized probabilistic
theories. Physical Review A, 75(3):032304, 2007. DOI: 10.1103/Phys-
RevA.75.032304.
[6] Jonathan Barrett, Lucien Hardy, and Adrian Kent. No signaling and quan-
tum key distribution. Physical review letters, 95(1):010503, 2005. DOI:
10.1007/s11128-014-0880-1.
[7] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge
University Press, 2004.
[8] Giulio Chiribella, Giacomo Mauro D’Ariano, and Paolo Perinotti. Proba-
bilistic theories with purification. Physical Review A, 81(6):062348, 2010.
DOI: 10.1103/PhysRevA.81.062348.
[9] Bob Coecke. Terminality implies non-signalling. arXiv preprint
arXiv:1405.3681, 2014.
[10] Bob Coecke and Aleks Kissinger. Categorical quantum mechanics I: Causal
quantum processes. arXiv preprint arXiv:1510.05468, 2015.
[11] Bob Coecke and Aleks Kissinger. Picturing quantum processes. Cambridge
University Press, 2017.
[12] E Brian Davies and John T Lewis. An operational approach to quantum
probability. Communications in Mathematical Physics, 17(3):239–260, 1970.
DOI: 10.1007/BF01647093.
[13] Uriel Feige and aszl´o Loasz. Two-prover one-round proof systems: Their
power and their problems. In Proceedings of the twenty-fourth annual ACM
Accepted in Quantum 2018-09-21, click title to verify 22
symposium on Theory of computing, pages 733–744. ACM, 1992. DOI:
10.1145/129712.129783.
[14] Samuel Fiorini, Serge Massar, Manas K Patra, and Hans Raj Tiwary. Gen-
eralized probabilistic theories and conic extensions of polytopes. Journal
of Physics A: Mathematical and Theoretical, 48(2):025302, 2014. DOI:
10.1088/1751-8113/48/2/025302.
[15] Dmitry Gavinsky. Quantum money with classical verification. In Compu-
tational Complexity (CCC), 2012 IEEE 27th Annual Conference on, pages
42–52. IEEE, 2012. DOI: 10.1063/1.4903116.
[16] Sevag Gharibian, Jamie Sikora, and Sarvagya Upadhyay. QMA variants
with polynomially many provers. Quantum Information & Computation,
13(1&2):0135–0157, 2013.
[17] Lucien Hardy. Quantum theory from five reasonable axioms. arXiv preprint
arXiv:0101012, 2001.
[18] Lucien Hardy. Reformulating and reconstructing quantum theory. arXiv
preprint arXiv:1104.2066, 2011.
[19] Anna Jenˇcoa and Martin Pl´avala. Conditions on the existence of maximally
incompatible two-outcome measurements in general probabilistic theory.
Physical Review A, 96:022113, 2017. DOI: 10.1103/PhysRevA.96.022113.
[20] Aleks Kissinger, Matty Hoban, and Bob Coecke. Equivalence of relativistic
causal structure and process terminality. arXiv preprint arXiv:1708.04118,
2017.
[21] Ludovico Lami, Carlos Palazuelos, and Andreas Winter. Ultimate data hid-
ing in quantum mechanics and beyond. Communications in Mathematical
Physics, pages 1–48, 2017. DOI: 10.1007/s00220-018-3154-4.
[22] Monique Laurent and Teresa Piovesan. Conic approach to quantum
graph parameters using linear optimization over the completely posi-
tive semidefinite cone. Siam J. Optim., 25(4):2461–2493, 2015. DOI:
10.1137/14097865X.
[23] G. Ludwig. An Axiomatic Basis of Quantum Mechanics. 1. Derivation of
Hilbert Space. Springer-Verlag, 1985.
[24] G. W. Mackey. The mathematical foundations of quantum mechanics. W.
A. Benjamin, New York, 1963.
[25] Abel Molina, Thomas Vidick, and John Watrous. Optimal counterfeiting
attacks and generalizations for Wiesner’s quantum money. In Proceedings of
the 7th Conference on Theory of Quantum Computation, Communication,
and Cryptography, volume 7582 of Lecture Notes in Computer Science, pages
45–64, 2013. DOI: 10.1007/978-3-642-35656-8˙4.
[26] Ashwin Nayak, Jamie Sikora, and Levent Tun¸cel. A search for quantum
coin-flipping protocols using optimization techniques. Mathematical Pro-
gramming, 156(1-2):581–613, 2016. DOI: 10.1007/s10107-015-0909-y.
[27] C. Piron. Axiomatique quantique. Helvetia Physica Acta, 37:439–468, 1964.
[28] CH Randall and DJ Foulis. An approach to empirical logic. The American
Mathematical Monthly, 77(4):363–374, 1970. DOI: 10.2307/2316143.
[29] John H Selby. A process theoretic triptych. PhD thesis, Imperial College
London, 2017.
Accepted in Quantum 2018-09-21, click title to verify 23
[30] John H Selby, Carlo Maria Scandolo, and Bob Coecke. Reconstruct-
ing quantum theory from diagrammatic postulates. arXiv preprint
arXiv:1802.00367, 2018.
[31] Jamie Sikora and John H Selby. A simple proof of the impossibility of bit-
commitment in generalised probabilistic theories using cone programming.
Physical Review A, 97:042302, 2018. DOI: 10.1103/PhysRevA.97.042302.
[32] Jamie Sikora and Antonios Varvitsiotis. Linear conic formulations for two-
party correlations and values of nonlocal games. Mathematical Program-
ming, 162(1-2):431–463, 2017. DOI: 10.1007/s10107-016-1049-8.
[33] Stephen Wiesner. Conjugate coding. SIGACT News, 15(1):78–88, 1983.
DOI: 10.1145/1008908.1008920.
A Proof of Lemma 1
Proof. First let us assume perfect counterfeiting, i.e., α
A
= 1. Since the value
of α
A
is attained (see Remark 1), we know that there exists a subcausal χ such
that
e
i
e
i
s
i
χ
= 1 , (69)
for all i. VS therefore implies that for all i, we have
e
i
s
i
χ
=
s
i
e
i
χ
=
s
i
. (70)
As each s
i
is causal, this implies that for all i,
e
i
s
i
χ
=
e
i
χ
=
s
i
1
. (71)
Using VS again, we have
s
i
χ
=
s
i
χ
=
s
i
(72)
for all i, which is precisely what it means for χ to be able to broadcast all of the
states s
i
.
Accepted in Quantum 2018-09-21, click title to verify 24
For the other direction, let us assume there is a channel B which broadcasts
the states s
i
:
s
i
B
=
s
i
B
=
s
i
. (73)
Therefore we have, for all i:
e
i
s
i
B
=
e
i
B
=
s
i
1
. (74)
As we know e
i
are subcausal, we can decompose the discarding map as e
i
+ E
i
where each E
i
is a subcausal effect. This gives, for all i:
e
i
s
i
B
= =
1
+
e
i
E
i
e
i
B
s
i
+
B B
e
i
E
i
e
i
s
i
s
i
e
i
. (75)
We use the subcausality of B (and the causality of each s
i
) to write
s
i
B
=
1
+
BB
e
i
E
i
e
i
s
i
s
i
e
i
B
e
i
+
s
i
E
i
B
E
i
+
s
i
E
i
(76)
using the same decomposition of the discarding map as above. Combining
Eqs. (75) and (76), we have
=
B
e
i
E
i
s
i
B
e
i
=
s
i
E
i
B
E
i
=
s
i
E
i
0
(77)
and
e
i
e
i
s
i
B
= 1 (78)
for all i, since each number is nonnegative. This implies that perfect counter-
feiting is possible.
B Proof of Lemma 4
The following well-known fact (see, e.g., [7]) characterises the interior of the dual
cone.
Accepted in Quantum 2018-09-21, click title to verify 25
Fact 1. For a closed convex cone K, we have
int(K
) = {y : hy, xi > 0, for all x K \ {0}}. (79)
We are now ready to prove Lemma 4.
Proof. We want to show that, for χ K
AA
A
,
y
χ
= 0 =
χ
= 0. (80)
To do so, however, recall the notion of tomography which is how equality is
defined for processes in GPTs. We have two processes f, g : A B are equal if
and only if
f
A
B
C
s
e
=
g
A
B
C
s
e
C, s K
AC
, e K
BC
. (81)
Therefore we need to check that
χ
C
e
s
= 0 C, s K
AC
, e K
AAC
. (82)
To see this first note that as y is interior, any other state, a K
A
belongs to
some convex decomposition of y. Therefore we have
y
χ
= 0 =
a
χ
= 0 a K
A
. (83)
In particular, we can take a to be the ‘marginal’ of some bipartite state, s, i.e.
χ
s
C
= 0. (84)
This holds for any state s and any system C so we can rewrite this as
χ
s
C
= 0 C, s K
AC
. (85)
Accepted in Quantum 2018-09-21, click title to verify 26
Note that the composite of the three discarding effects is the discarding effect
for the composite system. This discarding effect is in the interior of K
AAC
, so
any effect e K
AAC
can appear in some convex decomposition of the discarding
effect. Therefore we have
χ
C
e
s
= 0 C, s K
AC
, e K
AAC
. (86)
This concludes our proof as this is exactly the condition needed for tomography
to show that χ = 0.
Accepted in Quantum 2018-09-21, click title to verify 27