# On Bounded Advice Classes

Simon C. Marshall<EMAIL_ADDRESS>Casper Gyurik
Universiteit Leiden  Vedran Dunjko

###### Abstract

Advice classes in computational complexity have frequently been used to model
real-world scenarios encountered in cryptography, quantum computing and
machine learning, where some computational task may be broken down into a
preprocessing and deployment phase, each associated with a different
complexity. However, in these scenarios, the advice given by the preprocessing
phase must still be generated by some (albeit more powerful) bounded machine,
which is not the case in conventional advice classes. To better model these
cases we develop ‘bounded advice classes’, where a more powerful Turing
machine generates advice for another, less powerful, Turing machine. We then
focus on the question of when various classes generate useful advice, to
answer this we connect bounded advice to unary languages. This connection
allows us to state various conditional and unconditional results on the
utility of advice generated by $\mathsf{EXP}$, $\mathsf{NP}$, $\mathsf{BQP}$,
$\mathsf{PSPACE}$, and more. We study the relations between bounded advice
classes, quantum bounded advice classes, and randomised bounded advice. We
also examine how each of these concepts interact with recently introduced
classes, like $\mathsf{BPP/samp}$. Our results also improve the state of the
art in existing research on the complexity of advice functions.

##  1 Introduction

A common concept in complexity theory is ‘advice’, where a Turing machine is
provided with an advice string alongside its input. This string can provide
any conceivable advice on how to solve problems up to size $n$ but must be the
same advice string for all inputs of a given size. As this advice string could
be anything, advice classes are often much more powerful than their unadvised
counterparts, containing problems which are otherwise undecidable. This
powerful advice string allows advice classes to act as useful models for
problems with long/expensive preprocessing phases (modelled as advice)
followed by faster/cheaper processing phases. However, in many of these
situations, the advice is produced by a more powerful Turing machine, but not
an infinitely more powerful Turing machine, as would be the case in standard
advice classes. In such situations, it would be more appropriate to study a
form of ‘bounded advice’, where we ask what a given Turing machine of some
complexity can accomplish when given advice generated by a more powerful, but
not unbounded, Turing machine. For many cases where we might want to use
advice classes, this bounded advice captures a much tighter idea of what we
are trying to model:

  * •

Cryptography, when an adversary may be able to expend immense resources if the
information learnt allows them to break an encryption scheme for a much
smaller cost during run-time [5, 1].

  * •

Quantum computing, where the quantum computer is used to prepare an algorithm
which will run classically [12, 19, 16], or where a classical machine learning
algorithm attempts to replicate the quantum model just using data from the
quantum model [11].

  * •

Machine learning, where a large and expensive training run is used to compute
a smaller number of weights for a machine learning model. Once these weights
are computed the model is often comparatively quite cheap to run [8, 20, 18].

With bounded advice classes, we can address these scenarios, we can study how
a cryptographic scheme performs against an attacker with ‘only’ an
$\mathsf{EXP}$ generated cheat sheet, instead of an unbounded cheat sheet.
Formalising bounded advice allows us to exactly extract these ideas, and to
ask our key question: When is advice generated by a given Turing machine
useful? In this context, we can informally say a certain complexity class is a
useful advice generator to another complexity class when the former class can
be used to create advice strings that allow the latter class to recognize
strictly more languages.

In Section 2 we give common notation and define the class of problems solvable
by advice generated by a certain complexity class, e.g.
$\mathsf{P/poly^{EXP}}$ is the class of problems solvable by a polynomial-time
Turing machine with access to an exponential-time machine. We also review
closely connected work on the complexity of advice functions [9, 13, 8, 14,
15, 6]. This previous work typically studies the functional complexity of
generating the advice for a given problem in $\mathsf{P/poly}$. While our
results allow us to push the state of the art in this research direction (we
are able to improve the strongest result), we primarily focus on a closely
related, but different question: ‘For a given complexity of advice generator,
what problems can be solved?’.

In Section 3 we prove a connection between bounded advice and unary languages.
Namely:

$\mathsf{P/poly^{B}=P/poly^{Un(P^{B})}=P^{Un(P^{B})}},$

where $\mathsf{Un(B)}$ denotes the set of all unary languages in a class
$\mathsf{B}$.

This connection allows us to directly produce results on when given complexity
classes generate useful advice in Section 4.

  * •

$\mathsf{P\subsetneq P/poly^{EXP}}$

  * •

$\mathsf{P\subsetneq P/poly^{NP}}\iff\mathsf{EXP\neq EXP^{NP}}$

  * •

$\mathsf{P\subsetneq P/poly^{PSPACE}}\iff\mathsf{EXP\neq EXPSPACE}$

We connect our framework to existing quantum classes,
$\mathsf{BPP/samp^{BQP}\subseteq P/poly^{Un\left(ZPP^{NP^{BQP}}\right)}}$222We
will later define $\mathsf{BPP/samp^{BQP}}$ as the class of problems which can
be solved on a quantum computer or by a $\mathsf{BPP}$ machine with samples
from the quantum computer and with randomised advice
$\mathsf{BPP/samp^{BQP}}\subseteq\mathsf{P/rpoly^{BQP}}$ in Section 4.2. This
section also connects bounded quantum advice (where the advice itself is a
quantum state) into our framework, proving the bounded-advice equivalent of
the well known result, $\mathsf{BQP/qpoly\subseteq QMA/poly}$ [3]:

$\mathsf{BQP/qpoly^{B}}\subseteq\mathsf{QMA/poly^{ZPP^{QMA^{B}}}}.$

##  2 Background

###  2.1 General notation and definitions

This work makes use of notation or definitions that, while standard, may only
be known to readers of specific backgrounds. To aid with readibility by a wide
audience we provide a short list of notation, definitions of common complexity
classes should be checked in the complexity zoo [4].

  * •

The symbol ‘$\\#$’: It is often useful to join two inputs together to pass
them both to a Turing machine, e.g. if we want to calculate $x+y$ for $x=010$
and $y=11$ we will need to pass both $x$ and $y$, but as both are written in
binary a simple concatenation makes it unclear where $x$ ends and $y$ begins,
$xy=01011$. To solve this problem we introduce a special symbol to our
alphabet, $\\#$, which will be used to simply demarcate where two strings
meet, e.g. $x\\#y=010\\#11$

  * •

Prefixes: We say $x$ is a length $n$ prefix of $y$ if $x$ is length $n$ and
the first $n$ letters of $y$ are equal to $x$, e.g. $x=100$ is a length 3
prefix of $y=100010$.

  * •

Turing machine standardisation: Unless otherwise specified a Turing machine is
assumed to be a polynomial time deterministic Turing machine. Turing machine
is often abbreviated to TM. Occasionally the TM will not be deterministic or
not polynomial time, this will be specified or be clear from context (i.e. the
previous line specified a non-deterministic Turing machine and the following
line talks about ‘this TM’).

  * •

Unary: A unary language is a language such that all elements $x\in L$ consist
of a string of 1’s, i.e. $\forall x\in L$ $\exists m$ such that $x=1^{m}$.

The set of all unary languages is written $\mathsf{TALLY}$, all unary
languages in some complexity classes $\mathsf{B}$ could be written
$\mathsf{TALLY\cap B}$, but we find it is clearer to write
$\mathsf{Un(B):=TALLY\cap B}$.

  * •

Sparsity: A sparse language is a language which has at most $\mathrm{poly(n)}$
elements of size $n$.

The class of all sparse languages is written as $\mathsf{SPARSE}$.

The set of all sparse languages in a complexity class, $\mathsf{B}$, can be
written $\mathsf{SPARSE\cap B}$ (the intersection of these two classes) but
for notational clarity, we will write it as $\mathsf{SP(B):=SPARSE\cap B}$.
This significantly improves readability but may confuse readers familiar with
an older form of relativisation notation: $\mathsf{B(C):=B^{C}}$.

  * •

Which exponential time? $\mathsf{E}$ vs $\mathsf{EXP}$. There are two
standard, but non-equivalent, definitions of exponential time decision
problems: $\mathsf{E}$, which is equal to $\mathsf{DTIME(2^{O(n)})}$, and
$\mathsf{EXP}$, which is equal to $\bigcup_{\text{all polynomials
}p}\mathsf{DTIME(2^{p(n)})}$. This work will make it clear when our results
apply to only one of these definitions or to both. Older works, some cited
here, may not conform to this nomenclature.

  * •

$\bm{L(x)}$: For a language $L$ the function $L(x)$ is equal to 1 if $x\in L$
and 0 otherwise.

  * •

$\bm{1^{n}}$: $1^{n}$ denotes a string of ones of length $n$. $1^{4}=1111$.

  * •

$\mathsf{B-C}$. For two complexity classes, $\mathsf{B}$ and $\mathsf{C}$, the
class $\mathsf{B-C}$ is the set of all the languages in $\mathsf{B}$ that are
not also in $\mathsf{C}$. This notation comes from the definition of
complexity classes as sets.

###  2.2 Oracle-machines and double oracles

The standard definition of an oracular complexity class is given as follows.

######  Definition 1 (Oracular classes).

The complexity class of problems solvable by an algorithm in $\mathsf{B}$ with
access to an oracle for a language ${L}$ is $\mathsf{B^{L}}$. This extends to
define an oracular complexity class, $\mathsf{C}$ by taking the union:

$\mathsf{B^{C}:=\bigcup_{L\in C}B^{L}}$

Sometimes a single Turing machine will have to make Oracle calls to two
different languages, while this can be defined within the existing framework
by creating a third language that can answer oracular calls to either
language, we find it much simpler to define a double oracle machine.

######  Definition 2 (Double oracles).

For complexity classes $\mathsf{B}$, $\mathsf{C}$ and $\mathsf{D}$, a double
oracle machine is a Turing machine, $T$, with oracular access to two problems,
$L_{0}$, and $L_{1}$. The complexity class is:

$\mathsf{D^{B,C}=\bigcup_{L_{B}\in B,L_{C}\in C}D^{L_{B},L_{C}}}$

In previous works the notation $\mathsf{L_{B}\oplus L_{C}}$ is used for this
purpose. While logically equivalent we find the comma notation to be much
clearer, additionally it makes sparsity more apparent as either if
$\mathsf{B}$ or $\mathsf{C}$ are sparse their set-addition may not be.

###  2.3 Bounded and unbounded advice classes

We can now move onto the meat of our definitions: advice classes.

######  Definition 3 (Advice classes).

