A Quantum Approach to the Unique Sink Orientation Problem
Dave Bacon
Google, Seattle, WA 98103 USA∗

arXiv:1605.03266v2 [quant-ph] 26 May 2017

We consider quantum algorithms for the unique sink orientation problem on cubes. This problem
is widely considered to be of intermediate computational complexity. This is because there no
known polynomial algorithm (classical or quantum) from the problem and yet it arrises as part of
a series of problems for which it being intractable would imply complexity theoretic collapses. We
give a reduction which proves that if one can efficiently evaluate the kth power of the unique sink
orientation outmap, then there exists a polynomial time quantum algorithm for the unique sink
orientation problem on cubes.

In this paper we are concerned with finding an efficient
quantum algorithm for a problem that admits no known
classical polynomial time algorithm despite considerable
effort, the unique sink orientation problem on cubes. In
this problem one is given a directed graph on a hypercube such that every face (subcube) of the hypercube
admits a unique sink vertex, and the goal is to find the
global unique sink of the entire cube. Access to information about an instance of this problem is via an oracle
which takes as inputs one of the vertices of the cube and
outputs a list of the directions of the outgoing edges of
that vertex. The best (classical) algorithm for this problem queries the oracle O((1.467 . . .)n ) times where n is
the dimension of the hypercube [1], or, if the directed
graph has no cycles O(exp(n1/2 )) times [2, 3]. We are not
able to obtain a polynomial time quantum algorithm for
this problem, but we are able to show that if one could
efficiently calculate the kth power of the oracle in this
problem (defined below), then there exists an efficient
quantum algorithm. Our path to this is through period
finding, the key ingredient to Shor’s efficient quantum algorithm for factoring [4, 5]. The main difference in our
failure versus Shor’s success is that in Shor’s algorithm
there are efficient algorithms to calculate the kth power
of a number mod N for k exponentially large (modular
exponentiation), whereas for the unique sink orientation
problem on cubes we do not yet have such a procedure.
Our reduction opens a new approach towards obtaining
an efficient quantum algorithm for the unique sink orientation problem on cubes.
I.

BACKGROUND AND MOTIVATION

The unique sink orientation problem on cubes (hereafter abbreviated as the USO problem) arises as a fundamental problem in a variety of optimization problems.
The original application of USO problem comes from
the observation that a polynomial time algorithm for the
USO problem would yield a polynomial time algorithm
for a class of linear complementarity problems that have
no known polynomial time algorithm (those arising from

∗

dabacon@google.com

P-matrices) [6]. Another application is to linear programming. Recall that a numerical problem is strongly
polynomial if assuming unit cost for arithmetic on the
involved numerical quantities, the algorithm takes takes
a polynomial amount of time in the number of numerical constants. While there are weakly polynomial time
algorithms for linear programming [7], there is no known
strongly polynomial time algorithm. A polynomial time
algorithm for the USO problem, however, would imply a
strongly polynomial time algorithm for linear programming [8]. A variety of problems in the theory of games
would also admit polynomial time solution [9–11] if there
is a polynomial time algorithm algorithm for the USO
problem. Finally, finding the smallest ball enclosing a
set of ball would also admit a polynomial time solution
if there was a polynomial time algorithm for the USO
problem [12].
The USO problem is a promise problem: we are
promised that the faces of the hypercube graph all have a
unique sink. This promise is itself not known to be polynomial time verifiable [13]. Therefore (a decision) version
of this problem does not fit nicely into a discussion of
computational complexity. However there is strong evidence that the problems which motivate investing USO
are not computationally intractable. For example, the Pmatrix linear complementarity problem is not NP-hard
unless NP=coNP [14]. Because of this the USO problem is widely considered as a candidate for either having
a polynomial time algorithm, or being of intermediate
computational complexity, similar to the status of the
factoring problem.
A variety of classical algorithms exists for the USO
problem. Most of these are known to have instances on
which they take an exponentially long time. For example
the algorithm of randomly following one outgoing edge
of a vertex, RANDOM EDGE, can be shown to take
Ω(exp(n1/3 )) time [15]. Similarly the algorithm of choosing a random facet, and then recursing, can also be shown
to take Ω(exp(n1/2 )) time [3]. These results all give instances upon which the given algorithms fail to work in
polynomial time. In a similar vein we will show below
that a naive classical version of our quantum algorithm
that uses the standard oracle to solve the USO problem
requires exponential time.
Despite the USO problem being of intermediate com-

