text:
# Abstract.

#### Abstract.

Krentel \[J. Comput. System. Sci., 36, pp.490–509\] presented a framework for an NP optimization problem that searches an optimal value among exponentially-many outcomes of polynomial-time computations. This paper expands his framework to a quantum optimization problem using polynomial-time quantum computations and introduces the notion of an “universal” quantum optimization problem similar to a classical “complete” optimization problem. We exhibit a canonical quantum optimization problem that is universal for the class of polynomial-time quantum optimization problems. We show in a certain relativized world that all quantum optimization problems cannot be approximated closely by quantum polynomial-time computations. We also study the complexity of quantum optimization problems in connection to well-known complexity classes.

#### Keywords:

optimization problem, quantum Turing machine, universal problems

## 1 Introduction

Quantum computation theory was initiated in the early 1980s and has shown significant phenomena beyond the classical framework. During the 1990s, many classical concepts in complexity theory were examined and interpreted in quantum context, including the notions of “bounded-error polynomial-time computation” , “interactive proof system” , “parallel query computation” , “Kolmogorov complexity” , and “Merlin-Arthur game” . Along this line of research, this paper studies a quantum interpretation of a classical optimization problem.

An optimization problem is in general a certain type of search problem which is to find, among candidates to which some values are assigned, the maximal (or minimal) value or to find a solution with such the value. A typical example of such an optimization problem is the traveling salesperson problem that asks, upon given a map of cities and their traveling distances, for the length of a shortest tour to all the cities in the map. In the 1980s, Krentel  laid out a framework for studying the complexity of such optimization problems. He defined $`\mathrm{𝐎𝐩𝐭𝐏}`$ to be the collection of functions outputting the maximal (or minimal) value of indexed functions computable in polynomial-time. To locate the hardest optimization problems in $`\mathrm{𝐎𝐩𝐭𝐏}`$, Krentel introduced the notion of “completeness” under his metric reduction. The Traveling Salesperson Problem turns out to be a complete optimization problem for $`\mathrm{𝐎𝐩𝐭𝐏}`$ .