A language $L$ is in the advice class of $\mathsf{B}$, $\mathsf{B/poly}$, if
there exists an integer, $d$, and a set of advice strings,
$a=\\{a_{i}:|a_{i}|<di^{d}\\}_{i\in\mathbb{N}}$, such that the language

$L^{\prime}=\\{x\\#a_{|x|}:x\in L\\}$

is in $\mathsf{B}$.

At this point the extension of this definition to bounded advice seems
obvious, we just have to specify what it means for a complexity class to
‘generate’ a piece of advice. But it is not clear how a decision algorithm
(which outputs a bit) ‘in’ $\mathsf{C}$ generates a piece of advice (a string
of symbols). Fortunately, a lot of heavy lifting has already been done with
the definition of ‘transducers’ [17], which, unlike the standard definition of
a Turing machine, gives the entire final state of the tape as the output,
where a regular Turing machine only outputs ‘reject’ or ‘accept’.

Unfortunately, on closer inspection, transducers do not have the properties we
want; consider polynomial-sized advice generated by an exponential time
machine, which polynomially-sized piece of the exponentially long tape should
we take? Or a non-deterministic Turing machine, which path do we accept? What
about for even more artificial classes, like $\mathsf{SPARSE}$, which is
defined without reference to Turing machines at all! Previous works [9, 13, 8,
14, 15, 6] have dealt with these problems by using functional complexity
classes. While well-defined, functional complexity classes can have very
different properties from their decision-class counterparts [2], they also
lack a clear notion of unary languages, which is of key importance to this
work.

To combat these issues we choose a definition of bounded advice that uses the
tape from a polynomial-time Turing machine with oracular access to another
class. This is equivalent to using a $\mathsf{FP^{B}}$ advice generator for
some oracle class $\mathsf{B}$. This definition solves our problem of defining
the output tape but inherently transforms the advice generator into a
$\mathsf{P^{C}}$ machine, which makes it difficult to study classes for which
$\mathsf{P^{C}\not=C}$.

######  Definition 4 (Polynomial-sized bounded advice classes).

For arbitrary complexity classes, $\mathsf{B}$ and $\mathsf{C}$, a language
$L$ is in $\mathsf{B/poly^{C}}$ if there is an infinite set of advice strings,
$\\{a_{n}\\}_{n\in\mathbb{N}}$, such that:

  * •

(Advice Generation) There exists a deterministic polynomial-time ‘advice
generating’ Turing machine, T, with oracular access to $\mathsf{C}$ which on
input $1^{n}$ terminates in $\mathrm{poly(n)}$ time with $a_{n}$ as the final
state of its tape.

  * •

(Advice Use) The language

$L^{\prime}=\\{x\\#a_{|x|}:x\in L\\}$

is in $\mathsf{B}$

The notion of unbounded advice classes extends beyond classes of the form
$\mathsf{B/poly}$; logarithmic advice is possible with $\mathsf{B/log}$,
quantum advice, consisting of quantum states is possible with
$\mathsf{B/qpoly}$, or randomised advice can be captured with
$\mathsf{B/rpoly}$ [2]. Similarly, different flavours of bounded advice are
possible; $\mathsf{B/exp^{C}}$ is the class of problems solvable by
$\mathsf{B}$ given advice generated by a Turing machine running for
exponentially long, or a quantum advice generator $\mathsf{B/qpoly^{C}}$, or
even a non-deterministic advice generator $\mathsf{B/npoly^{C}}$. Exploring
these definitions may allow future papers to work around the
‘$\mathsf{P}$-oracle problem’ (how to study advice generated by a class
$\mathsf{C}$ such that $\mathsf{P^{C}\neq C}$). For our purposes, we will only
need one of the possible extensions of bounded advice.

######  Definition 5 ($\mathsf{BQP/qpoly^{C}}$).

For a fixed gate set and initial state, $\ket{0}$, a language $L$ is in
$\mathsf{BQP/qpoly^{C}}$ if the following two criteria are true:

  * •

(Advice Generation) There exists a polynomial-sized uniform family of quantum
circuits with oracular access to $\mathsf{C}$, $\\{Q_{n}\\}_{n\in\mathbb{N}}$
generating a set of advice states, $\\{\ket{\phi_{n}}=Q_{n}\ket{0}\\}$.

  * •

($\mathsf{BQP}$ Advice Use) There exists a polynomial-time quantum algorithm
$A$ such that for all $n$, $A(x,\ket{\phi_{n}})$ outputs $L(x)$ with
probability more than $2/3$ for all $x$ up to length $n$.

###  2.4 Previous work

We are not the first to consider bounded advice classes although a seemingly
minor difference in our framing brings us to a novel set of questions and
results. Much of the previous work on bounded advice has centred on the
question ‘If a given class $\mathsf{A}$ is in $\mathsf{P/poly}$, what is the
complexity of generating the advice string?’. This naturally leads to studying
the complexity of the ‘advice function’, a function which prints the advice
used by the $\mathsf{P/poly}$ algorithm. The strongest answer to this question
was noticed by Köbler and Watanabe [15] as a corollary to a result by Bshouty
et al. [6], showing that the advice function for any $\mathsf{A\in P/poly}$ is
in $\mathsf{FZPP^{NP^{A}}}$.

While our bounded advice classes are equivalent to studying the advice
function, the reframing leads to a different set of questions. Instead of
asking ‘for a given problem, what is the advice function to solve this?’ we
ask ‘for a given advice function, which problems can this solve?’. This
naturally leads to our central question of ‘when are certain advice classes
useful?’. It also forces us to standardise our notation and classes, which
proves useful to deriving more flexible results. Finally, instead of studying
functional classes to specify the advice function, we choose to stay within
decision classes. This allows us to use the well-known connection between
advice classes and unary languages.

For clarity, we will restate the state of the art result by Bshouty/Köbler
using our terminology.

######  Theorem 6 ([6, 15]).

For any set $\mathsf{A\in P/poly}$: $\mathsf{A\in P/poly^{ZPP^{NP^{A}}}}$

Reexamining the proof of [6] it is easy to see this generalises to
$\mathsf{B/poly}$. We can also use the connection to unary languages we derive
later to produce a stronger version of Bshouty et al.’s theorem.

######  Theorem 7.

For any complexity class, $A$, if $\mathsf{A\subseteq C}$ and
$\mathsf{A\subseteq B/poly}$ then $\mathsf{A\subseteq
B/poly^{Un\left(ZPP^{NP^{B,C}}\right)}}$

Many of our other results will rely on the well-known connection between
advice classes and unary/sparse languages. As most research in advice
functions has been functional languages this connection has scarcely been
used. The only connection we are aware of is to a 1985 result by Ko and
Schöning [13], showing that all sparse sets in $\mathsf{\Sigma_{i}^{p}}$ are
also in $\mathsf{P/poly}$ with an advice function in
$\mathsf{F\Delta^{p}_{i+1}}$.

##  3 Connection to sparse and unary languages

It is well known that any language in $\mathsf{P/poly}$ is Turing reducible to
a unary language. Here we prove an analogous result, that any language in
$\mathsf{P/poly^{B}}$ is Turing reducible to a unary language in
$\mathsf{P^{B}}$. We show this inclusion is tight, i.e. the set
$\mathsf{P/poly^{B}}$ is exactly the set of languages which are Turing
reducible to a unary language in $\mathsf{P^{B}}$. We further show that all
languages that are Turing reducible to sparse languages in $\mathsf{P^{B}}$
(i.e. in $\mathsf{P^{SP(P^{B})}}$) are also in $\mathsf{P/poly^{NP^{B}}}$.

To prove the main results we will need the following lemmas:

######  Lemma 8.

For any complexity class $\mathsf{B}$:

$\mathsf{P^{Un({P^{B}})}\subseteq P/poly^{B}}.$

###### Proof.

As $\mathsf{Un(P^{B})}$ has at most $n$ elements up to length $n$, the advice
can simply be an $n$ length string, $a$, whose $m$’th element is 1 iff
$1^{m}\in L$. Obviously, this string can be generated by $n$ queries to an
$\mathsf{P^{B}}$ language. The advice-receiving Turing machine can then use
this advice to simulate oracle calls to the $\mathsf{P^{B}}$ language. ∎

######  Lemma 9.

For any complexity classes $\mathsf{B}$ and $\mathsf{C}$,

$\mathsf{C/poly^{B}\subseteq P^{C,Un({P^{B}})}}$

###### Proof.

Take any $L\in\mathsf{C/poly^{B}}$, let $a_{n}$ be the advice string generated
by the advice generator, and let $p(n)$ be the polynomial which bounds the
length of the advice string ($\absolutevalue{a_{n}}\leq p(n)$), W.L.O.G. we
may assume the advice is a bit string of exactly $p(n)$ bits. We will now
describe an oracle in $\mathsf{Un(P^{B})}$ that can be used to generate
$a_{n}$ in polynomial time.

Define the language:

$L_{advice}=\\{1^{p(n)}1^{m}|\text{ the m'th bit of }a_{n}\text{ is 1 }\\}$

By the definition of bounded advice $a_{n}$ can be generated in polynomial
time with a $\mathsf{B}$ oracle, deciding if a particular bit is 1 or 0 is
also polynomial time. Therefore $L_{advice}$ is a unary language in
$\mathsf{P^{B}}$.

The language ${L_{advice}}$ can be used to construct $a_{n}$ one bit at a
time. This advice string can then be passed to the $\mathsf{C}$ oracle to
simulate the $\mathsf{C/poly^{B}}$ algorithm, showing that the language $L$ is
in $\mathsf{P^{C,Un(P^{B})}}$. ∎

Combining lemma 8 and lemma 9 we get the central theorem of this section:

######  Theorem 10.

For any complexity class $\mathsf{B}$,

$\mathsf{P/poly^{B}=P^{Un({P^{B}})}}$

A simple corollary, $\mathsf{P/poly^{B}=P/poly^{Un(P^{B})}}$, provides us with
a key insight: all bounded advice is unary advice.

The result of Theorem 10 also holds for advice receivers other than
$\mathsf{P}$. The choice of fixing $\mathsf{P}$ as the advice receiver was
merely to ensure Turing reductions. Following the steps of the proof for other
classes provides the following corollary.

######  Corollary 11.

$\mathsf{BPP/poly^{B}=BPP^{Un(P^{B})}}$ $\mathsf{NP\cap coNP/poly^{B}=(NP\cap
coNP)^{Un(P^{B})}}$ $\mathsf{BQP/poly^{B}}=\mathsf{BQP^{Un(P^{B})}}$

While the connection to unary languages is tighter, bounded advice can also be
connected to sparsity, finding that sparse languages always sit inside some
bounded advice class (Theorem 12), and bounded advice classes are contained in
sparse languages (Corollary 13). Theorem 12 is similar to the work of Ko and
Schöning [13] who show that all sparse sets in $\mathsf{\Sigma_{i}^{p}}$ are
also in $\mathsf{P/poly}$ with an advice function in
$\mathsf{F\Delta^{p}_{i+1}}$. Our result differs as it is both wider-reaching
(applying to classes outside the polynomial hierarchy) and showing inclusions
in both directions (advice inside sparsity, and sparsity inside advice).

######  Theorem 12.

For any complexity class $\mathsf{B}$,

$\mathsf{P^{SP(P^{B})}\subseteq P/poly^{SP(NP^{B})}}$

###### Proof.

Let $K$ be a language in $\mathsf{P^{SP(P^{B})}}$. Then there exists a sparse
language, ${L}$ in $\mathsf{P^{B}}$ such that $K\in P^{L}$. As $L$ is sparse
there are at most polynomially many strings $x\in L$ of any particular length,
$n$. Our strategy will be to find all of these strings with the advice
generating TM, to create a list, $A_{n}=\\{x:x\in L,|x|\leq n\\}$, and pass
$A_{n}$ as advice. The advice using TM can then simulate an oracle call to $L$
by simply checking if $x$ is on the list.

It is possible to generate $A_{n}$ in polynomial time with access to an
$\mathsf{NP^{B}}$ oracle, with access to the (sparse) language:

$L^{\prime}_{sparse}=\\{1^{n}\\#p:\exists x\text{ with }x\in L,\text{ and $p$
is a prefix of }x\\}.$

As $L$ is in $\mathsf{P^{B}}$ existence of an $x\in L$ is in
$\mathsf{NP^{B}}$.

We can use $L^{\prime}_{sparse}$ to find a complete list of strings by
beginning with an empty list, $A=\\{\\}$. We begin by using algorithm 1
starting from an empty string to find an initial element, $x\in L$, and put
this element in $A$. If we try to nïavely reuse algorithm 1 to find more
elements it may not return a new value of $x\in L$. We must force the
algorithm to return a new value of $x$. We can solve this problem by beginning
the search from some particular prefix, instead of the empty string.

Figure 1: Step of the procedure for finding all the elements of a sparse
language using $L^{\prime}$. We begin with a possibly incomplete list, $A$,
consisting of elements of $L$ below to some given size, $n$. In step a. we
represent $A$ with a prefix tree, each layer representing a possible prefix of
the string. If a string is a prefix for an element in $\mathsf{A}$ its branch
continues to a green node. b. We add the possible unexplored children to the
tree. We then use algorithm 1 starting from each unexplored child prefixes to
find possible new elements of $A$. Either one is found and added to $A$ (d.)
or none are found, implying there are none left to find and $A$ is complete
(c.).

Suppose our list, $A$, has $m$ elements in it. This defines a partially
explored trie, as shown in figure 1. At each node there are two children, one
child must be an explored path that leads to at least one previously found
element of $x\in A$, the other child may be unexplored. By beginning the
search with a prefix from one of the unexplored children (highlighted in step
b of figure 1) we will find any unfound elements beginning with that prefix.
If a new element is found we add it to $A$ and search its unexplored prefixes.
If no new elements are found after all prefixes have been explored then we
conclude the list $A$ is complete. This list is our advice.

As $A_{n}$ has at most polynomial elements and the tree is polynomially deep,
finding each element takes at most polynomial time. Creating the advice string
$A$ therefore takes polynomial time with an $\mathsf{NP^{B}}$ oracle, as
$L^{\prime}_{sparse}$ is also sparse, we have shown the result:

$\mathsf{P^{SP(P^{B})}\subseteq P/poly^{SP(NP^{B})}}.$

Algorithm 1 Binary search variant to find $a_{n}$ from $L_{sparse}$

Input: An integer $n$, a starting prefix, $p$

Output: The string $a^{\prime}$

1:$a^{\prime}\leftarrow$ “$p$” $\triangleright$ Initializing $a^{\prime}$ to
the given prefix

2:$advice\\_complete\leftarrow$ False $\triangleright$ Initializing
$advice\\_complete$ to False

3:while $advice\\_complete$ is False do

4: if $1^{n}\\#a^{\prime}0\in L$ then $\triangleright$ Find a symbol to append
to the advice string

5: $a^{\prime}\leftarrow a^{\prime}0$

6: else if $1^{n}\\#a^{\prime}1\in L$ then

7: $a^{\prime}\leftarrow a^{\prime}1$

8: else

9: $advice\\_complete\leftarrow$ True $\triangleright$ If no next symbol can
be found, then the string is complete

∎

Theorem 12 shows sparse languages are in a form of bounded advice, the
converse is also possible as a simple corollary of Theorem 10 as
$\mathsf{Un(B)\subseteq Sp(B)}$.

######  Corollary 13.

$\mathsf{P/poly^{B}\subseteq P^{SP(P^{B})}}$

##  4 When is bounded advice useful?

This section will address this paper’s fundamental question: “When is advice
generated by a given complexity class useful?” i.e. when advice from one class
increases the amount of problems that can be solved by another class. In the
first subsection, we will characterise when some major complexity classes
generate advice useful to a polynomial time machine (i.e. when
$\mathsf{P/poly^{A}}$ is not simply equal to $\mathsf{P}$). In the second
subsection, we look at when quantum complexity classes are useful advice
generators, this allows us to study a class of proposed uses of quantum
computing that prepare classical algorithms. We connect
$\mathsf{BPP/rpoly^{BQP}}$ to the class of languages that can be decided with
samples from a quantum computer through $\mathsf{BPP/samp}$[11]. We derive a
result connecting quantum bounded polynomial advice (i.e. a quantum state) to
non-quantum bounded polynomial advice (a classical bitstring).

###  4.1 Useful classical advice

As shown in the previous section $\mathsf{P/poly^{B}=P^{Un(P^{B})}}$, thus
bounded advice is useful if and only if unary languages are useful oracles.
Much is known about the conditions for the existence of various unary
languages, thus, this connection opens a variety of choices for grounding the
hardness of various bounded advice classes. We provide a number of these
results for the most famous complexity classes.

######  Theorem 14.

$\mathsf{P\neq P/poly^{EXP}}$

######  Theorem 15.

$\mathsf{P\neq P/poly^{PSPACE}}$ if and only if $\mathsf{EXPSPACE\neq EXP}$.

######  Theorem 16.

$\mathsf{P\neq P/poly^{NP}}$ if and only if $\mathsf{EXP^{NP}\neq EXP}$.

######  Theorem 17.

$\mathsf{BPP\neq BPP/poly^{BQP}}$ if and only if $\mathsf{BPEXP\neq BQEXP}$

Many other results in unary languages can be used to prove results in advice
classes. Such as showing the polynomial hierarchy gives useful advice if the
exponential hierarchy doesn’t collapse. However, for brevity, we have provided
only these 4.

###### Proof of Theorem 14.

We prove this result via showing $\mathsf{P\neq P^{Un(EXP)}}$. By the time
hierarchy theorem, there exists an $L$ such that,

$L\in\mathsf{DTIME(2^{n^{3}})-DTIME(2^{n^{2}})}.$

From $L$ we define the unary language:

${L_{unary}=\\{1^{x}:x\in L\\}}$

${L_{unary}}$ cannot be decided in $o(2^{log(n)^{2}})$, a quasipolynomial,
thus $\mathsf{L_{unary}}\notin\mathsf{P}$.

Given a string from $L_{unary}$, $1^{x}$, calculating $x$ takes $x$ steps,
therefore ${L_{unary}}$ can be decided by a deterministic Turing machine in
$O(2^{log(n)^{3}})$ time. As $\mathsf{DTIME(2^{log(n)^{3}})\subseteq EXP}$,
$L_{unary}\in\mathsf{EXP}$. Therefore we have demonstrated there exists a
unary language in $\mathsf{EXP-P}$, by theorem 10 this implies
$\mathsf{P/poly^{EXP}\neq P}$ ∎

###### Proof of Theorem 15.

By Theorem 10 $\mathsf{P/poly^{PSPACE}=P^{Un(P^{PSPACE})}}$, as
$\mathsf{P^{PSPACE}=PSPACE}$ [4] we derive the equality:
$\mathsf{P/poly^{PSPACE}=P^{Un({PSPACE})}}$. If $\mathsf{EXPSPACE=EXP}$ there
are no unary languages in $\mathsf{PSPACE-P}$ [10], proving the ‘only if’
direction. For the other direction we notice that all unary languages in
$\mathsf{PSPACE}$ are in $\mathsf{P^{Un(P^{PSPACE})}}$, therefore if
$\mathsf{P^{Un(P^{PSPACE})}=P}$ there are no unary languages in
$\mathsf{PSPACE}$ and $\mathsf{EXPSPACE=EXP}$ [10]. ∎

###### Proof of Theorem 16.

There are unary languages in $\mathsf{P^{NP}-P}$ if and only
$\mathsf{EXP^{NP}\neq EXP}$. Therefore $\mathsf{P/poly^{NP}}$ $\mathsf{\neq
P}$ if and only if $\mathsf{EXP^{NP}\neq EXP}$. ∎

###### Proof of Theorem 17.

There are unary languages in $\mathsf{BQP-BPP}$ if and only $\mathsf{BPEXP\neq
BQEXP}$, by a simple extension of the arguments in [10]. Therefore
$\mathsf{P/poly^{BQP}}$ $\mathsf{\neq P}$ if and only if $\mathsf{BQEXP\neq
BPEXP}$. ∎

###  4.2 Useful Quantum advice

This subsection studies bounded quantum advice and when it is useful. First,
we examine classical advice strings generated by quantum computers, this case
contains many of the proposed algorithms to use quantum computers to prepare
algorithms for classical machines [12, 11, 7, 19]. One prominent example,
using samples from some problem to produce an algorithm that can solve
instances of the same problem, is formalised in the class $\mathsf{BPP/samp}$,
if the samples are produced from a quantum computer, we denote it as the class
$\mathsf{BPP/samp^{BQP}}$ [11]. While it may be expected that
$\mathsf{BPP/samp^{BQP}}$ is contained in $\mathsf{P/poly^{BQP}}$ this
neglects the randomness in the sample selection, and we will show it is
instead contained in $\mathsf{P/rpoly^{BQP}}$. We also show a derandomised
result, that $\mathsf{BPP/samp^{BQP}}$ is contained in
$\mathsf{P/poly^{Un\left(ZPP^{NP^{BQP}}\right)}}$. Second, we study the
properties of bounded advice when the advice is itself a quantum state:
$\mathsf{BQP/qpoly^{B}}$, finding it is contained in a classical bounded
advice state $\mathsf{QMA\cap coQMA/poly^{Un(ZPP^{QMA^{B}})}}$.

######  Definition 18 ($\mathsf{BPP/samp}$ [11]).

A language $L$ is in $\mathsf{BPP/samp}$ if there exists probabilistic
polynomial-time Turing machines $M$ and $D$ with the following properties: On
input $1^{n}$, $D$ produces output distribution $\mathcal{D}_{n}$. $M$ takes
an input of size $n$ along with ‘samples’ from $L$,
$\mathcal{T}=\\{(x_{i},L(x_{i}))\\}_{i=1}^{poly(n)}$, where $x_{i}$ is sampled
from $\mathcal{D}_{n}$. $M$ outputs 1 with probability greater than $2/3$ if
${x\in L}$ , and less than $1/3$ if $x\notin L$, where the probability taken
is over the randomness in both sample selection and random coins.

The original definition of $\mathsf{BPP/samp}$ [11] is not explicit which
domain the $2/3$ failure probability applies to, it could be that for most
sets of samples the machine $M$ must function ‘according to the rules of
$\mathsf{BPP}$’ (for all points there is a $2/3$ probability of failure over
the coin flips), or it could be that for each point, a $2/3$ probability of
failure applies over both the set of samples and the set of coin flips. While
the former appears to be a much tighter restriction (the majority of all sets
work on all points for most sets of coin flips), fortunately, these two
definitions are equivalent via a simple boosting-and-majority-vote argument.
Similarly, it is clear that the use of $\mathsf{BPP}$ in the definition of
$\mathsf{BPP/samp}$ is superfluous as if there is randomness over the samples,
this randomness is sufficient to use as randomness to simulate coin flips. If
a given $\mathsf{BPP/samp}$ algorithm requires $m$ random coins, we can ask
for extra samples and use the random inputs $x$ as random coins333The random
distribution of samples, $\mathcal{D}_{n}$, might not be uniform, infact there
is no requirement for it to be non-deterministic. Fortunately, we can always
append $m/\absolutevalue{x}$ uniform random samples on the end of our set of
samples to use as random coin flips..

######  Theorem 19.

$\mathsf{BPP/samp=P/samp}$

For our purposes, we are interested in exactly the restriction of
$\mathsf{BPP/samp}$ to samples that can be produced by a particular machine
(i.e. a quantum machine/$\mathsf{BQP}$). We define $\mathsf{BPP/samp^{B}}$
equivalently to $\mathsf{BPP/samp}$ but requiring that the labelling problem
($L(x)$) is in the complexity class $\mathsf{B}$. Fortunately, this is simply
$\mathsf{BPP/samp\cap B}$.

######  Lemma 20.

$\mathsf{BPP/samp^{B}=BPP/samp\cap B}$

From this definition, the following result is immediately clear:

######  Theorem 21.

$\mathsf{BPP/samp^{BQP}\subseteq BPP/rpoly^{BQP}}$

As noted by Watrous [21] randomised advice can be used to give random coins to
a probabilistic algorithm, which extends to bounded advice to show
$\mathsf{BPP/rpoly^{BQP}=P/rpoly^{BQP}}$. This connection improves Theorem 21
to the following corollary.

######  Corollary 22.

$\mathsf{BPP/samp^{BQP}\subseteq P/rpoly^{BQP}}$

As noted above, the definition of $\mathsf{BPP/samp}$ seems to require
randomised advice. Fortunately, we can use Theorem 21 to derandomise this
advice, connecting $\mathsf{BPP/samp^{BQP}}$ to a deterministic bounded advice
class.

######  Theorem 23.

$\mathsf{BPP/samp^{BQP}\subseteq P/poly^{Un\left(ZPP^{NP^{BQP}}\right)}}$

###### Proof.

As $\mathsf{BPP/samp^{BQP}\subseteq BQP}$ and $\mathsf{BPP/samp^{BQP}\subseteq
P/poly}$, applying Theorem 21 produces the desired result. ∎

Similar these techniques bound other ‘quantum preparation classes’, such as
$\text{CSIM}_{\text{QE}}$ [7].

We can now turn our attention to quantum states given as advice, the standard
equivalent result in unbounded advice classes for connecting quantum advice to
advice is $\mathsf{BQP/qpoly\subseteq QMA\cap coQMA/poly}$ [3], we show a
close analogue exists for bounded advice classes:

######  Theorem 24.

$\mathsf{BQP/qpoly^{A}\subseteq QMA\cap coQMA/poly^{ZPP^{QMA^{A}}}}$

###### Proof.

Aaronson [3] and Drucker showed:

$\mathsf{BQP/qpoly\subseteq QMA\cap coQMA/poly}$

As $\mathsf{BQP/qpoly^{A}\subseteq BQP^{A}}$ we can apply Theorem 6 to derive:

$\mathsf{BQP/qpoly^{A}\subseteq QMA\cap coQMA/poly^{Un(ZPP^{QMA^{QMA\cap
coQMA,BQP^{A}}})}}$

This result can be significantly simplified, first, we note that
$\mathsf{QMA\cap coQMA}$ is low for $\mathsf{QMA}$

$\mathsf{QMA^{QMA\cap coQMA,BQP^{A}}\subseteq QMA^{BQP^{A}}}$

Then, we use $\mathsf{QMA^{BQP^{A}}=QMA^{A}}$ to derive the result

$\mathsf{BQP/qpoly^{A}\subseteq QMA\cap coQMA/poly^{Un(ZPP^{QMA^{A}})}}$

∎

## Acknowledgements

VD and SCM acknowledge the support by the project NEASQC funded from the
European Union’s Horizon 2020 research and innovation programme (grant
agreement No 951821). VD and SCM also acknowledge partial funding by an
unrestricted gift from Google Quantum AI. CG was supported by the Dutch
Research Council (NWO/OCW), as part of the Quantum Software Consortium
programme (project number 024.003.037). This work was supported by the
European Union’s Horizon Europe program through the ERC ERC CoG BeMAIQuantum
(Grant No. 101124342). This work was also supported by the Dutch National
Growth Fund (NGF), as part of the Quantum Delta NL programme.

## References

  * [1] Scott Aaronson.  Nsa in p/poly: The power of precomputation, 2015.  Published on May 22nd, 2015.
  * [2] Scott Aaronson, Harry Buhrman, and William Kretschmer.  A qubit, a coin, and an advice string walk into a relational problem.  arXiv preprint arXiv:2302.10332, 2023.
  * [3] Scott Aaronson and Andrew Drucker.  A full characterization of quantum advice.  SIAM Journal on Computing, 43(3):1131–1183, 2014.
  * [4] Scott Aaronson, Greg Kuperberg, and Oliver Habryka.  Complexity zoo, 2023.  Accessed: date.
  * [5] David Adrian, Karthikeyan Bhargavan, Zakir Durumeric, Pierrick Gaudry, Matthew Green, J Alex Halderman, Nadia Heninger, Drew Springall, Emmanuel Thomé, Luke Valenta, et al.  Imperfect forward secrecy: How diffie-hellman fails in practice.  In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, pages 5–17, 2015.
  * [6] Nader H. Bshouty, Richard Cleve, Ricard Gavaldà, Sampath Kannan, and Christino Tamon.  Oracles and queries that are sufficient for exact learning.  Journal of Computer and System Sciences, 52(3):421–433, 1996.
  * [7] M Cerezo, Martin Larocca, Diego García-Martín, NL Diaz, Paolo Braccia, Enrico Fontana, Manuel S Rudolph, Pablo Bermejo, Aroosa Ijaz, Supanut Thanasilp, et al.  Does provable absence of barren plateaus imply classical simulability? or, why we need to rethink variational quantum computing.  arXiv preprint arXiv:2312.09121, 2023.
  * [8] R. Gavalda.  The complexity of learning with queries.  In Proceedings of IEEE 9th Annual Conference on Structure in Complexity Theory, pages 324–337, 1994.
  * [9] R. Gavalda.  Bounding the complexity of advice functions.  Journal of Computer and System Sciences, 50(3):468–475, 1995.
  * [10] Juris Hartmanis.  On sparse sets in np–p.  Information Processing Letters, 16(2):55–60, 1983.
  * [11] Hsin-Yuan Huang, Michael Broughton, Masoud Mohseni, Ryan Babbush, Sergio Boixo, Hartmut Neven, and Jarrod R McClean.  Power of data in quantum machine learning.  Nature communications, 12(1):2631, 2021.
  * [12] Sofiene Jerbi, Casper Gyurik, Simon C Marshall, Riccardo Molteni, and Vedran Dunjko.  Shadows of quantum machine learning.  arXiv preprint arXiv:2306.00061, 2023.
  * [13] Ker-I Ko and Uwe Schöning.  On circuit-size complexity and the low hierarchy in np.  SIAM Journal on Computing, 14(1):41–51, 1985.
  * [14] Johannes Köbler and Thomas Thierauf.  Complexity-restricted advice functions.  SIAM Journal on Computing, 23(2):261–275, 1994.
  * [15] Johannes Köbler and Osamu Watanabe.  New collapse consequences of np having small circuits.  SIAM Journal on Computing, 28(1):311–324, 1998.
  * [16] Jonas Landman, Slimane Thabet, Constantin Dalyac, Hela Mhiri, and Elham Kashefi.  Classically approximating variational quantum machine learning with random fourier features.  arXiv preprint arXiv:2210.13200, 2022.
  * [17] Alexander Meduna.  Turing Transducers, pages 833–887.  Springer London, London, 2000.
  * [18] N. Rajgopal and R. Santhanam.  On the structure of learnability beyond P/Poly.  In Mary Wootters and Laura Sanità, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021), volume 207 of Leibniz International Proceedings in Informatics (LIPIcs), pages 46:1–46:23, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  Sections 2.4, 3.
  * [19] Franz J Schreiber, Jens Eisert, and Johannes Jakob Meyer.  Classical surrogates for quantum learning models.  Physical Review Letters, 131(10):100803, 2023.
  * [20] Ilya Volkovich.  On learning, lower bounds and (un) keeping promises.  In International Colloquium on Automata, Languages, and Programming, pages 1027–1038. Springer, 2014.
  * [21] John Watrous.  Quantum computational complexity.  arXiv preprint arXiv:0804.3401, 2008.