2
putational complexity the only quantum computation
work for this problem has been on the problem of recognizing whether an orientation is a unique sink orientation
or not [16]. We note in passing that a naive application
of Grover’s algorithm
[17] to the general USO problem
√
n
yields an O( 2 ) = O((1.414 . . .)n ) quantum algorithm,
which just marginally beats the best known classical algorithm which is O((1.467 . . .)n ) [1].

II.

UNIQUE SINK ORIENTATION PROBLEM

Here we introduce the USO problem and present some
prior results that will be useful. An excellent well-written
introduction to this problem is the Ph.D. thesis of I. A.
Schurr [18]. We begin with an information description of
the problem and then proceed to a more formal specification which is useful for stating basic useful properties
of the USO problem.
An instance of the USO problem is an orientation of
a boolean (combinatorial) hypercube which special properties. Recall that the boolean hypercube is the graph in
which vertices of the graph are boolean strings and there
is an edge between two vertices if these vertices differ in
only one character of the string. Thus 0010 is a vertex
and 0011 is one of its neighbors while 1011 is not one of
its neighbors. An orientation is a specification of a din
rection for each of the edges in the graph. There are 22
orientations. In the USO problem, however, a constraint
is imposed on the orientation. Recall that an a vertex
in a graph with directed edges is a sink if all the edges
adjacent to a vertex are incoming. In the USO problem,
the orientation is required to satisfy the condition that if
one restricts one attention a subcube, only one of these
vertices is a sink under this restriction. By restrict to a
subcube we mean consider a k ≤ n hypercube and only
examine the orientation of edges between the vertices of
this subcube.
Next we introduce the notation for the combinatorial hypercube we will use in this paper. This notation is that used by the literature about USOs and is
used here to help provide a bridge into that literature
and also to make the proofs that appear in Sec. III
cleaner. Let [n] = {1, 2, . . . , n}. We will label the vertices of the n-dimensional hypercube by the subsets of
[n]. That is vertices correspond to the power set of
[n]: V = 2[n] := {v ⊂ [n]}. If one prefers to think
about the hypercube vertices as boolean strings, then
one can consider a subset of [n] as corresponding to the
elements in an n bit string that are 1, while those not
in the subset are 0. The symmetric difference of two
sets u and v is the set of elements that are in u and
v but not both, u ⊕ v := (u ∪ v) \ (u ∩ v). Given
this definition the edges of the n-dimensional hypercube
are then vertices whose symmetric difference has size 1.
E = {(u, v)|u, v ⊆ [n], |u ⊕ v| = 1}. This the version of
the condition that an edge in a hypercube exists between
boolean strings if they differ in exactly one position.

More generally, for sets u ⊆ v define the interval of
these sets as [u : v] := {w|u ⊆ w ⊆ v}. Then the cube
spanned by these sets C [u:v] is defined as the graph with
vertex set
V (C [u:v] ) := [u : v]

(1)

E(C [u:v] ) := {(s, t)|s, t ∈ [u : v], |s ⊕ t| = 1}.

(2)

and edge set

A useful shorthand is C u = C [∅:u] , in which case the ndimensional hypercube is C [n] . Intervals are useful for
defining 0subcubes.
The cube C [u,v] is a subcube of the
0
cube C [u :v ] iff [u, v] ⊆ [u0 : v 0 ]. Subcubes of a cube are
often called faces and a face of dimension one less than
the cube is called a facet. If one prefers to work over
the boolean string representation of a hypercube, then
the vertices of a hypercube are those where a fixed set
of character positions are fixed, and other are allowed to
vary. The elements that are in v but not in u of a subcbue
C [u,v] are exactly the locations where the characters are
allowed to vary.
Edges of the n-dimensional hypercube are labeled in a
natural way by their direction label. That is for the edge
e = (u, v) there is a unique λ such that {λ} = u ⊕ v. The
set of all labels of a cube is called the carrier
carr C [u:v] := v \ u.

(3)