This paper studies a quantum interpretation of Krentel’s optimization problem. Krentel’s framework is easily generalized to the problem of optimizing the acceptance probabilityThe collection of all functions that output the acceptance probability of certain polynomial-time well-formed Turing machines is denoted $`\mathrm{\#}\mathrm{𝐐𝐏}`$ in . of indexed polynomial-time quantum computations. In consistence with Krentel’s notation, the notation $`\mathrm{𝐎𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ is used for the class of these problems. However, this is a mixture of classical indexing and quantum computations. Instead, we introduce quantum functions indexed with a quantum state of polynomially-many qubits (called a quantum index). A quantum optimization problem, discussed in this paper, is to ask for a maximal acceptance probability of quantum computations labeled with quantum indices. We use the notation $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ to denote the collection of such quantum optimization problems.

These quantum optimization problems are also characterized by maximal eigenvalues of certain types of positive semidefinite, contractive, Hermitian matrices. In Section 5, we use this characterization to show fundamental properties of quantum optimization problems in $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$.

The existence of complete optimization problems has largely contributed to the success of the theory of NP optimization problems. These complete optimization problems are considered, among all NP optimization problems, as the “hardest” problems to solve. In Section 6, we develop a similar “hardest” notion for quantum optimization problems. As shown by Bernstein and Vazirani , there exists a universal quantum Turing machine that simulates any well-formed quantum Turing machine with amplitudes approximable in polynomial time at the cost of polynomial slowdown. Different from a classical universal Turing machine, since all amplitudes are only approximated, the universal quantum Turing machine can simulate other machines only approximately to within a given closeness parameter. This manner of simulation gives rise to the notion of approximate reduction. We say that a function $`f`$ is approximately reducible to another function $`g`$ if $`f`$ has a Krentel’s metric-type reduction from $`f`$ to a certain function that approximates $`g`$ to within $`1/m`$, where $`m`$ is an accuracy parameter given as an auxiliary input to the reduction. In this fashion, we can define the notion of universal optimization problems for the class $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$. This notion requires two functions to be apart only in a distance that is a reciprocal of a polynomial. In Section 6, we exhibit an example of a canonical universal optimization problem, which can be viewed as a generalization of the Bounded Halting Problem for $`\mathrm{𝐍𝐏}`$. This notion of universality naturally induces promise-complete problems for many well-known quantum complexity classes, such as $`\mathrm{𝐁𝐐𝐏}`$ and $`\mathrm{𝐐𝐌𝐀}`$, which are believed to lack complete problems.

The class $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ includes its underlying class $`\mathrm{\#}\mathrm{𝐐𝐏}`$ as well as $`\mathrm{𝐎𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$. However, the complexity of $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ is not well-understood even in comparison with $`\mathrm{\#}\mathrm{𝐐𝐏}`$. This function class $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ naturally introduces the class of decision problems $`\mathrm{𝐐𝐎𝐏}`$ (“quantum optimization polynomial time”) in such a way that $`\mathrm{𝐏𝐏}`$ is characterizedA set $`S`$ is in $`\mathrm{𝐏𝐏}`$ iff there exit two functions $`f,g\mathrm{\#}𝐏`$ such that, for every $`x`$, $`xAf(x)>g(x)`$. by two $`\mathrm{\#}𝐏`$-functions. This class $`\mathrm{𝐐𝐎𝐏}`$ lies between $`\mathrm{𝐏𝐏}`$ and $`\mathrm{𝐏𝐒𝐏𝐀𝐂𝐄}`$. In Section 7, we show that, under the assumption $`\mathrm{𝐄𝐐𝐏}=\mathrm{𝐐𝐎𝐏}`$, every quantum optimization problem in $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ can be closely approximated by functions in $`\mathrm{\#}\mathrm{𝐐𝐏}`$. We may not remove the assumption because there exists a counterexample in a relativized world. Moreover, if every quantum optimization problem in $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ can be closely approximated by functions in $`\mathrm{\#}\mathrm{𝐐𝐏}`$, then $`\mathrm{𝐐𝐎𝐏}`$ is included in $`𝐏^{\mathrm{\#}𝐏[1]}`$.

The quantum optimization problems are also used to characterize other major complexity classes. One of the useful tools is the notion of “definability”, which is adapted from an earlier work of Fenner et al. . A complexity class $`𝒞`$ is called $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$-definable if we have a pair of disjoint sets $`A,R\mathrm{\Sigma }^{}\times `$ such that every set $`A`$ in $`𝒞`$ has witnesses $`f`$ in $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$; that is, for every $`x`$, if $`xA`$ then $`(x,f(x))A`$ and otherwise $`(x,f(x))R`$. An obvious example of such $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$-definable sets is the class $`\mathrm{𝐐𝐌𝐀}`$, a quantum version of Merlin-Arthur proof systems . A less trivial example is $`\mathrm{𝐍𝐐𝐏}`$, introduced by Adleman et al. . However, it is not yet known whether $`\mathrm{𝐏𝐏}`$ is $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$-definable. We present a partial answer to this question in Section 8 by giving a new characterization of $`\mathrm{𝐏𝐏}`$ in terms of quantum optimization problems. This characterization also yields Watrous’s recent result that $`\mathrm{𝐐𝐌𝐀}`$ is included in $`\mathrm{𝐏𝐏}`$ .

The $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$-definability gives light to the relationship between $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ and other well-known complexity classes. From a different perspective, we focus on the structure of the complexity classes that are induced from $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$. An example of such complexity classes is the class $`\mathrm{𝐐𝐎𝐏}`$. Based upon our new characterization of $`\mathrm{𝐏𝐏}`$ in Section 8, we introduce the new complexity class $`\mathrm{𝐀𝐐𝐌𝐀}`$. In Section 9, we first show several Boolean closure properties of $`\mathrm{𝐐𝐎𝐏}`$ and $`\mathrm{𝐀𝐐𝐌𝐀}`$. Another important concept in complexity theory is low sets. Any set $`A`$ that bears only poor information when it is used as an oracle for relativizable class $``$ (that is, $`^A=`$) is called an $``$-low set. We show that the class of $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$-low sets lies between $`\mathrm{𝐄𝐐𝐏}`$ and $`\mathrm{𝐄𝐐𝐌𝐀}`$, which is an error-free version of $`\mathrm{𝐐𝐌𝐀}`$ . This contrasts the known result that the class of $`\mathrm{\#}\mathrm{𝐐𝐏}`$-low sets is exactly $`\mathrm{𝐄𝐐𝐏}`$ .

## 2 Preliminaries

We introduce important notions and notation in this section.

Let $``$, $``$, and $``$ denote the sets of all natural numbers (e.g., nonnegative integers), of all real numbers, and of all complex numbers, respectively. Let $`^+=\{0\}`$. Let $`𝔻`$ be the collection of all dyadic rational numbers, where a dyadic rational number is of the form $`0.r`$ or $`0.r`$ for a certain finite series $`r`$ of $`0`$s and $`1`$s. In this paper, a polynomial means a multi-variate polynomial with nonnegative integer coefficients.

For any function $`f`$ and any integer $`m>0`$, $`f^m`$ denotes the function satisfying $`f^m(x)=(f(x))^m`$ for all $`x`$. For example, $`\mathrm{log}^kn`$ means $`(\mathrm{log}n)^k`$ for each $`k^+`$. The notation $`A^B`$, where $`A`$ and $`B`$ are any nonempty sets, denotes the set of all total functions mapping from $`A`$ to $`B`$: for example, $`^{}`$, $`𝔻^{}`$, etc. For any two functions $`f`$ and $`g`$ with the same domain, we say that $`f`$ majorizes $`g`$ if $`f(x)g(x)`$ for all $`x`$ in the domain of $`g`$.

Any element of a Hilbert space (i.e., a complex vector space with the standard inner product) of finite dimension is expressed by Dirac’s ket notation $`|\varphi `$. For an $`n\times n`$ matrix $`A=(a_{ij})_{1i,jn}`$ over $``$, the notation $`A^{}`$ denotes the Hermitian adjoint (i.e., the transposed complex conjugate) of $`A`$. Moreover, $`A`$ denotes the operator norm of $`A`$ defined by $`sup\{A|\varphi /|\varphi \}`$, where the supremum is over all nonzero vectors $`|\varphi `$. Note that if $`A`$ is Hermitian, then $`A=sup_{|\varphi 0}\{|\varphi |A|\varphi |/|\varphi \}`$. A square matrix $`A`$ is contractive if $`A1`$. See, e.g.,  for more detail.

#### Classical Complexity:

Our alphabet is $`\mathrm{\Sigma }=\{0,1\}`$ throughout this paper and assume the standard (canonical and lexicographical) order on $`\mathrm{\Sigma }^{}`$. The empty string is denoted $`\lambda `$. For a string $`x`$, $`|x|`$ denotes the length of $`x`$. We assume the reader’s familiarity with multi-tape, off-line Turing machines (TMs). We fix a pairing function $`,`$, which is a one-to-one map from $`\mathrm{\Sigma }^{}\times \mathrm{\Sigma }^{}`$ to $`\mathrm{\Sigma }^{}`$, satisfying that, for a certain polynomial $`p`$, $`|x,y|p(|x|,|y|)`$ for all $`x`$ and $`y`$. In particular, we assume that the paring function preserves the length, that is, $`|x,y|=|x^{},y^{}|`$ whenever $`|x|=|x^{}|`$ and $`|y|=|y^{}|`$.

Let $`\stackrel{~}{}`$ be the set of all polynomial-time approximable complex numbers (that is, the real and imaginary parts are approximated to within $`2^k`$ in time polynomial in the size of input together with $`k`$). For any two sets $`A`$ and $`B`$, $`AB`$ is the disjoint union of $`A`$ and $`B`$ defined by $`AB=\{0xxA\}\{1xxB\}`$.

We also assume the reader’s familiarity with basic complexity classes: $`𝐏`$, $`\mathrm{𝐍𝐏}`$, $`\mathrm{co}\text{-}\mathrm{𝐍𝐏}`$, $`\mathrm{𝐁𝐏𝐏}`$, $`\mathrm{𝐏𝐏}`$, $`\mathrm{𝐏𝐒𝐏𝐀𝐂𝐄}`$, and $`\mathrm{𝐄𝐗𝐏}`$. The definition of theses complexity classes are found in, e.g., . In particular, we use the notation $`\mathrm{𝐅𝐏}`$ to denote the collection of all polynomial-time computable functions from $`\mathrm{\Sigma }^{}`$ to $`\mathrm{\Sigma }^{}`$. Similarly, $`\mathrm{𝐅𝐏𝐒𝐏𝐀𝐂𝐄}`$ is defined as the collection of polynomial-space computable functions whose outputs are also bounded by polynomials.

The class $`\mathrm{\#}𝐏`$ consists of all functions $`f`$ from $`\mathrm{\Sigma }^{}`$ to $``$ whose values are exactly the number of accepting paths of some polynomial-time nondeterministic TMs . Moreover, $`\mathrm{𝐆𝐚𝐩𝐏}`$ is the set of functions from $`\mathrm{\Sigma }^{}`$ to $``$ that calculate the difference between the number of accepting paths and the number of rejecting paths of polynomial-time nondeterministic TMs . For convenience, we translate the binary outcome of a Turing machine to an integer or a dyadic rational number by identifying $`\{0,1\}^{}`$ with $``$ or $`\{\pm 0.rr\{0,1\}^{}\}`$ in the standard order§§§To translate an integer or a dyadic rational number into a string, we use the first bit (called the sign bit) of the string to express the sign (that is, $`+`$ or $``$) of the number.. By this identification, we have the basic inclusions: $`\mathrm{𝐅𝐏}\mathrm{\#}𝐏\mathrm{𝐆𝐚𝐩𝐏}\mathrm{𝐅𝐏𝐒𝐏𝐀𝐂𝐄}`$.

#### Quantum Complexity:

A quantum state is a vector of unit norm in a Hilbert space. A quantum bit (qubit, for short) is a quantum state of two-dimensional Hilbert space. We mainly use the standard basis $`\{|0,|1\}`$ to express a quantum state. Any quantum state in $`2^n`$-dimensional Hilbert space is called a quantum string (qustring, for short) of size $`n`$. The notation $`_{\mathrm{}}`$ is used for the collection of all finite qustrings for brevity.

We use multi-tape quantum Turing machines (QTMs), defined in , as a mathematical model of quantum computation. A multi-tape QTM is equipped with two-way infinite tapes, tape heads, and a finite-control unit, similar to a classical TM. A QTM follows its transition function (or algorithm), which dictates the next move of the machine. Formally, a $`k`$-tape QTM $`M`$ is a six-tuple $`(Q,\mathrm{\Sigma }_1\times \mathrm{\Sigma }_2\times \mathrm{}\times \mathrm{\Sigma }_k,\mathrm{\Gamma }_1\times \mathrm{\Gamma }_2\times \mathrm{}\times \mathrm{\Gamma }_k,q_0,Q_f,\delta )`$, where $`Q`$ is a finite set of internal states including the initial state $`q_0`$ and a set $`Q_f`$ of final states, each $`\mathrm{\Sigma }_i`$ is an input alphabet of tape $`i`$, each $`\mathrm{\Gamma }_i`$ is a tape alphabet of tape $`i`$ including a blank symbol and $`\mathrm{\Sigma }_i`$, and $`\delta `$ is a quantum transition function from $`Q\times \mathrm{\Gamma }_1\times \mathrm{}\times \mathrm{\Gamma }_k`$ to $`^{Q\times \mathrm{\Gamma }_1\times \mathrm{}\times \mathrm{\Gamma }_k\times \{L,N,R\}^k}`$. An oracle QTM is a QTM equipped with an extra query tape and two distinguished states: a pre-query and post-query states. Let $`A`$ be an oracle. When the machine enters a pre-query state, the string written in the query tape, say $`|x|b`$, where $`x\mathrm{\Sigma }^{}`$ and $`b\{0,1\}`$, is changed into $`|x|bA(x)`$ in a single step and the machine enters a post-query state. The running time of $`M`$ on multi-inputs $`\stackrel{}{x}`$ is the minimal number $`t`$ (if any) such that, at time $`t`$, all computation paths of $`M`$ on inputs $`\stackrel{}{x}`$ reach final configurations (i.e., configurations with final states). We say that $`M`$ on inputs $`\stackrel{}{x}`$ halts in time $`t`$ if the running time of $`M`$ on $`\stackrel{}{x}`$ is defined and is exactly $`t`$.

The transition function is considered as an operator that transforms a superposition of configuration at time $`t`$ to another superposition of configurations at time $`t+1`$. We call such an operator a time-evolution operator (or matrix). A QTM has $`K`$-amplitudes if all the entries of its time-evolution matrix are drawn from set $`K`$. A QTM is called well-formed if its time-evolution operator is unitary (see Appendix for three local requirements given in ). For simplicity, all QTMs dealt in this paper are assumed to be well-formed unless otherwise stated. A $`k`$-tape QTM $`M`$ is stationary if all tape heads move back to the start cells, and $`M`$ is in normal form if, for every $`qQ_f`$, there exists a series of directions $`\stackrel{}{d}\{L,N,R\}^k`$ such that $`\delta (q,\stackrel{}{\sigma })=|q_0|\stackrel{}{\sigma }|\stackrel{}{d}`$ for all tape symbols $`\stackrel{}{\sigma }\mathrm{\Gamma }_1\times \mathrm{}\times \mathrm{\Gamma }_k`$. We say that a well-formed QTM $`M`$ accepts input $`|\varphi `$ with probability $`\alpha `$ if $`M`$ halts in a final configuration in which, when observed, bit $`1`$ is found in the start cell of the output tape with probability $`\alpha `$. In this case, we also say that $`M`$ rejects input $`|\varphi `$ with probability $`1\alpha `$.

A function $`f`$ from $`\mathrm{\Sigma }^{}`$ to the unit real interval $`[0,1]`$ is in $`\mathrm{\#}\mathrm{𝐐𝐏}`$ (“sharp” QP) if there exists a polynomial-time well-formed QTM $`M`$ with $`\stackrel{~}{}`$-amplitudes such that, for every $`x`$, $`f(x)`$ is the probability that $`M`$ accepts $`x`$ . In this case, we simply say that $`M`$ witnesses $`f`$. A function $`f`$ from $`\mathrm{\Sigma }^{}`$ to $`[1,1]`$ is in $`\mathrm{𝐆𝐚𝐩𝐐𝐏}`$ if there exists a polynomial-time well-formed QTM $`M`$ with $`\stackrel{~}{}`$-amplitudes such that, for every $`x`$, $`f(x)`$ is the difference between the acceptance probability of $`M`$ on input $`x`$ and the rejection probability of $`M`$ on $`x`$ . Let $`\mathrm{𝐅𝐄𝐐𝐏}`$ be the collection of all functions from $`\mathrm{\Sigma }^{}`$ to $`\mathrm{\Sigma }^{}`$ whose outputs are produced by polynomial-time, $`\stackrel{~}{}`$-amplitude, well-formed QTMs with certainty . A set $`A`$ is in $`\mathrm{𝐁𝐐𝐏}`$ if there exists a function $`f`$ in $`\mathrm{\#}\mathrm{𝐐𝐏}`$ such that, for every $`x`$, if $`xA`$ then $`f(x)3/4`$ and otherwise $`f(x)1/4`$ . A set $`A`$ is in $`\mathrm{𝐍𝐐𝐏}`$ if there exists a function $`f`$ in $`\mathrm{\#}\mathrm{𝐐𝐏}`$ such that, for every $`x`$, $`xA`$ iff $`f(x)>0`$ .

Remark on the convention of quantum extension: Although we normally deal with classical inputs for a QTM $`M`$, we sometimes feed $`M`$ with quantum states. In this way, however, we can naturally expand the definition of a function $`f`$ based on classical strings to a function $`\stackrel{ˇ}{f}`$ based on qustrings without altering $`M`$ that defines $`f`$. Such $`\stackrel{ˇ}{f}`$ is called the quantum extension of $`f`$. By abusing the notation, we use the same symbol $`f`$ to cope with both functions. We use the same convention for a set of strings.

Using the aforementioned convention of quantum extension, we define $`\mathrm{𝐐𝐌𝐀}`$ as follows: a set $`A`$ is in $`\mathrm{𝐐𝐌𝐀}`$ if there exist a polynomial $`p`$ and a function $`f`$ in $`\mathrm{\#}\mathrm{𝐐𝐏}`$ such that, for every $`x`$, if $`xA`$ then $`f(|x|\varphi )3/4`$ for a certain qustring $`|\varphi `$ of size $`p(|x|)`$ and if $`xA`$ then $`f(|x|\varphi )1/4`$ for every qustring $`|\varphi `$ of size $`p(|x|)`$ Kitaev  and Watrous  defined the class $`\mathrm{𝐐𝐌𝐀}`$ based on the quantum circuit model. In this paper, for our convenience, we use the quantum Turing machine model..

## 3 Krentel’s Framework for Optimization Problems

Optimization problems have arisen in many areas of computer science. Most $`\mathrm{𝐍𝐏}`$-complete decision problems, for instance, naturally yield their optimization counterparts. In the 1980s, Krentel  made a systematic approach toward NP optimization problems. In particular, he studied the problems of finding the maximal (as well as minimal) outcome of a polynomial-time nondeterministic computation and he introduced the function class, called $`\mathrm{𝐎𝐩𝐭𝐏}`$, that constitutes all such optimization problems.

###### Definition 3.1

 A function from $`\mathrm{\Sigma }^{}`$ to $``$ is in $`\mathrm{𝐎𝐩𝐭𝐏}`$ if there exists a polynomial-time nondeterministic TM $`M`$ such that, for every $`x`$, (i) every computation path of $`M`$ on input $`x`$ terminates with binary strings (which are interpreted as natural numbers) on its output tape and accepts and (ii) $`f(x)`$ is the maximumAlthough Krentel also includes the minimization problems into $`\mathrm{𝐎𝐩𝐭𝐏}`$, this paper focuses only on maximization problems as in  and Definition 3.1 does not include any minimization problems. output value of $`M`$ on input $`x`$.

Using the notion of $`\mathrm{𝐅𝐏}`$-functions, we rephrase Definition 3.1 in the following way: a function $`f`$ is in $`\mathrm{𝐎𝐩𝐭𝐏}`$ iff there exist a polynomial $`p`$ and a function $`g\mathrm{𝐅𝐏}`$ such that, for every $`x`$,

$$f(x)=\mathrm{max}\{g_s(x)s\text{ is any string of length }p(|x|)\text{ }\},$$

where $`g_s(x)`$ means $`g(x,s)`$ for each $`s`$ viewed as an index. This characterization enables us to generalize $`\mathrm{𝐎𝐩𝐭𝐏}`$ to $`\mathrm{𝐎𝐩𝐭}`$ by replacing an $`\mathrm{𝐅𝐏}`$-function $`g`$ with another function from a more general function class $``$.

###### Definition 3.2

Let $``$ be any set of functions from $`\mathrm{\Sigma }^{}`$ to $``$. A function $`f`$ from $`\mathrm{\Sigma }^{}`$ to $``$ is in $`\mathrm{𝐎𝐩𝐭}`$ if there exists a polynomial $`p`$ and a function $`g`$ in $``$ such that, for every $`x`$, $`f(x)=\mathrm{max}\{g_s(x)s\mathrm{\Sigma }^{p(|x|)}\}`$, where $`g_s(x)=g(x,s)`$. The subscript $`s`$ is called a classical index. The class $``$ is called the underlying class of $`\mathrm{𝐎𝐩𝐭}`$.

With this general notation, $`\mathrm{𝐎𝐩𝐭𝐅𝐏}`$ coincides with $`\mathrm{𝐎𝐩𝐭𝐏}`$. Another example obtained from the above definition is the function class $`\mathrm{𝐎𝐩𝐭}\mathrm{\#}𝐏`$ by taking $`\mathrm{\#}𝐏`$ as an underlying class. Clearly, $`\mathrm{𝐎𝐩𝐭𝐏}\mathrm{\#}𝐏\mathrm{𝐎𝐩𝐭}\mathrm{\#}𝐏`$ since $`\mathrm{𝐅𝐏}\mathrm{\#}𝐏`$ (by identifying binary strings with natural numbers). Moreover, we can define the class $`\mathrm{𝐎𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ by taking $`\mathrm{\#}\mathrm{𝐐𝐏}`$ as an underlying set. This class naturally expands $`\mathrm{𝐎𝐩𝐭}\mathrm{\#}𝐏`$ but stays within $`\mathrm{\#}\mathrm{𝐐𝐏}^{\mathrm{𝐍𝐏}^{\mathrm{𝐏𝐏}}}`$.

###### Lemma 3.3

1. For every $`f\mathrm{𝐎𝐩𝐭}\mathrm{\#}𝐏`$, there exist two functions $`g\mathrm{𝐎𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ and $`\mathrm{}\mathrm{𝐅𝐏}`$ such that, for all $`x`$, $`f(x)=g(x)\mathrm{}(1^{|x|})`$.
2. $`\mathrm{𝐎𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}\mathrm{\#}\mathrm{𝐐𝐏}^{\mathrm{𝐍𝐏}^{\mathrm{𝐏𝐏}}}`$.

For the proof, we need the following result from a revision of .

###### Lemma 3.4

\[33, revision\] Let $`A`$ be any set. The following three statements are all equivalent: (i) $`A\mathrm{𝐏𝐏}`$; (ii) there exist two functions $`f,g\mathrm{\#}\mathrm{𝐐𝐏}`$ such that, for every $`x`$, $`xA`$ iff $`f(x)>g(x)`$; and (iii) there exist two functions $`f,g\mathrm{𝐆𝐚𝐩𝐐𝐏}`$ such that, for every $`x`$, $`xA`$ iff $`f(x)>g(x)`$.

Proof of Lemma 3.3.  1) Let $`f`$ be any function in $`\mathrm{𝐎𝐩𝐭}\mathrm{\#}𝐏`$. That is, there exists a polynomial $`p`$ and a function $`h\mathrm{\#}𝐏`$ such that $`f(x)=\mathrm{max}\{h_s(x)s\mathrm{\Sigma }^{p(|x|)}\}`$, where $`h_s(x)=h(x,s)`$. By the argument used in , we can define $`k\mathrm{\#}\mathrm{𝐐𝐏}`$ and $`\mathrm{}\mathrm{𝐅𝐏}`$ that satisfy the following condition: $`k(x,s)=0`$ if $`|s|p(|x|)`$, and otherwise, $`k(x,s)\mathrm{}(1^{|x|})=h(x,s)`$. For the desired $`g`$, define $`g(x)=\mathrm{max}\{k_s(x)s\mathrm{\Sigma }^{p(|x|)}\}`$ for each $`x`$.

2) Let $`f`$ be any function in $`\mathrm{𝐎𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ and take a $`g\mathrm{\#}\mathrm{𝐐𝐏}`$ and a polynomial $`p`$ such that $`f(x)=\mathrm{max}\{g_s(x)s\mathrm{\Sigma }^{p(|x|)}\}`$ for all $`x`$. Choose the lexicographically minimal string $`s_x`$ such that $`f(x)=g(x,s_x)`$ and $`|s_x|=p(|x|)`$. Define $`A=\{x,s,t,yz(sztg_z(x)0.y)\}`$. Note that $`A`$ belongs to $`\mathrm{𝐍𝐏}^{\mathrm{𝐏𝐏}}`$ by Lemma 3.4. The function $`f`$ is computed as follows using $`A`$ as an oracle. Let $`x`$ be any input of length $`n`$. By binary search, we find a string $`\widehat{y}`$ such that (i) $`g_{s_x}(x)0.\widehat{y}`$ and (ii) for every $`z\mathrm{\Sigma }^{p(|x|)}`$, $`g_z(x)<g_{s_x}(x)`$ implies $`g_z(x)<0.\widehat{y}`$. Then, by decreasing the interval $`[s,t]`$ in a way similar to the binary search, we can find a string $`s_0`$ of length $`p(|x|)`$ such that $`g_{s_0}(x)0.\widehat{y}`$. At last, we compute $`g_{s_0}(x)`$ in a quantum fashion. Thus, $`f`$ is in $`\mathrm{\#}\mathrm{𝐐𝐏}^A\mathrm{\#}\mathrm{𝐐𝐏}^{\mathrm{𝐍𝐏}^{\mathrm{𝐏𝐏}}}`$. $`\mathrm{}`$

We next show that the collapse $`\mathrm{𝐎𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}=\mathrm{\#}\mathrm{𝐐𝐏}`$ is unlikely. To state Proposition 3.6, we recall from  the class $`\mathrm{𝐖𝐐𝐏}`$, which is a quantum analogue of $`\mathrm{𝐖𝐏𝐏}`$ in .

###### Definition 3.5

 A set $`S`$ is in $`\mathrm{𝐖𝐐𝐏}`$ (“wide” QP) if there exist two functions $`f\mathrm{\#}\mathrm{𝐐𝐏}`$ and $`g\mathrm{𝐅𝐄𝐐𝐏}`$ such that, for every $`x`$, (i) $`g(x)(0,1]`$ and (ii) if $`xS`$ then $`f(x)=g(x)`$ and otherwise $`f(x)=0`$, where we identify a string with a rational number expressed as a pair of integers (e.g., $`g(x)=\frac{1}{3}`$).

Note that $`\mathrm{𝐄𝐐𝐏}\mathrm{𝐖𝐐𝐏}\mathrm{𝐍𝐐𝐏}\mathrm{𝐏𝐏}`$. However, we do not know any relationship between $`\mathrm{𝐖𝐐𝐏}`$ and $`\mathrm{𝐁𝐐𝐏}`$.

###### Proposition 3.6

$`\mathrm{𝐏𝐏}=\mathrm{𝐄𝐐𝐏}`$ $``$ $`\mathrm{\#}\mathrm{𝐐𝐏}=\mathrm{𝐎𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ $``$ $`\mathrm{𝐏𝐏}=\mathrm{𝐖𝐐𝐏}`$.

###### Proof.

If $`\mathrm{𝐄𝐐𝐏}=\mathrm{𝐏𝐏}`$ then $`\mathrm{𝐍𝐏}^{\mathrm{𝐏𝐏}}\mathrm{𝐏𝐏}^{\mathrm{𝐏𝐏}}\mathrm{𝐄𝐐𝐏}^{\mathrm{𝐄𝐐𝐏}}=\mathrm{𝐄𝐐𝐏}`$. Since $`\mathrm{\#}\mathrm{𝐐𝐏}^{\mathrm{𝐄𝐐𝐏}}=\mathrm{\#}\mathrm{𝐐𝐏}`$ , by Lemma 3.3, we obtain $`\mathrm{𝐎𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}\mathrm{\#}\mathrm{𝐐𝐏}`$.

For the second implication, assume that $`\mathrm{\#}\mathrm{𝐐𝐏}=\mathrm{𝐎𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$. Let $`A`$ be an arbitrary set in $`\mathrm{𝐏𝐏}`$. As shown in , $`\mathrm{𝐏𝐏}`$ coincides with its quantum analogue $`\mathrm{𝐏𝐐𝐏}_\stackrel{~}{}`$. Thus, there exists a function $`f\mathrm{\#}\mathrm{𝐐𝐏}`$ such that, for every $`x`$, (i) if $`xA`$ then $`f(x)>1/2`$ and (ii) if $`xA`$ then $`f(x)<1/2`$. Define $`g(x)=\mathrm{max}\{f(x),\frac{1}{2}\}`$ for every $`x`$. This $`g`$ is clearly in $`\mathrm{𝐎𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ and thus in $`\mathrm{\#}\mathrm{𝐐𝐏}`$. By the definition of $`g`$, if $`xA`$ then $`g(x)>1/2`$ and otherwise $`g(x)=1/2`$. Next, define $`h(x)=g(x)\frac{1}{2}`$ for all $`x`$’s. Since $`\mathrm{𝐆𝐚𝐩𝐐𝐏}=\mathrm{\#}\mathrm{𝐐𝐏}\mathrm{\#}\mathrm{𝐐𝐏}`$ , $`h`$ is in $`\mathrm{𝐆𝐚𝐩𝐐𝐏}`$. Thus, $`h^2`$ is in $`\mathrm{\#}\mathrm{𝐐𝐏}`$ . For this $`h^2`$, it follows that $`xA`$ implies $`h^2(x)>0`$ and $`xA`$ implies $`h^2(x)=0`$. At this moment, we obtain that $`A\mathrm{𝐍𝐐𝐏}`$.

Since $`h^2`$ is in $`\mathrm{\#}\mathrm{𝐐𝐏}`$, there exists a polynomial $`p`$ such that, for every $`x`$, if $`h^2(x)>0`$ then $`h^2(x)>2^{p(|x|)}`$ because the acceptance probability of a QTM is expressed in terms of a polynomial in the transition amplitudes from $`\stackrel{~}{}`$. To complete the proof, we define $`k(x)=\mathrm{min}\{h^2(x),2^{p(|x|)}\}`$ for every $`x`$. It follows that $`xA`$ implies $`k(x)=2^{p(|x|)}`$ and $`xA`$ implies $`k(x)=0`$. To see that $`k`$ is in $`\mathrm{\#}\mathrm{𝐐𝐏}`$, consider the fact that $`1k(x)=\mathrm{max}\{1h^2(x),12^{p(|x|)}\}`$ is in $`\mathrm{𝐎𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$, which is $`\mathrm{\#}\mathrm{𝐐𝐏}`$ by our assumption. Thus, $`1(1k(x))`$ is also in $`\mathrm{\#}\mathrm{𝐐𝐏}`$, which implies that $`k`$ is in $`\mathrm{\#}\mathrm{𝐐𝐏}`$. ∎

At the end of this section, we note that Krentel’s framework has been extended in several different manners in the literature .

## 4 Quantum Optimization Problems

Krentel’s optimization problems are to maximize the value of indexed functions chosen from underlying class $``$. As shown in the previous section, Krentel’s framework can cope with the class $`\mathrm{𝐎𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$. However, $`\mathrm{𝐎𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ is a concoction of a classical indexing system and quantum computations. In this section, we truly expand Krentel’s framework and introduce quantum optimization problems. Our quantum optimization problem uses a quantum computation together with a quantum index, which is a qustring of polynomial size. We begin with the general definition, paving a road to our study of $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$.

###### Definition 4.1

Let $``$ be a set of functions from $`\mathrm{\Sigma }^{}\times _{\mathrm{}}`$ to $``$. A quantum optimization problem $`f`$ from $`\mathrm{\Sigma }^{}`$ to $``$ is in $`\mathrm{𝐐𝐨𝐩𝐭}`$ if there exist a polynomial $`p`$ and a function $`g`$ such that, for all $`x`$,

$$f(x)=sup\{g_{|\varphi }(x)\text{ }|\varphi \text{ is any qustring of size }p(|x|)\text{ }\},$$

where $`g_{|\varphi }(x)=g(x,|\varphi )`$. The subscript $`|\varphi `$ is called a quantum index. For simplicity, we say that $`g`$ witnesses $`f`$.

In the course of a study on a quantum optimization problem, it is rather convenient to optimize the acceptance probability of a polynomial-time well-formed QTM indexed with a quantum state. From this reason, we mainly study the class $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ throughout this paper and leave other platforms to the interested reader. This class $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ consists of all quantum optimization problems $`f`$ such that there exist a polynomial $`p`$ and a multi-tape, polynomial-time, well-formed QTM $`M`$ with $`\stackrel{~}{}`$-amplitudes satisfying that, for all $`x`$, $`f(x)`$ is equal to the supremum, over all qustring $`|\varphi `$ of size $`p(|x|)`$, of the probability that $`M`$ accepts $`(|x,|\varphi )`$. The class $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ naturally includes $`\mathrm{𝐎𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$.

Observation: The size factor $`p`$ of a quantum index $`|\varphi `$ in Definition 4.1 can be replaced by any polynomial $`q`$ that majorizes $`p`$. This is shown easily by ignoring the extra $`q(|x|)p(|x|)`$ qubits on input $`x`$ because those qubits that are not accessed by a QTM do not affect the acceptance probability of the QTM.

Solving a quantum optimization problem is closely related to finding the maximal eigenvalue of a certain type of positive semidefinite, contractive, Hermitian matrix. In what follows, we clarify this relationship. Assume that we have a multi-tape well-formed QTM witnessing a quantum optimization problem $`f`$. Let $`p`$ be a polynomial expressing the size of a quantum index. Without loss of generality, we can assume that $`M`$ is stationary in normal form . As shown in , there exists a reversing QTM for $`M`$, denoted $`M^{}`$. We then introduce the new QTM, called $`N_{M,p}`$, that behaves as follows:

> On input $`(x,t)`$ given in the input tape, if $`|t|p(|x|)`$ then skip the following procedure and halt. Let $`n=|x|`$ and assume that $`t\mathrm{\Sigma }^{p(n)}`$. Copy $`x`$ onto a new tape, called the storage tape. Run $`M`$ on input $`(x,t)`$. When it halts in polynomial time, copy $`M`$’s output bit (either $`|0`$ or $`|1`$) onto another new tape, called the result tape. Run the reversing machine $`M^{}`$ on the final configuration excluding the storage tape and the result tape. After $`M^{}`$ halts in polynomial time, if $`N_{M,p}`$’s configuration consists only of $`(x,s)`$ in the input tape, where $`s`$ is a certain string of length $`p(|x|)`$, of $`x`$ in the storage tape, of $`1`$ in the result tape (and empty elsewhere), then move $`(x,s)`$ into the output tape and empty all the other tapes and halt. Otherwise, write the blank symbol in the output tape and halts.

By an appropriate implementation, we can make all the computation paths of $`N_{M,p}`$ on each input terminate simultaneously. Now, fix $`x`$ and let $`n=|x|`$. For each pair $`(s,t)\mathrm{\Sigma }^{p(n)}\times \mathrm{\Sigma }^{p(n)}`$, define $`\alpha _{x,s,t}`$ to be the amplitude of a unique final configuration in which, starting with input $`(x,t)`$, $`N_{M,p}`$ outputs $`(x,s)`$ in a unique final inner state. Let $`P_{M,p,x}`$ be the $`2^{p(n)}\times 2^{p(n)}`$ matrix $`(\alpha _{x,s,t})_{s,t\mathrm{\Sigma }^{p(n)}}`$. It is not difficult to show by the definition of $`N_{M,p}`$ that $`P_{M,p,x}`$ is Hermitian, positive semidefinite, and contractive. Thus, each $`\alpha _{x,s,t}`$ is a real number and $`\alpha _{x,s,t}=\alpha _{x,t,s}`$ for all pairs $`(s,t)\mathrm{\Sigma }^{p(n)}\times \mathrm{\Sigma }^{p(n)}`$. Note that the acceptance probability of $`M`$ on input $`(x,|\varphi )`$ is exactly $`|\varphi |P_{M,p,x}|\varphi |`$. Thus,

$`f(x)`$ $`=`$ $`sup\{|\varphi |P_{M,p,x}|\varphi |\text{ }|\varphi \text{ is any qustring of size }p(n)\text{ }\}`$
$`=`$ $`P_{M,p,x},`$
which coincides with the maximal eigenvalue $`\lambda `$ of $`P_{M,p,x}`$ (see, e.g., ). A similar construction has been shown in the literature .

In a quantum setting, “squaring” becomes a unique operation because of the reversibility nature of quantum computation. For example, as shown in , $`f\mathrm{𝐆𝐚𝐩𝐐𝐏}`$ implies $`f^2\mathrm{\#}\mathrm{𝐐𝐏}`$. In the next lemma, we show that squaring does not increase the size of a quantum index.

###### Lemma 4.2

Let $`p`$ be any polynomial, $`g`$ any function in $`\mathrm{\#}\mathrm{𝐐𝐏}`$, and $`f`$ any function in $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$. Assume that $`f(x)=sup\{g(x,|\varphi )\text{ }|\varphi \text{ is any qustring of size }p(|x|)\text{ }\}`$ for all $`x`$. Then, there exists a function $`h`$ in $`\mathrm{\#}\mathrm{𝐐𝐏}`$ such that $`f^2(x)=sup\{h(x,|\varphi )\text{ }|\varphi \text{ is any qustring of size }p(|x|)\text{ }\}`$ for all $`x`$.

###### Proof.

Since $`g\mathrm{\#}\mathrm{𝐐𝐏}`$, let $`M`$ be a multi-tape, $`\stackrel{~}{}`$-amplitude, stationary, well-formed QTM $`M`$ in normal form that witnesses $`g`$. By the aforementioned argument, $`f(x)`$ equals $`P_{M,p,x}`$. Since $`P_{M,p}`$ is Hermitian, $`f^2(x)=P_{M,p,x}^2=P_{M,p}^2`$. We slightly modify the QTM $`N_{M,p}`$ and define the new QTM, called $`N`$, in the following fashion:

> On input $`(x,t)`$, if $`|t|p(|x|)`$ then reject the input. Let $`n=|x|`$ and assume that $`t\mathrm{\Sigma }^{p(n)}`$. Run $`N_{M,p}`$ on input $`(x,t)`$. If $`N_{M,p}`$ outputs $`(x,s)`$ for a certain string $`s`$ of length $`p(|x|)`$, then accept the input. Otherwise, reject the input.

For the desired $`h`$, define $`h(x,t)`$ to be the acceptance probability of $`N`$ on input $`(x,t)`$. Note that $`N_{M,p}`$ accepts input $`(x,|\varphi )`$ with probability exactly $`|\varphi |P_{M,p,x}^{}P_{M,p,x}|\varphi |`$, which equals $`|\varphi |P_{M,p,x}^2|\varphi |`$. Hence,

$`P_{M,p,x}^2`$ $`=`$ $`sup\{|\varphi |P_{M,p,x}^2|\varphi |\text{ }|\varphi \text{ is any qustring of size }p(|x|)\text{ }\}`$
$`=`$ $`sup\{h(x,|\varphi )\text{ }|\varphi \text{ is any qustring of size }p(|x|)\text{ }\}.`$
Since $`f^2(x)=P_{M,p,x}^2`$, we obtain the desired equation. ∎

## 5 Fundamental Properties of Qopt#QP

We examine the fundamental properties of quantum optimization problems in $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$. In what follows, we show that $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ enjoys important closure properties, such as multiplication, exponentiation, limited addition, and limited composition.

Firstly, we show that $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ is closed under composition with $`\mathrm{𝐅𝐏}`$-functions. To be more precise, for any two function classes $``$ and $`𝒢`$, let $`𝒢`$ denote the class of functions $`fg`$, where $`f`$ and $`g𝒢`$ and $`fg`$ is the composition defined as $`fg(x)=f(g(x))`$ for all $`x`$ in the domain of $`g`$. Using this notation, our claim is expressed as follows. The proof of the claim is immediate.

###### Lemma 5.1

$`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}\mathrm{𝐅𝐏}=\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$.

In the previous section, we have shown that solving a quantum optimization problem is equivalent to finding the maximal eigenvalue of a certain positive semidefinite, contract, Hermitian matrix. We use this characterization to show the fundamental properties of quantum optimization problems. To describe the claim, we need the notion of an $`\mathrm{}`$-qubit source.

A qubit ensemble is a sequence of qustrings with index set $`I`$. A qubit ensemble $`\{|\varphi _x\}_{xI}`$ is called an $`\mathrm{}`$-qubit source if each $`|\varphi _x`$ is a qustring of size $`\mathrm{}(|x|)`$ and there exists a polynomial-time, $`\stackrel{~}{}`$-amplitude, well-formed, clean QTM that generates $`|\varphi _x`$ on input $`x`$, where a QTM is called clean if it is stationary in normal form and all the tapes except the output tape are empty when it halts with one distinguished final state.

###### Lemma 5.2

Let $`q`$ be a polynomial. Let $`\mathrm{}`$ be any function in $`^{}`$ such that $`\mathrm{}(n)O(\mathrm{log}n)`$ and let $`\{|\varphi _x\}_{x\mathrm{\Sigma }^{}}`$ be any $`\mathrm{}`$-qubit source. Assume that $`f`$ is a function in $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$. The following functions all belong to $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$.

1. $`g(x)=\mathrm{max}\{f(x,y)y\mathrm{\Sigma }^{q(|x|)}\}`$.
2. $`g(x)=_{y:|y|=\mathrm{}(|x|)}|y|\varphi _x|^2f(x,y)`$.
3. $`g(x)=_{y:|y|=\mathrm{}(|x|)}f(x,y)`$.
4. $`g(x,y)=f(x)^{|y|}`$.

###### Proof.

1) Take a polynomial $`p`$ and a function $`h\mathrm{\#}\mathrm{𝐐𝐏}`$ such that $`f(x,y)=sup\{h(x,y,|\varphi )\text{ }|\varphi \text{ is any qustring of size }p(|x|)\text{ }\}`$ for any strings $`x`$ and $`y\mathrm{\Sigma }^{q(|x|)}`$. Since $`h\mathrm{\#}\mathrm{𝐐𝐏}`$, there exists an appropriate QTM $`M`$ that witnesses $`h`$. For simplicity, assume that there exists a polynomial $`r`$ such that $`|x,y|=r(|x|)`$ for all $`y\mathrm{\Sigma }^{q(|x|)}`$.

Define the new QTM $`N`$ as follow. Let $`(x,|\psi )`$ be any quantum input, where $`n=|x|`$ and $`|\psi `$ is any qustring of size $`q(n)+p(n)`$. Note that $`|\psi `$ is written in the form $`_{y:|y|=q(n)}\beta _y|y|\varphi _y`$ for a certain series of qustrings $`\{|\varphi _y\}_{y\mathrm{\Sigma }^{q(n)}}`$ and a certain series of complex numbers $`\{\beta _y\}_{y\mathrm{\Sigma }^{q(n)}}`$ satisfying $`_{y:|y|=q(n)}|\beta _y|^2=1`$.

> First, observe the first $`q(n)`$ qubits (i.e., $`|y`$) of the tape content $`|\psi `$ and copy the result onto a new tape to remember it. After the observation, we obtain $`y`$ and a quantum state $`\beta _y|\varphi _y`$. Then, simulate $`M`$ on inputs $`(x,y)`$ and $`\beta _y|\varphi _y`$.

Let $`k(x,|\psi )`$ denote the acceptance probability of $`N`$ on input $`(x,|\psi )`$. Obviously, $`k(x,|\psi )=_{y:|y|=q(n)}|\beta _y|^2h(x,y,|\varphi _y)`$.

Consider the supremum $`sup_{|\psi }\{k(x,|\psi )\}`$, where $`|\psi `$ runs over all qustrings of size $`q(n)+p(n)`$. By a simple calculation, $`sup_{|\psi }\{k(x,|\psi )\}=sup_{\{\beta _y\}_y,|\varphi _y}\{_{y:|y|=q(n)}|\beta _y|^2h(x,y,|\varphi _y)\}`$, which is equal to $`sup_{\{\beta _y\}_y}\{_{y:|y|=q(n)}|\beta _y|^2f(x,y)\}`$, where $`\{\beta _y\}_{y\mathrm{\Sigma }^{q(|x|)}}`$ runs over all sequences of complex numbers with $`_{y:|y|=q(|x|)}|\beta _y|^2=1`$ and each $`|\varphi _y`$ runs all qustrings of size $`q(n)`$. By the property of convex combination with $`_{y:|y|=q(n)}|\beta _y|^2=1`$, the value $`sup_{\{\beta _y\}_y}\{_{y:|y|=q(n)}|\beta _y|^2f(x,y)\}`$ equals $`\mathrm{max}\{f(x,y)y\mathrm{\Sigma }^{q(n)}\}`$. Therefore, $`N`$ witnesses $`g`$.

2) For simplicity, we assume the existence of a polynomial $`r`$ such that $`2^{\mathrm{}(n)}r(n)`$ for all $`n`$. Without loss of generality, we can assume that there exist a polynomial $`p`$ and a function $`h\mathrm{\#}\mathrm{𝐐𝐏}`$ which, for any strings $`x`$ and $`y\mathrm{\Sigma }^{\mathrm{}(|x|)}`$, force $`sup\{h(x,y,|\varphi )\text{ }|\varphi \text{ is any qustring of size }p(|x|)\text{ }\}`$ to be $`f(x,y)`$. Let $`M`$ be an appropriate QTM $`M`$ that witnesses $`h`$.

Consider the following QTM $`N`$. Let $`x`$ (say, $`n=|x|`$) be any input string and $`|\psi `$ any input qustring of size $`r(n)p(n)`$. We section $`|\psi `$ into $`r(n)`$ blocks of equal size $`p(n)`$. The first $`2^{\mathrm{}(n)}`$ blocks are assumed to be indexed with strings of length $`\mathrm{}(n)`$.

> Generate qustring $`|\varphi _x`$ in a new tape and then observe the tape content. Let $`y`$ be the result after the observation. Now, copy $`y`$ onto a new tape and then simulate $`M`$ on input $`(x,y)`$ as well as the content of the $`y`$th block of $`|\psi `$.

For each $`y`$, let $`|\psi _y`$ be any qustring of size $`p(n)`$ that achieves the maximal acceptance probability of $`M`$ on input $`(x,y,|\psi _y)`$; that is $`f(x,y)=h(x,y,|\psi _y)`$. Note that, for any qustring $`|\psi `$ of size at least $`p(n)`$, the acceptance probability of $`M`$ on input $`(x,y)`$ accessing only the first $`p(n)`$ qubits of $`|\psi `$ cannot be more than $`f(x,y)`$. Hence, to maximize the acceptance probability of $`N`$, $`|\psi `$ must be the tensor product $`(_{y:|y|=\mathrm{}(n)}|\psi _y)|\xi `$, where $`|\xi `$ is any qustring of size $`(r(n)2^{\mathrm{}(n)})p(n)`$. In this case, the acceptance probability of $`N`$ on input $`(x,|\psi )`$, after $`y`$ is observed, is $`|y|\varphi _x|^2h(x,y,|\psi _y)`$. Note that any two simulations on different $`y`$’s do not interfere each other. Hence, $`N`$ witnesses $`g`$.

3) Following 2), we assume that $`2^{\mathrm{}(n)}r(n)`$ for all $`n`$ and $`f(x,y)=sup\{h(x,y,|\varphi )\text{ }|\varphi \text{ is any qustring of size }p(|x|)\text{ }\}`$ for any strings $`x`$ and $`y\mathrm{\Sigma }^{\mathrm{}(|x|)}`$. This $`h`$ is witnessed by a QTM $`M`$. The new QTM $`N`$ works as follows. Let $`x`$ be any string of length $`n`$ and $`|\psi `$ any qustring of size $`r(n)p(n)`$. We use the same sectioning of $`|\psi `$ as in 2).

> Set $`y=0^{\mathrm{}(n)}`$ initially. By incrementing $`y`$ lexicographically until $`1^{\mathrm{}(n)}`$, simulate recursively $`M`$ on inputs $`x,y`$ together with the content of the $`y`$th block of $`|\psi `$. Before each simulation, copy the value $`y`$ onto a separate tape to make each round of simulation independent. If $`M`$ reaches a rejecting configuration at a certain round, then reject the input. Otherwise, accept the input.

Similar to 2), when $`|\psi `$ is the tensor product of the form $`(_{y:|y|=\mathrm{}(n)}|\psi _y)|\xi `$, we can achieve the maximal acceptance probability of $`N`$ on input $`(x,|\psi )`$. Thus, $`N`$ witnesses $`g`$.

4) This is basically an extension of the proof of Lemma 4.2. Since $`f\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$, let $`p`$ be a polynomial and $`M`$ be a QTM that witnesses $`f`$. Let $`N_{M,p}`$ be the QTM induced from $`M`$ as described in Section 4. For our proof, we slightly modify $`N_{M,p}`$ in such way that, instead of moving $`(x,s)`$ from the input tape to the output tape, it keeps $`(x,s)`$ in the input tape and erases only the storage-tape content (keeping 1 in the result tape).

Now, consider the following QTM $`P`$. Let $`x`$ be any input string of length $`n`$ and $`y`$ be any string of length $`m`$. Let $`m=2k+j`$, where $`k`$ and $`j\{0,1\}`$. We prepare a new tape, called the checking tape.

> On input $`(x,y,|\psi )`$ given in tape 1, repeat the following procedure (\*) by incrementing $`i`$ by one from $`1`$ to $`k`$. For convenience, we call the initial configuration round 0.
>
> (\*) At round $`i`$, $`P`$ simulate $`N_{M,p}`$ starting with the configuration left from the previous round, and when it halts, move the one-bit content of the result tape into the $`i`$th cell of the checking tape.
>
> After this procedure, when $`j=1`$, we make one additional round: simulate $`M`$ starting with the configuration left from the previous round and, when it halts, write the outcome (either $`0`$ or $`1`$) into the $`k+j`$th cell of the checking tape. Finally, observe the checking tape and accept the input iff the $`k+j`$ cells consists only of $`1`$s.

Let $`|\psi _x`$ be any quantum index that maximizes the acceptance probability of $`M`$ on input $`(x,|\psi _x)`$. From the proof of Lemma 4.2, $`N_{M,p}`$ accepts $`(x,|\varphi _x)`$ with probability $`f^2(x)`$. More generally, we can show by induction that, after each round $`i`$, if we observe the checking tape with observable $`|1^i`$ then we obtain the quantum state $`f^{2i}(x)|x|\varphi _x`$ in the input tape. In case where $`j=1`$, the additional round contributes to a multiplicative factor of $`f(x)`$. Therefore, $`P`$ accepts $`(x,|\psi _x)`$ with probability exactly $`f^{2k+j}(x)`$, which is $`f^m(x)`$.

It is also important to note that the size of quantum index is independent of $`y`$. ∎

The class $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ is shown to be robust in the following sense.

###### Proposition 5.3

$`\mathrm{𝐐𝐨𝐩𝐭}(\mathrm{𝐎𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏})=\mathrm{𝐎𝐩𝐭}(\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏})=\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$.

As for the definition of $`\mathrm{𝐐𝐨𝐩𝐭}(\mathrm{𝐎𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏})`$, it is important to note that, by our convention of quantum extension, $`f`$ is in $`\mathrm{𝐐𝐨𝐩𝐭}(\mathrm{𝐎𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏})`$ iff there exists a function $`h\mathrm{\#}\mathrm{𝐐𝐏}`$ such that, for every $`x`$, $`f(x)=sup_{|\varphi }\mathrm{max}_s\{h(x,|\varphi ,s)\}`$, where $`|\varphi `$ runs over all qustrings of polynomial size and $`s`$ runs over all strings of polynomial length.

Proof of Proposition 5.3.  It follows from $`\mathrm{\#}\mathrm{𝐐𝐏}\mathrm{𝐎𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ that $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}\mathrm{𝐐𝐨𝐩𝐭}(\mathrm{𝐎𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏})`$. We then show that $`\mathrm{𝐐𝐨𝐩𝐭}(\mathrm{𝐎𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏})\mathrm{𝐎𝐩𝐭}(\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏})`$. This follows from the fact that we can swap the “max” operator and the “sup” operator. The inclusion $`\mathrm{𝐎𝐩𝐭}(\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏})\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ follows from Lemma 5.2(1). $`\mathrm{}`$

Proposition 5.3 seems unlikely to be extended to $`\mathrm{𝐐𝐨𝐩𝐭}(\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏})=\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ because of the inability to distinguish a tensor product of two short quantum indices from one large quantum index. We conjecture that $`\mathrm{𝐐𝐨𝐩𝐭}(\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏})\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$.

This also suggests a generalization of $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ into $`\mathrm{𝐐𝐨𝐩𝐭}_k\mathrm{\#}\mathrm{𝐐𝐏}`$ for each $`k^+`$ by taking a tensor product of $`k`$ quantum indices: a function $`f`$ is in $`\mathrm{𝐐𝐨𝐩𝐭}_k\mathrm{\#}\mathrm{𝐐𝐏}`$ if there exists a polynomial $`p`$ and a function $`g\mathrm{\#}\mathrm{𝐐𝐏}`$ such that, for every $`x`$, $`f(x)=sup\{g(x,|\varphi _1|\varphi _2\mathrm{}|\varphi _k)\}`$, where the supremum is over all $`k`$-tuples $`(|\varphi _1,|\varphi _2,\mathrm{},|\varphi _k)`$ of strings of size $`p(|x|)`$. With this notation, we can show that $`\mathrm{𝐐𝐨𝐩𝐭}(\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏})=\mathrm{𝐐𝐨𝐩𝐭}_2\mathrm{\#}\mathrm{𝐐𝐏}`$.

## 6 Approximate Reduction and Universality

Based upon his metric reducibility between NP optimization problems, Krentel  introduced the notion of complete problems for $`\mathrm{𝐎𝐩𝐭𝐏}`$. There are also many other reductions used for NP optimization problems in the literature. Krentel’s complete problems constitute the hardest problems in $`\mathrm{𝐎𝐩𝐭𝐏}`$. It is natural to consider a similar notion among quantum optimization problems. However, problems in $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ are functions computed by well-formed $`\stackrel{~}{}`$-amplitude QTMs and thus, there is no single QTM that exactly simulates all the other well-formed QTMs with $`\stackrel{~}{}`$-amplitudes. Instead, we relax the meaning of “completeness”.

Following Deutsch’s work , Bernstein and Vazirani  constructed a universal QTM that can approximately simulate any well-formed QTM $`M`$ for $`t`$ steps with desired accuracy $`ϵ`$ at the cost of polynomial slowdown. In other words, every QTM can be “approximately” reduced to one single QTM. We can generalize this notion of universality in the following fashion.

###### Definition 6.1

1) Let $`f`$ and $`g`$ be any functions from $`\{0,1\}^{}`$ to $`[0,1]`$. The function $`f`$ is (polynomial-time) approximately reducible to $`g`$, denoted $`f^pg`$, if there is a function $`k\mathrm{𝐅𝐏}`$ such that, for every $`x`$ and $`m^+`$, $`|f(x)g(k(x01^m))|1/m`$.