For a given direction λ we can split the cube into two
subcubes, called the λ-facets. In particular for the cube
C [n] , the lower λ-facet is C [n]\{λ} and the upper λ-facet
is C [{λ}:[n]] . Less formally the condition is that when one
considers only the orientations of the edges between the
vertices in a subcube, this orientation has a unique sink
vertex. See Fig. 1 for this labeling scheme and direction
in the case of n = 3.
An orientation φ of a graph G = (V, E) is a map from
the edges E to the vertices V such that φ((v, w)) = v
or φ((v, w)) = w for all (v, w) ∈ E. This maps edges
to their corresponding sink vertex. Thus if (v, w) ∈ E
and φ((v, w)) = v then the orientation has the edge E
directed from w to v. In this case w is the source and v
is the sink. Given this notion for a particular vertex we
can partition edges that contain the vertex into those for
which the vertex is the sink (incoming edges) and those
for which it is the source (outgoing edges).
{1, 2, 3}
{2, 3}
{3}

{1, 3} {1, 2}
{2}

{1}
{3}

{2}

{1}

∅
FIG. 1. Labeling of the vertices of a hypercube for n = 3 on
the left and the different directions on the right.

3
Λ ⊆ carr C the λ-edge of φ are reversed has an outmap of
s0 (v) = Λ ⊕ s(v). If the original orientation φ is a USO,
then, according to the following Lemma, the orientation
φ0 is also a USO:

{1, 2, 3}
{2, 3}
{3}

{1, 3} {1, 2}
{2}

{1}

Lemma 1 [18] Given a unique sink outmap s of a cube
C [n] , and a set of directions, Λ ⊆ carr C [n] , the map defined by s0 (v) = Λ ⊕ s(v) is the outmap of a USO.

∅
FIG. 2. Example of a USO. The unique sink is vertex {1, 3}
and the unique source is ϕ. Note, for instance that this is a
USO since all of its faces considered alone have a unique sink
vertex. For example the C [∅:{1,2}] cube has the unique sink of
{1, 2}.

Given an orientation φ of a cube C, we define the
outmap s of φ as the map that assigns to every vertex
the labels of the outgoing edges from that vertex:
s : V (C) → 2carr

C

(4)

We can now define a USO of a cube C. A USO of a
cube C is an orientation φ such that every subcube has a
unique sink. That is an orientation φ with outmap s is a
USO iff
∀u, v C [u,v] is a unique sink orientation.

(5)

where a subcube C [u,v] is a unique sink orientation if
there exists a unique vertex w such that the outmap does
not point along any of the outgoing directions in the carrier space for a subcube, carr C [u:v] ,
∃ unique w such that ∀λ ∈ carr C [u:v] , s(w) ∈
/λ

(6)

See Fig. 2 for a picture of a USO for n = 3.
The central problem we would like to solve can now be
introduced.
[n]

Problem 1 (USO) Given a USO φ on a cube C and
a subcube C [u:v] , determine by querying the outmap s of
φ whether the unique sink of C [n] lies in C [u:v] .
Note that this is a decision problem having a yes/no answer for each φ and subcube C [u:v] . However it can be
used to efficiently solve the search version of the problem,
finding the unique sink vertex of the entire cube. To do
this one simply uses the decision version on facets of the
cube, determining whether the unique sink is in one of
two facets, and then recursively applying this procedure
to the facet with the unique sink.

PROOF. We will first show this is true for Λ = {λ}.
We need to show that the new outmap s0 corresponds
to an orientation φ0 that has the USO property. Let
Cu and Cl denote the upper and lower λ-facets of C [n]
respectively. Consider any subcube C of C [n] . If C is
entirely within a λ-facet, then the orientation obtained by
reversing all edges along the λ direction does not change
the orientation on any edges of C. In this case since φ has
a unique sink on C, so does φ0 on C. On the other hand, if
C spans λ-facets, then we can partition C into sub cubes
Du = C ∪ Cu and Dd = C ∪ Cd . Over the orientation
φ suppose that these two subcubes have unique sinks
ou and od . Assume without loss of generality that the
unique sink of φ over C is ou . Flipping all of the edges
along λ means that ou is no longer a unique sink (since
it’s λ edge now points away from it). However od must
now be a unique sink of C since prior to flipping the λ
edge the only thing keeping od from being a unique sink
of C was the λ edge. All other vertices cannot be unique
sinks of C since they are not unique sinks in Du or Dd
and none of the edges in those sub cubes are flipped.
Hence φ0 is the outmap of a USO for Λ = {λ}. For
the general case of Λ = {λ1 , . . . , λk } note that it follows
from the application of the just proven case k times since
s0 (v) = Λ ⊕ s(v) = {λ1 } ⊕ · · · ⊕ {λk } ⊕ s(v).
The use of the above lemma is that it implies an important property of all outmaps of a USO of a cube.
Lemma 2 [19] The outmap of a USO of a cube C is a
bijection.
PROOF. Given a USO φ of a cube C. Suppose that
there exists two vertices, u 6= v which each have the
same image under the outmap s, s(v) = s(u) = t. Then
consider the orientation φ0 obtained by flipping all of the
edges along the t direction. This has outmap s0 (v) = t⊕v.
Via Lemma 1 this new orientation is a USO. However
s0 (u) = s0 (v) = ∅, which is a contradiction. Hence there
are not two vertices which have the same image under
the outmap s.

IV.
III.

QUANTUM APPROACH

PROPERTIES OF USOS

Here we recall certain properties of USOs on cubes
that we will use. We present short proofs of these results
for completeness.
If φ is an orientation with corresponding outmap s for
a cube C, then the orientation φ0 in which for every λ ∈

In the last section we have seen that the outmap of
a USO is a bijection from vertices to the power set of
the carrier space of the cube. Vertices are labeled by
elements of 2[n] and elements of the carrier space are also
labeled by 2[n] . Viewed in this manner we can map the
carrier space back to the vertices, and hence we can view

4
the outmap as a permutation on 2[n] . Given this view we
can then define the kth power of this map
sk := |s ◦ s ◦{z· · · ◦ s}

(7)

k times

i.e. the permutation s applied k times.
Consider the sequence
∅, s(∅), s2 (∅), . . .

(8)

Because s is a bijection this sequence is periodic with a
period at most 2n . That is there exists a minimal l > 0
such that sk (∅) = sk+l (∅).
Suppose that we could determine the minimal l 6= 0
such that sk (∅) = sk+l (∅). Then sl (∅) = ∅ and hence
s(sl−1 (∅)) = ∅, or in other words sl−1 (∅) is the unique
sink of the cube. In other words determining the period
of s, and then evaluating s raised to that power minus
one, yields the unique sink. The problem of finding the
period of a function is one in which quantum computers
offer exponential advantage over classical computers, and
this is the basis of Shor’s algorithm for factoring [4, 5].
In particular this leads us to our main result. Let φ
be a USO with outmap s. Let H = Cn2 ⊗ Cn2 ⊗ Cn2
and label the basis of these states by |k, u, vi with k ∈
{0, . . . , 2n − 1} and u, v ∈ 2[n] . We say that a unitary
U calculates the kth power of an outmap if acts on this
basis as
U |k, u, vi = |k, u, v ⊕ sk (u)i.

(9)

Theorem 1 Given a unitary U which can calculate the
kth power of the outmap permutation of a USO, there
exists a polynomial sized quantum algorithm that queries
this oracle O(1) times and identifies the unique sink with
constant probability with a circuit of size O(poly(n)).
PROOF. Straightforward application of Shor’s period
finding algorithm to the given oracle [4, 5], followed by
using the oracle once to calculate sl−1 (∅).

V.

EXPONENTIALLY LONG PERIODS

In the previous section we showed that if one could
efficiently determine the period of an outmap s of a
USO of a cube and one can evaluate the outmap at
this period minus one, then one can efficiently solve the
USO problem. A question which arises is whether or
not this an efficient classical algorithm. A naive classical use of this period finding method would be try to
calculates(∅), s2 (∅), . . . until the sequence repeats. Here
we show that this approach fails because there are USOs
where this sequence is exponentially long.
We will explicitly show an example of such a USO.
Given two USOs of the same dimension n, φ1 and φ2 ,
one can produce a new USO of dimension n + 1 by using
φ1 as a lower n+1 face and φ2 as the upper n+1 face and