2) Let $``$ be any class of functions from $`\{0,1\}^{}`$ to $`[0,1]`$. A function $`g`$ from $`\mathrm{\Sigma }^{}`$ to $`[0,1]`$ is universal for $``$ (or $``$-universal, in short) if (i) $`g`$ is in $``$ and (ii) every function $`f`$ is approximately reducible to $`g`$.

Unfortunately, we may not replace the term $`1/m`$ in the above definition by $`2^m`$. This relation $`^p`$ is reflexive and transitive. The proof is immediate from the definition.

###### Lemma 6.2

The relation $`^p`$ satisfies that (i) for any $`f`$, $`f^pf`$ and (ii) for any $`f`$, $`g`$, and $`h`$, if $`f^pg`$ and $`g^ph`$, then $`f^ph`$.

The importance of a universal function is given as in Lemma 6.4. Before describing the lemma, we introduce useful notations for “approximate membership” and “approximate inclusion.”

###### Definition 6.3

Let $``$ and $`𝒢`$ be any two classes of functions from $`\mathrm{\Sigma }^{}`$ to the unit real interval $`[0,1]`$ and let $`f`$ be any function from $`\mathrm{\Sigma }^{}`$ to $`[0,1]`$. The notation $`f\stackrel{}{}{}_{}{}^{p}`$ means that, for every polynomial $`p`$, there exists a function $`g`$ in $``$ satisfying $`|f(x)g(x)|1/p(|x|)`$ for all $`x`$. The notation $`^p𝒢`$ means that $`f\stackrel{}{}{}_{}{}^{p}𝒢`$ for any function $`f`$ in $``$.