then directing all of the n + 1 edges either from the lower
to the upper face, or vice versa. Label these two cases
φ1 ↑ φ2 and φ1 ↓ φ2 , respectively. It is clear that the
new orientation constructed in this manner is a USO,
since every face either lies entirely in φ1 or φ2 (and so
is a USO), or the face spans φ1 and φ2 and hence each
component in the upper and lower n+1 face has a unique
sink so the global USO exists and is uniquely the one in
which the new n + 1 orientation points.
Let ψ1 be the 1 dimensional orientation in which the
single edge points from ∅ to {1}. Further define the
uniform orientation un,a as the n dimensional orientation
whose outmap is s(v) = v ⊕ a. Recursively define the
orientation
ψn+1 = ψn ↓ un−1,∅

(10)

This orientation has ψn as it’s lower n + 1 facet, the
uniform orientation towards ∅ in its upper n + 1 facet,
and n + 1 edges from the upper to the lower n + 1 facet.
Lemma 3 Define P (φ) as the period of the outmap of φ,
starting at ∅. Then
P (ψn+1 ) = 2P (ψn )

(11)

and hence since P (ψ1 ) = 2, P (ψn ) = 2n .
PROOF. Let sn denote the outmap of ψn . The outmap
of ψn+1 can be written as

{n + 1} ∪ sn (v) if n + 1 ∈
/v
sn+1 (v) =
(12)
v \ {n + 1} otherwise
From
this
it
follows
that
the
sequence
sn+1 (∅), s2n+1 (∅), s3n+1 (∅), s4n+1 (∅), . . . is equal to
sn (∅) ∪ {n + 1}, sn (∅), s2n (∅) ∪ {n + 1}, s2n (∅) . . .. Since
sn does not act on the n + 1 element, the claim follows
directly.
Because there exist USOs like φn that have exponentially long periods the naive classical algorithm for finding the period fails. Note that this does not mean that
a classical approach based upon identifying the period
will fail, only that the naive algorithm would take exponentially long. Perhaps USOs have structure which
will would allow for an efficient classical algorithm based
upon finding the period of the outmap.
VI.

THE MISSING PIECE

We have shown that the ability to efficiently calculate
the kth power of a USOs outmap would lead to an efficient quantum algorithm for the problem and that the
same is not necessarily true for a naive classical algorithm. In Shor’s algorithm the step we are replacing with
the kth power of a USO is the evaluation of rx mod N .
This can be done by modular exponentiation (using the
trick of repeated squaring). We have been unable to find
an efficient way to calculate this kth power. In general

5
it would seem that such a procedure would need to rely
on properties of USOs. Note that in general there is
no procedure that efficiently calculates the power of an
arbitrary unitary gate. This follows from [20] where it
was shown that evaluating exp(−iHt) scales at list linearly in t, though this does not preclude such powering
for known sets of unitaries (see also [21, 22]). There are
a large classes of USOs which have structure because
they arise from different algorithmic problems [23]. For
example those arising in the P-matrix linear complementarity problem are known to be a restricted class that is
rather small relative to all USOs and yet efficiently solving the USO arising from these problem would constitute
a breakthrough. Focusing on these instances is suggested
as an important future direction.

VII.

is an efficient quantum algorithm for the USO problem.
This approaches uses a key component that is thought to
be important for quantum speedups [24], period finding.
A variety of open problems remain, even beyond the obvious of trying to efficiently power the outmap. One important question is whether there are classes of USOs for
which there is a quantum speedup. For example, USOs
that are decomposable are known have query complexity
Θ(n) [18, 25], is there a constant query quantum algorithm for these cases? Another interesting question is
whether the query complexity of the USO is polynomial
in an information theoretic sense.

CONCLUSION

We have shown that the ability to efficiently calculate
the kth power of a USOs outmap would imply that there

[1] Tibor Szabó and Emo Welzl, “Unique sink orientations of
cubes,” in Proceedings 42nd IEEE Symposium on Foundations of Computer Science (IEEE, 2001) pp. 547–555.
[2] Bernd Gärtner, “Combinatorial linear programming: Geometry can help,” in Randomization and Approximation
Techniques in Computer Science (Springer, 1998) pp. 82–
96.
[3] Bernd Gärtner, “The random-facet simplex algorithm on
combinatorial cubes,” Random Structures & Algorithms
20, 353–381 (2002).
[4] Peter W Shor, “Algorithms for quantum computation:
Discrete logarithms and factoring,” in 35th Annual Symposium on Foundations of Computer Science (IEEE,
1994) pp. 124–134.
[5] Peter W Shor, “Polynomial-time algorithms for prime
factorization and discrete logarithms on a quantum computer,” SIAM review 41, 303–332 (1999), arXiv:quantph/9508027.
[6] Richard W Cottle, Jong-Shi Pang, and Richard E Stone,
The linear complementarity problem, Vol. 60 (Siam,
1992).
[7] Leonid G Khachiyan, “Polynomial algorithms in linear
programming,” USSR Computational Mathematics and
Mathematical Physics 20, 53–72 (1980).
[8] Bernd Gärtner and Ingo Schurr, “Linear programming
and unique sink orientations,” in Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm (Society for Industrial and Applied Mathematics, 2006) pp. 749–757.
[9] Bernd Gärtner and Leo Rüst, “Simple stochastic
games and p-matrix generalized linear complementarity problems,” in Fundamentals of Computation Theory
(Springer, 2005) pp. 209–220.
[10] Ola Svensson, “Mean payoff games and linear complementarity,” in Proceedings of the ESSLLI (Citeseer,
2005).

[11] Sergei Vorobyov, “Cyclic games and linear programming,” Discrete Applied Mathematics 156, 2195–2231
(2008).
[12] Kaspar Fischer and Bernd Gärtner, “The smallest enclosing ball of balls: combinatorial structure and algorithms,” International Journal of Computational Geometry & Applications 14, 341–378 (2004).
[13] Bernd Gärtner and Antonis Thomas, “The complexity
of recognizing unique sink orientations,” in 32nd International Symposium on Theoretical Aspects of Computer
Science (2015) p. 341.
[14] Nimrod Megiddo, A note on the complexity of P-matrix
LCP and computing an equilibrium (IBM Thomas J.
Watson Research Division, 1988).
[15] Jindrich Matousek and Tibor Szabó, “RANDOM EDGE
can be exponential on abstract cubes,” in Foundations of
Computer Science, 2004. Proceedings. 45th Annual IEEE
Symposium on (IEEE, 2004) pp. 92–100.
[16] Vitor Bosshard, Classical and Quantum Algorithms for
USO Recognition, Master’s thesis, ETH Zürich (2015).
[17] Lov K Grover, “A fast quantum mechanical algorithm
for database search,” in Proceedings of the twenty-eighth
annual ACM symposium on Theory of computing (ACM,
1996) pp. 212–219, arXiv:quant-ph/9605043.
[18] Ingo Andreas Schurr, Unique sink orientations of cubes,
Ph.D. thesis, ETH Zürich (2004).
[19] Kathy Williamson Hoke, “Completely unimodal numberings of a simple polytope,” Discrete Applied Mathematics
20, 69 – 81 (1988).
[20] Dominic W Berry, Graeme Ahokas, Richard Cleve, and
Barry C Sanders, “Efficient quantum algorithms for simulating sparse hamiltonians,” Communications in Mathematical Physics 270, 359–371 (2007), quant-ph/0508139.
[21] Mehdi Soleimanifar and Vahid Karimipour, “No-go theorem for iterations of unknown quantum gates,” Physical
Review A 93, 012344 (2016), arXiv:1510.06888.

6
[22] Yosi Atia and Dorit Aharonov, “Fast-forwarding of
hamiltonians and exponentially precise measurements,”
(2016), 1610.09619.
[23] Jan Foniok, Bernd Gärtner, Lorenz Klaus,
and
Markus Sprecher, “Counting unique-sink orientations,”
Discrete Applied Mathematics 163, 155–164 (2014),

arXiv:1012.1537.
[24] Andrew M Childs and Wim Van Dam, “Quantum algorithms for algebraic problems,” Reviews of Modern
Physics 82, 1 (2010), arXiv:0812.0380.
[25] Ingo Schurr and Tibor Szabó, “Finding the sink takes
some time,” in Algorithms—ESA 2002 (Springer, 2002)
pp. 833–844.