###### Lemma 6.4

Let $``$ and $`𝒢`$ be any two classes of functions from $`\mathrm{\Sigma }^{}`$ to $`[0,1]`$. Assume that $`𝒢\mathrm{𝐅𝐏}𝒢`$ and let $`f`$ be any $``$-universal function. Then, $`^p𝒢`$ iff $`f\stackrel{}{}{}_{}{}^{p}𝒢`$.

###### Proof.

(Only If - part) This is trivial since $`f`$. (If -part) Assume that $`f\stackrel{}{}{}_{}{}^{p}𝒢`$. Take any function $`g`$ in $``$ and any polynomial $`p`$. Since $`f`$ is $``$-universal, $`g^pf`$. There exists a function $`k\mathrm{𝐅𝐏}`$ such that $`|g(x)f(k(x01^{2p(|x|)}))|1/2p(|x|)`$ for all $`x`$. Moreover, since $`f\stackrel{}{}{}_{}{}^{p}𝒢`$, there exists a function $`r𝒢`$ such that $`|f(k(x01^{2p(|x|)}))r(k(x01^{2p(|x|)}))|1/2p(|x|)`$. Define $`f^{}(x)=f(k(x01^{2p(|x|)}))`$ and $`r^{}(x)=r(k(x01^{2p(|x|)}))`$. Clearly, $`r^{}`$ is in $`𝒢\mathrm{𝐅𝐏}𝒢`$. Thus, $`g\stackrel{}{}{}_{}{}^{p}𝒢`$ since $`|g(x)r^{}(x)||g(x)f^{}(x)|+|f^{}(x)r^{}(x)|1/p(|x|)`$. This implies that $`^p𝒢`$. ∎

Most natural classes satisfy the premise of Lemma 6.4. For example, $`\mathrm{\#}\mathrm{𝐐𝐏}`$, $`\mathrm{𝐆𝐚𝐩𝐐𝐏}`$, $`\mathrm{𝐎𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$, and $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ satisfy the premise.

Most well-known quantum complexity classes are believed to lack complete problems. The notion of universality naturally provides promise complete problems for, e.g., $`\mathrm{𝐁𝐐𝐏}`$ by posing appropriate restrictions on the acceptance probabilities of quantum functions in $`\mathrm{\#}\mathrm{𝐐𝐏}`$.

The notion of a universal QTM given by Bernstein and Vazirani  gives rise to the $`\mathrm{\#}\mathrm{𝐐𝐏}`$-universal function QAP. We assume each DTM has its code (or its description) expressed in binary. A code of an amplitude $`\alpha `$ in $`\stackrel{~}{}`$ is a code of a DTM that approximates $`\alpha `$ to within $`2^n`$ in time polynomial in $`n`$. A code of a QTM means the description of the machine with codes of all amplitudes used for the QTM. We assume that any code is expressed in binary.

We fix the universal QTM $`M_U`$ that, on input $`M,x,1^t,1^m`$, simulates $`M`$ on input $`x`$ for $`t`$ steps and halts in a final configuration $`|\varphi _{M_U}`$ satisfying that $`|\varphi _{M_U}|\varphi _M1/m`$, where $`|\varphi _M`$ is the configuration of $`M`$ on $`x`$ after $`t`$ steps . For completeness, we assume that if $`M`$ is not a well-formed QTM then $`M_U`$ rejects the input with probability $`1`$. From the construction of a universal QTM in , we can assume that $`M_U`$ has $`\{0,\pm 1,\pm \mathrm{cos}\theta ,\pm \mathrm{cos}\theta ,\pm e^{i\theta }\}`$-amplitudes, where $`\theta =2\pi _{i=1}^{\mathrm{}}2^{2^i}`$. Adleman et al.  further simplified the above set of amplitudes; for example, we can replace $`\mathrm{cos}\theta `$ and $`\mathrm{sin}\theta `$ by $`3/5`$ and $`4/5`$, respectively.

We then define the Qtm Approximation Problem (QAP) as follows:

Qtm Approximation Problem: QAP

* input: $`M,x,1^t,1^m`$, where $`M`$ is a $`\stackrel{~}{}`$-amplitudes well-formed QTM, $`t`$, and $`m^+`$.
* output: the acceptance probability of $`M_U`$ on input $`M,x,1^t,1^m`$.

As Bernstein and Vazirani  demonstrated, every function $`f`$ outputting the acceptance probability of a certain polynomial-time well-formed QTM with $`\stackrel{~}{}`$-amplitudes is approximately reducible to QAP. It is easy to see that QAP is in $`\mathrm{\#}\mathrm{𝐐𝐏}`$. We have the following proposition.

###### Proposition 6.5

QAP is $`\mathrm{\#}\mathrm{𝐐𝐏}`$-universal.

The proof of Proposition 6.5 uses the following folklore lemma. Although the proof of the lemma is easy, it is given in Appendix for completeness.

###### Lemma 6.6

Let $`M`$ and $`N`$ be two well-formed QTMs. Let $`U_M`$ and $`U_N`$ be the superpositions of final configurations of $`M`$ on input $`|\varphi `$ and of $`N`$ on input $`|\psi `$, respectively. Let $`\eta _M(|\varphi )`$ and $`\eta _N(|\psi )`$ be the acceptance probabilities of $`M`$ on input $`|\varphi `$ and of $`N`$ on input $`|\psi `$, respectively. Then, $`|\eta _M(|\varphi )\eta _N(|\psi )|U_M|\varphi U_N|\psi `$.

Now, we give the proof of Proposition 6.5.

Proof of Proposition 6.5.  Let $`p`$ be any polynomial and let $`g`$ be any function in $`\mathrm{\#}\mathrm{𝐐𝐏}`$. Let $`M`$ be a polynomial-time $`\stackrel{~}{}`$-amplitude well-formed QTM that witnesses $`g`$ with quantum index size $`p`$. Let $`q`$ be a polynomial that bounds the running time of $`M`$. We show that $`g^p\mathrm{QAP}`$.

Fix $`x`$ and $`m`$ arbitrarily. Let $`|\varphi _{M_U}`$ be the final configuration of $`M_U`$ on input $`M,x,1^{q(|x|)},1^m`$ and define $`|\varphi _M`$ to be the final configuration of $`M`$ on input $`x`$. We set $`k(x01^m)=M,x,1^{q(|x|)},1^m`$. It follows from the definition of $`M_U`$ that $`|\varphi _{M_U}|\varphi _M1/m`$. Thus, Lemma 6.6 implies that $`|\mathrm{QAP}(M,x,1^t,1^m)g(x)||\varphi _{M_U}|\varphi _M1/m`$. Therefore, we obtain

$$|\mathrm{QAP}(k(x01^m))g(x)|=|\mathrm{QAP}(M,x,1^t,1^m)g(x)|\frac{1}{m}.$$

This guarantees $`g^p\mathrm{QAP}`$. $`\mathrm{}`$

We exhibit a canonical universal problem for $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$. To avoid any notational inconvenience, we write $`\mathrm{QAP}(M,x,1^t,1^m,s)`$ when $`M`$ takes an input $`x,s`$. Based on this convention, we define the Maximum Qtm Problem (MAXQTM) as follows.

Maximum Qtm Problem: MAXQTM

* input: $`M,x,1^t,1^m`$, where $`M`$ is a $`\stackrel{~}{}`$-amplitudes well-formed QTM, $`t`$, and $`m^+`$.
* output: the maximal acceptance probability, over all quantum indices $`|\varphi `$ of size $`|x|`$, of $`M_U`$ on input $`(M,x,1^t,1^m,|\varphi )`$.

Obviously, MAXQTM belongs to $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$. We further claim that MAXQTM is indeed universal for $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$.

###### Theorem 6.7

MAXQTM is $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$-universal.

###### Proof.

To see this, let $`f`$ be any function in $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$. There exist a polynomial $`p`$ and a function $`g\mathrm{\#}\mathrm{𝐐𝐏}`$ such that $`f(x)=sup\{g(x,|\varphi )\text{ }|\varphi \text{ is any qustring of size }p(|x|)\text{ }\}`$ for every $`x`$. Without loss of generality, assume that $`p(n)>n+1`$ for all $`n`$. Take an appropriate QTM $`M_g`$ that witnesses $`g`$. We show that $`f^p\mathrm{MAXQTM}`$. Define another QTM $`M_g^{}`$ as follows: on input $`z`$ and $`s\mathrm{\Sigma }^{|z|}`$, if $`z`$ is not of the form $`x01^{p(|x|)|x|1}`$, then reject the input. Otherwise, simulate $`M_g`$ on input $`(x,s)`$.

Let $`q`$ be any polynomial such that, for every $`x`$, $`M_g^{}`$ on input $`x01^{p(|x|)|x|1}`$ halts in at most $`q(|x|)`$ steps. Thus, Proposition 6.5 implies that, for every $`s\mathrm{\Sigma }^{p(|x|)}`$,

$$|\mathrm{QAP}(M_g^{},x01^{p(|x|)|x|1},1^{q(|x|)},1^m,s)g(x,s)|\frac{1}{m}.$$

This clearly yields the following inequality:

$$|\underset{|\varphi }{sup}\{\mathrm{QAP}(M_g^{},x01^{p(|x|)|x|1},1^{q(|x|)},1^m,|\varphi )\}\underset{|\varphi }{sup}\{g(x,|\varphi )\}|\frac{1}{m},$$

where $`|\varphi `$ runs over all qustrings of size $`p(|x|)`$. To complete the proof, it suffices to define $`k(x01^m)=M_g^{},x01^{p(|x|)|x|1},1^{q(|x|)},1^m`$ for all $`x`$ and $`m`$. ∎

###### Corollary 6.8

$`\mathrm{MAXQTM}\stackrel{}{}{}_{}{}^{p}\mathrm{\#}\mathrm{𝐐𝐏}`$ iff $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}^p\mathrm{\#}\mathrm{𝐐𝐏}`$.

We have just shown an example of universal optimization problem, MAXQTM, for $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$. Nonetheless, MAXQTM heavily relies on a universal QTM and it seems artificial. To develop a fruitful theory of quantum optimization problems, we need “natural” examples of universal problems in a variety of fields, such as graph theory, logic, and group theory. Finding such natural problems is one of the most pressing open problems in our theory.

## 7 Relationship between Qopt#QP and #QP

The quantum optimization problems $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ are induced from $`\mathrm{\#}\mathrm{𝐐𝐏}`$-functions by taking quantum indices. However, there has been shown few relationship between $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ and $`\mathrm{\#}\mathrm{𝐐𝐏}`$ except for the trivial inclusion $`\mathrm{\#}\mathrm{𝐐𝐏}\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$. To fill in the gap between them, we begin with a simple observation using Lemma 5.2(4) (see also ).

###### Proposition 7.1

For any function $`h`$ in $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$, there exists a function $`g\mathrm{\#}\mathrm{𝐐𝐏}`$ and a polynomial $`p`$ such that, for all strings $`x`$ and integers $`m>0`$,

$$g(x01^m)h^m(x)2^{p(|x|)}g(x01^m).$$

###### Proof.

Let $`h`$ be any function in $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$. Let $`h^{}(x,y)=h(x)^{|y|}`$. By Lemma 5.2(4), $`h^{}`$ belongs to $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$. The key idea comes from the fact that, in the proof of Lemma 5.2(4), we can assume that, for a certain fixed polynomial $`p`$ and a function $`f\mathrm{\#}\mathrm{𝐐𝐏}`$, $`h^{}(x,y)=sup\{f(x,y,|\varphi )\text{ }|\varphi \text{ is a qustring of size }p(|x|)\text{ }\}`$ for all $`x`$ and $`y`$. Notice that the size of $`|\varphi `$ is independent of $`y`$.

The rest of the proof is to estimate $`h^{}(x,y)`$. Define $`g(x01^m)=2^{p(|x|)}_{s:|s|=p(|x|)}f(x,1^m,s)`$ for all $`x`$ and $`m`$. Obviously, $`g\mathrm{\#}\mathrm{𝐐𝐏}`$. By the maximality of $`h^{}`$, $`f(x,1^m,s)h^{}(x,1^m)`$ for every $`s\mathrm{\Sigma }^{p(|x|)}`$. Since the value $`2^{p(|x|)}_{s:|s|=p(|x|)}f(x,1^m,s)`$ is the average of all $`f(x,1^m,s)`$, we have $`2^{p(|x|)}_{s:|s|=p(|x|)}f(x,1^m,s)h^{}(x,1^m)`$, which implies $`g(x01^m)h^{}(x,1^m)`$. On the other hand, $`h^{}(x,1^m)_{s:|s|=p(|x|)}f(x,1^m,s)`$, which implies $`h^{}(x,1^m)2^{p(|x|)}g(x01^m)`$. ∎

Although Proposition 7.1 is a rough approximation, it is used as a tool in Section 8.

We further explore a relationship between $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ and $`\mathrm{\#}\mathrm{𝐐𝐏}`$. In the previous section, we have introduced the notations $`\stackrel{}{}^p`$ and $`^p`$ in connection to universal problems. These notations are used to indicate a certain notion of “closeness” (that is, bounded by reciprocal of a polynomial). In this section, we need a much tighter notion of “closeness.”

###### Definition 7.2

Let $``$ and $`𝒢`$ be any two classes of functions. For any function $`f`$, we write $`f\stackrel{}{}{}_{}{}^{e}`$ if, for every polynomial $`p`$, there exists a function $`g`$ such that, for every $`x`$, $`|f(x)g(x)|2^{p(|x|)}`$. The notation $`^e𝒢`$ means that $`f\stackrel{}{}{}_{}{}^{e}𝒢`$ for all functions $`f`$ in $``$.

In Proposition 7.4, we show that any quantum optimization problem in $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ can be closely approximated by $`\mathrm{\#}\mathrm{𝐐𝐏}`$-functions with the help of certain oracles. For this purpose, we define the new class, called $`\mathrm{𝐐𝐎𝐏}`$. The following definition resembles the $`\mathrm{\#}\mathrm{𝐐𝐏}`$-characterization of $`\mathrm{𝐏𝐏}`$ sets in Lemma 3.4.

###### Definition 7.3

A set $`A`$ is in $`\mathrm{𝐐𝐎𝐏}`$ (“quantum optimization polynomial time”) if there exist two functions $`f,g\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ and a function $`h\mathrm{𝐅𝐏}`$ such that, for every $`x`$, $`xA`$ exactly when $`2^{|h(x)|}f(x)>2^{|h(x)|}g(x)`$. This $`h`$ is called a selection function.

Note that, in Definition 7.3, we can replace the value $`|h(x)|`$ by $`p(|x|)`$ for an appropriate polynomial $`p`$. This is seen by taking $`p`$ that satisfies $`|h(x)|p(|x|)`$ for all $`x`$ and by replacing $`f`$ and $`g`$, respectively, with $`\widehat{f}(x)=2^{p(|x|)+|h(x)|}f(x)`$ and $`\widehat{g}(x)=2^{p(|x|)+|h(x)|}g(x)`$. It also follows from Proposition 9.6 that $`\mathrm{𝐏𝐏}\mathrm{𝐐𝐎𝐏}`$.

In the following proposition, we view an $`\mathrm{𝐅𝐏𝐒𝐏𝐀𝐂𝐄}`$-function as a function from $`\mathrm{\Sigma }^{}`$ to $`𝔻`$.

###### Proposition 7.4

$`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}^e\mathrm{\#}\mathrm{𝐐𝐏}^{\mathrm{𝐐𝐎𝐏}}^e\mathrm{𝐅𝐏𝐒𝐏𝐀𝐂𝐄}𝔻^\mathrm{\Sigma }^{}`$.

###### Proof.

Let $`f\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$. Take a function $`g\mathrm{\#}\mathrm{𝐐𝐏}`$ and a polynomial $`q`$ such that $`f(x)=sup\{g(x,|\varphi )\text{ }|\varphi \text{ is any qustring of size }q(|x|)\text{ }\}`$ for every $`x`$. Define the sets $`A_+`$ and $`A_{}`$ as follows: $`A_+=\{(x,y)2^{p(|x|)+1}f(x)num(y)\}`$ and $`A_{}=\{(x,y)2^{p(|x|)+1}f(x)num(y)\}`$, where $`num(y)`$ is the number $`n`$ in $``$ such that $`y`$ is the $`n`$th string in the standard order (the empty string is the $`0`$th string). Let $`A=A_+A_{}`$, where $``$ is the disjoint union. It is not difficult to show that $`A\mathrm{𝐐𝐎𝐏}`$. Let $`p`$ be any polynomial. By a standard binary search algorithm using $`A`$, we can find an approximation of $`f(x)`$ to within $`2^{p(|x|)}`$ in polynomial time. Let $`h^A`$ be the function computed by this algorithm with oracle $`A`$. Then, we have $`|f(x)h^A(x)|2^{p(|x|)}`$.

For the second inclusion, it suffices to show that $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}^e\mathrm{𝐅𝐏𝐒𝐏𝐀𝐂𝐄}𝔻^\mathrm{\Sigma }^{}`$ since this implies $`\mathrm{𝐐𝐎𝐏}\mathrm{𝐏𝐒𝐏𝐀𝐂𝐄}`$ together with the fact that $`\mathrm{\#}\mathrm{𝐐𝐏}^e\mathrm{𝐅𝐏𝐒𝐏𝐀𝐂𝐄}𝔻^\mathrm{\Sigma }^{}`$ (which follows from the result in ). Let $`f`$ be any function in $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$. Let $`M`$ be a QTM that witnesses $`f`$ with a polynomial $`p`$ bounding the quantum index size. Recall the QTM $`N_{M,p}`$ and its associated matrices $`\{P_{M,p,x}\}_{x\mathrm{\Sigma }^{}}`$ given in Section 4 such that, for every $`x`$, (i) $`P_{M,p,x}`$ is a $`2^{p(|x|)}\times 2^{p(|x|)}`$ positive semidefinite, contractive, Hermitian matrix and (ii) $`f(x)=P_{M,p,x}`$. Note that each $`(s,t)`$-entry of $`P_{M,p,x}`$ is approximated to within $`2^m`$ deterministically using space polynomial in $`m`$, $`|x|`$, $`|s|`$, and $`|t|`$ by simulating all computation paths of $`N_{M,p}`$ on input $`(x,t)`$. Consider the characteristic polynomial $`u(z)=\mathrm{det}(zIV_x)`$. This $`u(z)`$ has the form $`u(z)=_{i=0}^{2^{p(|x|)}}a_iz^i`$. It is easy to see that each coefficient $`a_i`$ can be approximated using polynomial space (see also the argument in ). Thus, we can also approximate each real root of $`u(z)`$ using polynomial space. Finally, we find a good approximation of the maximal eigenvalue of $`P_{M,p,x}`$. Thus, $`f\stackrel{}{}{}_{}{}^{p}\mathrm{𝐅𝐏𝐒𝐏𝐀𝐂𝐄}𝔻^\mathrm{\Sigma }^{}`$. ∎

The following is an immediate consequence of Proposition 7.4.

###### Corollary 7.5

If $`\mathrm{𝐄𝐐𝐏}=\mathrm{𝐐𝐎𝐏}`$, then $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}^e\mathrm{\#}\mathrm{𝐐𝐏}`$.

The converse of Corollary 7.5 does not seem to hold. Instead, we show the following weaker form of the converse. For our proposition, let $`\widehat{\mathrm{𝐐𝐎𝐏}}`$ denote the subset of $`\mathrm{𝐐𝐎𝐏}`$ with the extra condition that $`2^{|h(x)|}f(x)2^{|h(x)|}g(x)`$ for all $`x`$ in Definition 7.3.

###### Proposition 7.6

If $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}^e\mathrm{\#}\mathrm{𝐐𝐏}`$, then $`\widehat{\mathrm{𝐐𝐎𝐏}}=\mathrm{𝐏𝐏}`$ and $`\mathrm{𝐐𝐎𝐏}𝐏^{\mathrm{\#}𝐏[1]}`$, where $`[]`$ stands for the number of queries on each input.

###### Proof.

Assume that $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}^e\mathrm{\#}\mathrm{𝐐𝐏}`$. We first show that $`\widehat{\mathrm{𝐐𝐎𝐏}}=\mathrm{𝐏𝐏}`$. Let $`A`$ be any set in $`\widehat{\mathrm{𝐐𝐎𝐏}}`$. There exist a polynomial $`p`$ and functions $`f`$ and $`g`$ in $`\mathrm{𝐎𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ such that, for every $`x`$, (i) if $`xA`$ then $`2^{p(|x|)}f(x)>2^{p(|x|)}g(x)`$ and (ii) if $`xA`$ then $`2^{p(|x|)}f(x)<2^{p(|x|)}g(x)`$. Since $`f\stackrel{}{}{}_{}{}^{p}\mathrm{\#}\mathrm{𝐐𝐏}`$ by our assumption, there exists a certain function $`\widehat{f}`$ in $`\mathrm{\#}\mathrm{𝐐𝐏}`$ such that, for every $`x`$, $`|f(x)\widehat{f}(x)|2^{p(|x|)1}`$, which implies that $`2^{p(|x|)}f(x)=2^{p(|x|)}\widehat{f}(x)`$. Similarly, we obtain $`\widehat{g}`$ from $`g`$. Assume that $`xA`$. Then, we have $`2^{p(|x|)}f(x)>2^{p(|x|)}g(x)`$. This clearly implies $`\widehat{f}(x)>\widehat{g}(x)`$. Similarly, if $`xA`$ then $`\widehat{f}(x)<\widehat{g}(x)`$. Therefore, $`A=\{x\widehat{f}(x)>\widehat{g}(x)\}`$. By Lemma 3.4, $`A`$ belongs to $`\mathrm{𝐏𝐏}`$.

Next, we show that $`\mathrm{𝐐𝐎𝐏}𝐏^{\mathrm{\#}𝐏[1]}`$. Let $`A`$ be in $`\mathrm{𝐐𝐎𝐏}`$. Similar to 1), we obtain $`\widehat{f}`$ and $`\widehat{g}`$ in $`\mathrm{\#}\mathrm{𝐐𝐏}`$. For this $`\widehat{f}`$, by , there exist two functions $`\stackrel{~}{f}\mathrm{𝐆𝐚𝐩𝐏}`$ and $`\mathrm{}\mathrm{𝐅𝐏}`$ such that, for every $`x`$, $`|\widehat{f}(x)\stackrel{~}{f}(x)/\mathrm{}(1^{|x|})|2^{p(|x|)1}`$. Thus, $`2^{p(|x|)}\widehat{f}(x)`$ coincides with the first $`p(|x|)`$ bits of the binary expansion of $`2^{p(|x|)}\stackrel{~}{f}(x)/\mathrm{}(1^{|x|})`$. Similarly, we obtain $`\stackrel{~}{g}`$ and $`\mathrm{}^{}`$. Without loss of generality, we can assume that $`\mathrm{}=\mathrm{}^{}`$. To determine whether $`x`$ is in $`A`$, we first compute the value $`\stackrel{~}{f}(x)`$ and $`\stackrel{~}{g}(x)`$ and then compare the first $`p(|x|)`$ bits of the binary expansion of $`2^{p(|x|)}\stackrel{~}{f}(x)/\mathrm{}(1^{|x|})`$ and those of $`2^{p(|x|)}\stackrel{~}{g}(x)/\mathrm{}(1^{|x|})`$. This is done by making one query to each of $`\stackrel{~}{f}`$ and $`\stackrel{~}{g}`$. It is easy to reduce these two queries to one single query; for example, we can define another $`\mathrm{\#}𝐏`$-function $`h(x)`$ to be $`2^{q(|x|)}\stackrel{~}{f}(x)+\stackrel{~}{g}(x)`$, where $`q`$ is a polynomial satisfying $`|\stackrel{~}{f}(x)|+|\stackrel{~}{g}(x)|q(|x|)`$ for all $`x`$. Thus, $`A`$ belongs to $`𝐏^{\mathrm{\#}𝐏[1]}`$. ∎

By a simple argument, we next show that $`\mathrm{𝐁𝐐𝐏}\mathrm{𝐐𝐌𝐀}`$ implies $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}⋐̸^p\mathrm{\#}\mathrm{𝐐𝐏}`$. We use the result from Lemma 8.2(2) that $`A\mathrm{𝐐𝐌𝐀}`$ iff there exists a $`f\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ such that, for every $`x`$, if $`xA`$ then $`f(x)3/4`$ and otherwise $`f(x)1/4`$.

###### Lemma 7.7

$`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}⋐̸^p\mathrm{\#}\mathrm{𝐐𝐏}`$ unless $`\mathrm{𝐁𝐐𝐏}=\mathrm{𝐐𝐌𝐀}`$.

###### Proof.

Assume that $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}^p\mathrm{\#}\mathrm{𝐐𝐏}`$. Let $`A`$ be any set in $`\mathrm{𝐐𝐌𝐀}`$. Using the amplification property of $`\mathrm{𝐐𝐌𝐀}`$ (see ), we can assume the existence of a function $`f`$ in $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ such that, for every $`x`$, if $`xA`$ then $`f(x)7/8`$ and otherwise $`f(x)1/8`$. By our assumption, there exists a function $`g\mathrm{\#}\mathrm{𝐐𝐏}`$ such that $`|f(x)g(x)|1/8`$. Thus, if $`xA`$ then $`g(x)f(x)\frac{1}{8}\frac{3}{4}`$. If $`xA`$ then $`g(x)f(x)+\frac{1}{8}\frac{1}{4}`$. Therefore, $`A`$ belongs to $`\mathrm{𝐁𝐐𝐏}`$. ∎

Recall the fact that $`\mathrm{𝐍𝐏}^A\mathrm{𝐁𝐐𝐏}^A`$ for a certain set $`A`$  and that $`\mathrm{𝐍𝐏}^B\mathrm{𝐐𝐌𝐀}^B`$ for any set $`B`$. As a consequence, we obtain the following corollary since Lemma 7.7 relativizes.

###### Corollary 7.8

There exists a set $`B`$ such that $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}^B⋐̸^p\mathrm{\#}\mathrm{𝐐𝐏}^B`$.

## 8 Qopt#QP-Definable Classes

This section discusses the relationship between quantum optimization problems and known complexity classes. To describe the relationship, one useful notion is “definability” of Fenner et al. , which is originally defined only for $`\mathrm{𝐆𝐚𝐩𝐏}`$-functions. The $`\mathrm{\#}\mathrm{𝐐𝐏}`$-definability is also discussed in . We give this “definability” below in a general fashion.

###### Definition 8.1

Let $``$ be any set of functions from $`\mathrm{\Sigma }^{}`$ to $``$. A class $`𝒞`$ of sets is said to be (uniformly) $``$-definable if there exist an positive integer $`k`$ and a pair of disjoint sets $`A,R\mathrm{\Sigma }^{}\times `$ such that, for every set $`A`$ in $`𝒞`$, there exists a function $`f`$ in $``$ satisfying the following condition: for every $`x`$, if $`xA`$ then $`(x,f(x))A`$ and otherwise $`(x,f(x))R`$.

In what follows, we focus on $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$-definable classes. Obvious examples of such classes are $`\mathrm{𝐄𝐐𝐌𝐀}`$ and $`\mathrm{𝐐𝐌𝐀}`$, where $`\mathrm{𝐄𝐐𝐌𝐀}`$ is an error-free restriction of $`\mathrm{𝐐𝐌𝐀}`$  defined as follows. A set $`S`$ is in $`\mathrm{𝐄𝐐𝐌𝐀}`$ if there exists a polynomial $`p`$ and a polynomial-time $`\stackrel{~}{}`$-amplitude well-formed QTM $`M`$ such that, for every $`x`$, (i) if $`xS`$ then there exists a qustring $`|\varphi _x`$ of size $`p(|x|)`$ that forces $`M`$ to accept $`|x|\varphi _x`$ with certainty and (ii) if $`xS`$ then, for any qustring $`|\varphi `$ of size $`p(|x|)`$, $`M`$ rejects $`|x|\varphi `$ with certainty.

###### Lemma 8.2

1. $`\mathrm{𝐄𝐐𝐌𝐀}`$ is $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$-definable. More precisely, $`A\mathrm{𝐄𝐐𝐌𝐀}`$ iff $`\chi _A\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$, where $`\chi _A`$ is the characteristic function of $`A`$; that is, $`\chi _A(x)=1`$ if $`xA`$ and $`\chi _A(x)=0`$ otherwise.

2. $`\mathrm{𝐐𝐌𝐀}`$ is $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$-definable. More strongly, a set $`S`$ is in $`\mathrm{𝐐𝐌𝐀}`$ iff there exist a polynomial $`p`$ and a function $`f\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ such that, for every $`x`$, if $`xA`$ then $`f(x)3/4`$ and otherwise $`f(x)1/4`$.

A less obvious example of $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$-definable class is $`\mathrm{𝐍𝐐𝐏}`$. This is an immediate consequence of Proposition 7.1.

###### Lemma 8.3

$`\mathrm{𝐍𝐐𝐏}`$ is $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$-definable. More strongly, a set $`A`$ is in $`\mathrm{𝐍𝐐𝐏}`$ iff there exists a function $`f\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ such that, for every $`x`$, (i) if $`xA`$ then $`f(x)>0`$, and (ii) if $`xA`$ then $`f(x)=0`$.

###### Proof.

(If – part) Assume that $`A`$ and $`f`$ in $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ satisfy that, for every $`x`$, $`xA`$ iff $`f(x)>0`$. By Proposition 7.1, there exists a function $`g\mathrm{\#}\mathrm{𝐐𝐏}`$ such that, for every $`x`$, $`f(x)>0`$ iff $`g(x)>0`$. Thus, $`A\mathrm{𝐍𝐐𝐏}`$. (Only if – part) This is trivial because $`\mathrm{\#}\mathrm{𝐐𝐏}\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$. ∎

The class $`\mathrm{𝐏𝐏}`$ is one of the most important complexity classes and $`\mathrm{𝐏𝐏}`$ also contains most well-known quantum complexity classes, such as $`\mathrm{𝐁𝐐𝐏}`$, $`\mathrm{𝐐𝐌𝐀}`$, and $`\mathrm{𝐍𝐐𝐏}`$. Moreover, $`\mathrm{𝐏𝐏}`$ is robust in the sense that it equals $`\mathrm{𝐏𝐐𝐏}_\stackrel{~}{}`$, a quantum interpretation of $`\mathrm{𝐏𝐏}`$ . Thus, it is natural to ask whether $`\mathrm{𝐏𝐏}`$ is $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$-definable. The following proposition is a partial answer to this question. This proposition also yields Watrous’s recent result that $`\mathrm{𝐐𝐌𝐀}\mathrm{𝐏𝐏}`$ .

###### Proposition 8.4

Let $`A`$ be any subset of $`\{0,1\}^{}`$. The following statements are equivalent.

1. $`A`$ is in $`\mathrm{𝐏𝐏}`$.
2. For every polynomial $`q`$, there exist two functions $`f\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ and $`g\mathrm{𝐆𝐚𝐩𝐐𝐏}`$ such that, for every string $`x`$ and integer $`m`$ ($`m|x|`$), (i) $`g(x01^m)>0`$; (ii) $`xA`$ implies $`(12^{q(m)})g(x01^m)f(x01^m)g(x01^m)`$; and (iii) $`xA`$ implies $`0f(x01^m)2^{q(m)}g(x01^m)`$.

###### Proof.

(1 implies 2) Let $`A`$ be any set in $`\mathrm{𝐏𝐏}`$. Note that the following characterization of $`\mathrm{𝐏𝐏}`$ is well-known (see ).

###### Fact. 8.5

A set is in $`\mathrm{𝐏𝐏}`$ iff, for every polynomial $`p`$, there exist two functions $`f,g\mathrm{𝐆𝐚𝐩𝐏}`$ such that, for every $`x`$ and every $`m|x|`$, (i) $`g(x01^m)>0`$, (ii) $`xA`$ implies $`(12^{q(m)})g(x01^m)f(x01^m)g(x01^m)`$, and (iii) $`xA`$ implies $`0f(x01^m)2^{q(m)}g(x01^m)`$.

Take $`\stackrel{~}{g}`$ and $`\stackrel{~}{f}`$ from $`\mathrm{𝐆𝐚𝐩𝐐𝐏}`$ and $`\mathrm{}`$ from $`\mathrm{𝐅𝐏}`$ such that $`f(x)=\stackrel{~}{f}(x)\mathrm{}(1^{|x|})`$ and $`g(x)=\stackrel{~}{g}(x)\mathrm{}(1^{|x|})`$ for all $`x`$ . We thus replace $`g`$ and $`f`$ in Fact 8.5 by $`\stackrel{~}{g}`$ and $`\stackrel{~}{f}`$ and then make all the terms squared. Note that $`\stackrel{~}{f}^2`$ and $`\stackrel{~}{g}^2`$ belong to $`\mathrm{\#}\mathrm{𝐐𝐏}`$  and thus, the both are in $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$. Since $`(12^{q(m)})^212^{q(m)+1}`$ and $`(2^{q(m)})^22^{q(m)+1}`$, we can obtain the desired result.

(2 implies 1) Set $`q(n)=n`$ and assume that there exist two functions $`f\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ and $`g\mathrm{𝐆𝐚𝐩𝐐𝐏}`$ satisfying the conditions of statement 2). Since $`g\mathrm{𝐆𝐚𝐩𝐐𝐏}`$ implies $`g^2\mathrm{\#}\mathrm{𝐐𝐏}`$ , we can assume from the beginning of this proof that $`g\mathrm{\#}\mathrm{𝐐𝐏}`$. For each $`x`$, let $`\widehat{x}=x01^{|x|}`$. Proposition 7.1 guarantees the existence of a polynomial $`p`$ and a function $`h\mathrm{\#}\mathrm{𝐐𝐏}`$ satisfying that, for every $`x`$ and $`m>1`$, $`h(\widehat{x}01^m)f^m(\widehat{x})2^{p(|x|)}h(\widehat{x}01^m)`$. We can also assume that $`p(n)2`$ for all $`n`$. Let $`g^{}(x)=2^{2p(|x|)}g^{p(|x|)}(\widehat{x})`$ and $`h^{}(x)=h(\widehat{x}01^{p(|x|)})`$ for all $`x`$. It is easy to see that $`g^{},h^{}\mathrm{\#}\mathrm{𝐐𝐏}`$ since $`g,h\mathrm{\#}\mathrm{𝐐𝐏}`$. In what follows, we show that, for all but finitely-many strings $`x`$, $`xA`$ iff $`g^{}(x)<h^{}(x)`$. This implies that, by Lemma 3.4, $`A`$ is indeed in $`\mathrm{𝐏𝐏}`$.

Fix $`x`$ arbitrarily with $`n=|x|4`$. In the case where $`xA`$, we obtain:

$$2^{\frac{p(n)}{n2}}g^{p(n)}(\widehat{x})(12^n)^{p(n)}g^{p(n)}(\widehat{x})f^{p(n)}(\widehat{x})2^{p(n)}h(\widehat{x}01^{p(n)})$$

since $`(12^n)^{p(n)}=((12^n)^{n2})^{\frac{p(n)}{n2}}`$ and $`(12^n)^{n2}12^{n+(n2)+1}=\frac{1}{2}`$. This yields the inequality $`2^{p(n)(1+1/(n2))}g^{p(n)}(\widehat{x})h^{}(x)`$, which further implies that $`g^{}(x)<h^{}(x)`$ since $`n4`$. Consider the other case where $`xA`$. In this case, we obtain:

$$h^{}(x)=h(\widehat{x}01^{p(n)})f^{p(n)}(\widehat{x})(2^n)^{p(n)}g^{p(n)}(\widehat{x})2^{np(n)}g^{p(n)}(\widehat{x}),$$

which implies $`h^{}(x)<2^{2p(n)}g^{p(n)}(\widehat{x})=g^{}(x)`$ since $`n>2`$. ∎

## 9 Complexity Classes Induced from Qopt#QP

The $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$-definability is a tool in demonstrating a close relationship between $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ and other complexity classes. Here, we take another approach toward the study of the complexity of quantum optimization problems. Instead of $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$, we explore complexity classes induced from $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$. We have already seen the class $`\mathrm{𝐐𝐎𝐏}`$, which has played an important role in approximating quantum optimization problems in Proposition 7.4.

The following claim for $`\mathrm{𝐐𝐎𝐏}`$ is trivial since $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}\mathrm{𝐅𝐏}=\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$.

###### Lemma 9.1

$`\mathrm{𝐐𝐎𝐏}`$ is closed downward under polynomial-time many-one reductions.

We next focus on sets with low information, known as low sets, for $`\mathrm{𝐐𝐎𝐏}`$. Here is a general definition of $``$-low sets.

###### Definition 9.2

Let $``$ be any class (of functions or sets). For any set $`A`$, $`A`$ is low for $``$ (or $``$-low) if $`^A=`$. Let $`\mathrm{𝐥𝐨𝐰}\text{-}`$ denote the collection of all sets that are $``$-low.

An example of such a low set is $`\mathrm{𝐥𝐨𝐰}\text{-}\mathrm{\#}\mathrm{𝐐𝐏}=\mathrm{𝐥𝐨𝐰}\text{-}\mathrm{𝐆𝐚𝐩𝐐𝐏}=\mathrm{𝐄𝐐𝐏}`$ . In the following proposition, we show the low sets for $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ and $`\mathrm{𝐐𝐎𝐏}`$.

###### Proposition 9.3

1. $`\mathrm{𝐄𝐐𝐏}\mathrm{𝐥𝐨𝐰}\text{-}\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}\mathrm{𝐄𝐐𝐌𝐀}`$.

2. $`\mathrm{𝐥𝐨𝐰}\text{-}\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}\mathrm{𝐥𝐨𝐰}\text{-}\mathrm{𝐐𝐎𝐏}\mathrm{𝐐𝐎𝐏}\mathrm{co}\text{-}\mathrm{𝐐𝐎𝐏}`$.

###### Proof.

1) For the first inclusion, assume that $`A\mathrm{𝐄𝐐𝐏}`$. Let $`M_A`$ be its associated QTM. Using the squaring lemma in , we can assume that $`M_A`$ reaches a specific final configuration (in which the tape content is either $`|x|1`$ or $`|x|0`$ and empty elsewhere) with probability $`1`$. Consider any function $`f`$ in $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}^A`$ and its associated QTM $`M`$. As shown in , we can also assume that we have the same number of queries on each computation path of $`M`$. We then obtain a non-relativized QTM by substitute the simulation of $`M_A`$ for a query given by $`M`$. Since this new machine witnesses $`f`$, $`f`$ belongs to $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$.

For the second inclusion, assume that $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}^A=\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$. Since $`\chi _A\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}^A`$, we conclude that $`\chi _A\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$, which implies that $`A\mathrm{𝐄𝐐𝐌𝐀}`$ by Lemma 8.2(1).

2) The first inclusion is trivial. The second inclusion comes from the fact that $`A\mathrm{𝐐𝐎𝐏}^A\mathrm{co}\text{-}\mathrm{𝐐𝐎𝐏}^A`$ for all $`A`$’s. ∎

The difference between $`\mathrm{𝐥𝐨𝐰}\text{-}\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ and $`\mathrm{𝐥𝐨𝐰}\text{-}\mathrm{𝐐𝐎𝐏}`$ stems from the floor-operation (rounding down the terms $`2^{|h(x)|}f(x)`$ and $`2^{|h(x)|}g(x)`$) for $`\mathrm{𝐐𝐎𝐏}`$ in Definition 7.3.

Another example of $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$-related class comes from Proposition 8.4. Our complexity class is inspired by Li’s earlier work. Li  introduced the complexity class $`\mathrm{𝐀𝐏𝐏}`$: a set $`A`$ is in $`\mathrm{𝐀𝐏𝐏}`$ (“amplified” $`\mathrm{𝐏𝐏}`$) iff, for every polynomial $`p`$, there exist two functions $`f,g\mathrm{𝐆𝐚𝐩𝐏}`$ such that, for every $`x`$ and every $`m|x|`$, (i) $`g(1^m)>0`$; (ii) if $`xA`$ then $`(12^{q(m)})g(1^m)f(x01^m)g(1^m)`$; and (iii) if $`xA`$ then $`0f(x01^m)2^{q(m)}g(1^m)`$. Now, we introduce its quantum extension using $`\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$.

###### Definition 9.4

A set $`A`$ is in $`\mathrm{𝐀𝐐𝐌𝐀}`$ (“amplified” QMA) if, for every polynomial $`q`$, there exist two functions $`f\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ and $`g\mathrm{𝐆𝐚𝐩𝐐𝐏}`$ such that, for every string $`x`$ and integer $`m`$ ($`m|x|`$),

i) $`g(1^m)>0`$;

ii) if $`xA`$ then $`(12^{q(m)})g(1^m)f(x01^m)g(1^m)`$; and

iii) if $`xA`$ then $`0f(x01^m)2^{q(m)}g(1^m)`$.

As shown in the proof of Proposition 8.4, by squaring formulas (i) and (ii) in Definition 9.4 (as well as choosing $`q(m)+1`$), we can replace the class $`\mathrm{𝐆𝐚𝐩𝐐𝐏}`$ by $`\mathrm{\#}\mathrm{𝐐𝐏}`$.

Similar to $`\mathrm{𝐀𝐏𝐏}`$, the class $`\mathrm{𝐀𝐐𝐌𝐀}`$ also enjoys simple closure properties: intersection and disjoint union.

###### Lemma 9.5

$`\mathrm{𝐀𝐐𝐌𝐀}`$ is closed under intersection and disjoint union.

###### Proof.

Let $`A_1`$ and $`A_2`$ be any two sets in $`\mathrm{𝐀𝐐𝐌𝐀}`$. Also let $`q`$ be any polynomial. For each $`i\{1,2\}`$, there exist two functions $`f_i\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ and $`g_i\mathrm{𝐆𝐚𝐩𝐐𝐏}`$ such that, for every $`x`$ and $`m|x|`$,

* if $`xA_i`$ then $`(12^{q(m)})g_i(1^m)f_i(x01^m)g_i(1^m)`$ and
* if $`xA_i`$ then $`0f_i(x01^m)2^{q(m)}g_i(1^m)`$.

By the remark after Definition 9.4, we can assume that $`g_1,g_2\mathrm{\#}\mathrm{𝐐𝐏}`$.

For the intersection, note that (i’) if $`xA_1A_2`$ then $`(12^{q(m)})^2g_1(1^m)g_2(1^m)f_1(x01^m)f_2(x01^m)g_1(1^m)g_2(1^m)`$ and (ii’) if $`xA_1A_2`$ then $`0f_1(x01^m)f_2(x01^m)(2^{q(m)})^2g_1(1^m)g_2(1^m)`$. We define $`g(z)=g_1(z)g_2(z)`$ and $`f(z)=f_1(z)f_2(z)`$. Obviously, $`g\mathrm{𝐆𝐚𝐩𝐐𝐏}`$ and $`f\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$. Moreover, $`(12^{q(m)})^212^{q(m)+1}`$ and $`(2^{q(m)})^22^{q(m)+1}`$. Thus, it suffices to take $`q(m)+1`$ for $`q(m)`$ in (i) and (ii).

For the disjoint union, we first multiply the formulas in both (i) and (ii) by $`g_{\overline{i}}(1^m)`$, where $`\overline{i}=3i`$. Define $`g(z)=g_1(z)g_2(z)`$ for all $`z`$. Obviously, $`g`$ is in $`\mathrm{\#}\mathrm{𝐐𝐏}`$. Also, define $`f^{}`$ and $`f^{\prime \prime }`$ so that $`f^{}(x01^m)=f_1(x01^m)g_2(1^m)`$ and $`f^{\prime \prime }(x01^m)=g_1(1^m)f_2(x01^m)`$. Clearly, $`f^{},f^{\prime \prime }\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ since $`g_1,g_2\mathrm{\#}\mathrm{𝐐𝐏}\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$. Let $`M`$ and $`M^{}`$ be appropriate QTMs that witness $`f^{}`$ and $`f^{\prime \prime }`$, respectively, with a polynomial $`p`$ bounding the size of quantum indices. Consider the following QTM $`M`$: on input $`(bx,|\varphi )`$, where $`b\{0,1\}`$, $`x\mathrm{\Sigma }^{}`$, and $`|\varphi `$ is any quantum index of size $`p(|x|+1)`$, if $`b=0`$ then simulate $`M^{}`$ on input $`(x,|\varphi )`$; otherwise, simulate $`M^{\prime \prime }`$ on input $`(x,|\varphi )`$. Let $`f(z)`$ be the maximal acceptance probability, over all $`|\varphi `$, of $`M`$ on input $`(x,|\varphi )`$. It is easy to show that $`g`$ and $`f`$ witness $`A_1A_2`$. ∎

The relationships among aforementioned complexity classes are summarized as follows. Watrous’s recent result $`\mathrm{𝐐𝐌𝐀}\mathrm{𝐏𝐏}`$  is also improved to $`\mathrm{𝐐𝐌𝐀}\mathrm{𝐀𝐐𝐌𝐀}`$.

###### Proposition 9.6

$`\mathrm{𝐀𝐏𝐏}\mathrm{𝐐𝐌𝐀}\mathrm{𝐀𝐐𝐌𝐀}\mathrm{𝐏𝐏}\mathrm{𝐐𝐎𝐏}\mathrm{𝐏𝐒𝐏𝐀𝐂𝐄}`$.

###### Proof.

It is easy to show that $`\mathrm{𝐀𝐏𝐏}\mathrm{𝐀𝐐𝐌𝐀}`$. We next show that $`\mathrm{𝐐𝐌𝐀}\mathrm{𝐀𝐐𝐌𝐀}`$. Let $`A`$ be any set in $`\mathrm{𝐐𝐌𝐀}`$. Note that $`\mathrm{𝐐𝐌𝐀}`$ enjoys the amplification property. Let $`q`$ be any (nondecreasing) polynomial. There exists a function $`f\mathrm{𝐐𝐨𝐩𝐭}\mathrm{\#}\mathrm{𝐐𝐏}`$ such that, for every $`x`$, if $`xA`$ then $`f(x)12^{q(|x|)}`$ and otherwise $`f(x)2^{q(|x|)}`$. Define $`g(x)=1`$ for all strings $`x`$. It follows that $`f`$ and $`g`$ satisfy Definition 9.4. The inclusion $`\mathrm{𝐀𝐐𝐌𝐀}\mathrm{𝐏𝐏}`$ easily follows from Proposition 8.4. Finally, we show that $`\mathrm{𝐏𝐏}\mathrm{𝐐𝐎𝐏}`$. This is obvious by Lemma 3.4 and the following fact: for every $`f\mathrm{\#}\mathrm{𝐐𝐏}`$, there exists a polynomial $`p`$ such that $`2^{p(|x|)}f(x)=2^{p(|x|)}f(x)`$ for all $`x`$. The last inclusion $`\mathrm{𝐐𝐎𝐏}\mathrm{𝐏𝐒𝐏𝐀𝐂𝐄}`$ follows from Proposition 7.4. ∎

### Acknowledgments

The author is truly grateful of Hirotada Kobayashi for his insightful comments and corrections of errors in an early draft of this paper and of Steve Homer and Frederic Green for an interesting discussion at Boston University on quantum optimization problems. He also thanks Jack C.H. Lin for pointing out typos.

## Appendix

We show from  three local requirements on a quantum transition function that its associated QTM should be well-formed.

We begin with the simple case of 1-tape QTMs. Let $`M=(Q,\{q_0\},Q_f,\mathrm{\Sigma },\delta )`$ be a 1-tape QTM with initial state $`q_0`$ and a set $`Q_f`$ of final states. As noted before, the head move directions $`R`$, $`N`$, and $`L`$ are freely identified with $`1`$, $`0`$, and $`+1`$, respectively. We introduce new notation that is helpful to describe the well-formedness of QTMs. Let $`D=\{0,1,1\}`$, $`E=\{0,\pm 1,\pm 2\}`$, and $`H=\{0,\pm 1,\mathrm{}\}`$. For $`dD`$ and $`ϵE`$, we write $`E_d=\{ϵE|2dϵ|1\}`$ and $`D_ϵ=\{dD|2dϵ|1\}`$. Let $`(p,\sigma ,\tau )Q\times \mathrm{\Sigma }^2`$ and $`ϵE`$.

Bernstein and Vazirani  introduced the notation $`\delta (p,\sigma |\tau ,d)`$ for $`_{qQ}\delta (p,\sigma ,q,\tau ,d)|q`$. Instead of their notation, we introduce the notation $`\delta [p,\sigma ,\tau |ϵ]`$. An element $`\delta [p,\sigma ,\tau |ϵ]`$ in $`^H`$ is defined as:

$$\delta [p,\sigma ,\tau |ϵ]=\underset{qQ}{}\underset{dD_ϵ}{}\frac{\delta (p,\sigma ,q,\tau ,d)}{\sqrt{|E_d|}}|q|h_{d,ϵ},$$

where $`h_{d,ϵ}=2dϵ`$ if $`ϵ0`$ and $`h_{d,ϵ}=\mathrm{}`$ otherwise. The term $`\sqrt{|E_d|}`$ in the above equation ensures that $`_{ϵE}\delta [p,\sigma ,\tau |ϵ]^2=_{dD}\delta (p,\sigma |\tau ,d)^2`$.

###### Lemma 9.7

A 1-tape QTM $`M=(Q,\{q_0\},Q_f,\mathrm{\Sigma },\delta )`$ is well-formed iff the following three conditions hold.

1. (unit length) $`\delta (p,\sigma )=1`$ for all $`(p,\sigma )Q\times \mathrm{\Sigma }`$.
2. (orthogonality) $`\delta (p_1,\sigma _1)\delta (p_2,\sigma _2)=0`$ for any distinct pair $`(p_1,\sigma _1),(p_2,\sigma _2)Q\times \mathrm{\Sigma }`$.
3. (separability) $`\delta [p_1,\sigma _1,\tau _1|ϵ]\delta [p_2,\sigma _2,\tau _2|ϵ^{}]=0`$ for any distinct pair $`ϵ,ϵ^{}E`$ and for any pair $`(p_1,\sigma _1,\tau _1),(p_2,\sigma _2,\tau _2)Q\times \mathrm{\Sigma }^2`$.

We return to the case of $`k`$-tape QTMs. Now we expand the notation $`\delta [p,\sigma ,\tau |ϵ]`$ as follows. Let $`(p,𝝈,𝝉)Q\times (\mathrm{\Sigma }^k)^2`$ and $`\mathit{ϵ}E^k`$. Let $`D__\mathit{ϵ}=\{𝒅D^ki\{1,\mathrm{},k\}(|2d_iϵ_i|1)\}`$, where $`𝒅=(d_i)_{1ik}`$ and $`\mathit{ϵ}=(ϵ_i)_{1ik}`$. Let $`h_{{}_{𝒅}{}^{},_\mathit{ϵ}}=(h_{d_i,ϵ_i})_{1ik}`$. Note that if $`|\mathit{ϵ}||\mathit{ϵ}^{}|`$ then $`h_{{}_{𝒅}{}^{},_\mathit{ϵ}}h_{{}_{𝒅}{}^{}{}_{}{}^{},_{}^{}{}_{\mathit{ϵ}}{}^{}}`$ for any $`𝒅D__\mathit{ϵ}`$ and any $`𝒅^{}D__{}^{}{}_{\mathit{ϵ}}{}^{}`$, where $`|ϵ|=(|ϵ_i|)_{1ik}`$.

We define $`\delta [p,𝝈,𝝉|\mathit{ϵ}]`$ as follows:

$$\delta [p,𝝈,𝝉|\mathit{ϵ}]=\underset{qQ}{}\underset{{}_{𝒅}{}^{}D__\mathit{ϵ}}{}\frac{\delta (p,𝝈,q,𝝉,𝒅)}{\sqrt{|E__𝒅|}}|q|h_{{}_{𝒅}{}^{},_\mathit{ϵ}}.$$

Since any two distinct tapes do not interfere, multi-tape QTMs must satisfy the $`k`$ independent conditions of Lemma 9.7. Thus, we obtain:

###### Lemma 9.8

(Well-Formedness Lemma) Let $`k1`$. A $`k`$-tape QTM $`M=(Q,\{q_0\},Q_f,\mathrm{\Sigma }^k,\delta )`$ is well-formed iff the following three conditions hold.

1. (unit length) $`\delta (p,𝝈)=1`$ for all $`(p,𝝈)Q\times \mathrm{\Sigma }^k`$.
2. (orthogonality) $`\delta (p_1,𝝈_1)\delta (p_2,𝝈_2)=0`$ for any distinct pairs $`(p_1,𝝈_1),(p_2,𝝈_2)Q\times \mathrm{\Sigma }^k`$.
3. (separability) $`\delta [p_1,𝝈_1,𝝉_1|\mathit{ϵ}]\delta [p_2,𝝈_2,𝝉_2|\mathit{ϵ}^{}]=0`$ for any distinct pair $`\mathit{ϵ},\mathit{ϵ}^{}E^k`$ and for any pair $`(p_1,𝝈_1,𝝉_1),(p_2,𝝈_2,𝝉_2)Q\times (\mathrm{\Sigma }^k)^2`$.

At the end of this appendix, we give the proof of Lemma 6.6.

Proof of Lemma 6.6.  Let $`ACC`$ and $`REJ`$ be the sets of all accepting configurations and rejecting configurations, respectively. Let $`ALL=ACCREJ`$. Assume that $`U_M|\varphi =_{iALL}\alpha _i|i`$ and $`U_N|\psi =_{iALL}\beta _i|i`$.

$`2|\eta _M(|\varphi )\eta _N(|\psi )|`$ $`=`$ $`|\eta _M(|\varphi )\eta _N(|\psi )|+|\overline{\eta }_M(|\varphi )\overline{\eta }_N(|\psi )|`$
$``$ $`{\displaystyle \underset{iACC}{}}\left||\alpha _i|^2|\beta _i|^2\left|+{\displaystyle \underset{iREJ}{}}\right||\alpha _i|^2|\beta _i|^2\right|`$
$`=`$ $`{\displaystyle \underset{iALL}{}}\left|(|\alpha _i||\beta _i|)(|\alpha _i|+|\beta _i|)\right|`$
$``$ $`{\displaystyle \underset{iALL}{}}|\alpha _i\beta _i||\alpha _i|+{\displaystyle \underset{iALL}{}}|\alpha _i\beta _i||\beta _i|`$
$``$ $`\left({\displaystyle \underset{iALL}{}}|\alpha _i\beta _i|^2{\displaystyle \underset{iALL}{}}|\alpha _i|^2\right)^{1/2}+\left({\displaystyle \underset{iALL}{}}|\alpha _i\beta _i|^2{\displaystyle \underset{iALL}{}}|\beta _i|^2\right)^{1/2}`$
$`=`$ $`2\left({\displaystyle \underset{iALL}{}}|\alpha _i\beta _i|^2\right)^{1/2}`$
$`=`$ $`2U_M|\varphi U_N|\psi _2,`$
where $`\overline{\eta }_M(x)`$ is the rejection probability of $`M`$ on input $`x`$. For the first and the second inequalities, we use $`||\alpha _i||\beta _i|||\alpha _i\beta _i|`$ and the Cauchy-Schwartz inequality. $`\mathrm{}`$