Quantum Complexity Classes and Oracle Separations

Fix one valid query to the indexed transducer. Its read-only input and query tapes have polynomially many head positions in $n$, its work tapes use $O(\log (n+2))$ cells over a fixed alphabet, and its finite control has finitely many states. Thus it has at most $(n+2{)}^c$ internal configurations for some fixed $c$. A halting deterministic computation cannot repeat an internal configuration: because the input tapes are read-only and the output tape is write-only, a repetition would repeat the same future transitions forever. Hence each size, type, predecessor, or output query takes polynomial time and writes polynomially many bits.

Query the total node count $N_n\le n+q(n)$ once. For every index $1,\dots ,N_n$, query its type, recording its input label or constant value when applicable, and query every predecessor required by that type; also query the designated output. This includes all $n$ input nodes wherever they occur in the topological order. There are polynomially many queries, each of polynomial time by step 1.1. Every node index is at most $n+q(n)$, so each self-delimiting index has $O(\log (n+q(n)+2))$ bits. Writing the input-count header and all records therefore takes polynomial time and produces a polynomial-length full list.

Each record is the exact gate type, input label or constant value, and predecessor data returned for that same topological node, and the final output field is the exact designated node. The full-list decoder consequently evaluates the same ordered DAG on every input, including the case $n=0$ when the input list is empty.

Each basis projection $P_a$ and $Q_b$ is diagonal with entries $0$ or $1$, hence self-adjoint and idempotent; distinct projections in each family are orthogonal and each family sums to the identity. By [F8], their lifted maps $P_a\otimes I_B$ and $I_A\otimes Q_b$ are self-adjoint idempotents, and each lifted family sums to $I_{A\otimes B}$.

The product basis $(e_a\otimes g_b{)}_{a,b}$ is orthonormal by [F4]. Therefore the coordinates of $\psi$ satisfy ${\sum }_{a,b}\mathrm{\mid }{c}_{a,b}{\mathrm{\mid }}^2=1$. By [F7], $\rho =\mathrm{\mid }\psi ⟩⟨\psi \mathrm{\mid }$ has matrix $v{v}^{†}$, so for every coordinate vector $u$ its quadratic form is $u^{†}v{v}^{†}u=\mathrm{\mid }{v}^{†}u{\mathrm{\mid }}^2\ge 0$ and its trace is ${\sum }_{a,b}\mathrm{\mid }{c}_{a,b}{\mathrm{\mid }}^2=1$. Hence $\rho$ is a density operator by [F6].

Each branch map is complex-linear. For any finite reference register $R$, write an operator $Q$ on $(A\otimes B)\otimes R$ in the ancilla blocks of [F2]. Its amplified branch sends each block $Q_{ij}$ to $C{Q}_{ij}C$, so [F8] identifies the full block matrix as $Q^{\mathrm{\prime }}=(C\otimes I_R)Q(C\otimes I_R)$, where $C$ is the lifted projector from step 1.1. If $Q$ is nonnegative, then $Q^{\mathrm{\prime }}$ is self-adjoint and $⟨Q^{\mathrm{\prime }}u,u⟩=⟨Q(C\otimes I_R)u,(C\otimes I_R)u⟩\ge 0$ for every $u$ by [F3], so every amplification preserves nonnegative operators. Thus each branch is completely positive by [F2].

Write $v$ for the coordinate column of $\psi$ and $C$ for either lifted projector. By [F7], the corresponding branch is $Cv{v}^{†}C=(Cv)(Cv{)}^{†}$. For outcome $a$, $(P_a\otimes I_B)\psi ={\sum }_b{c}_{a,b}{e}_a\otimes g_b$, so the diagonal entry at each coordinate $(a,b)$ is $\mathrm{\mid }{c}_{a,b}{\mathrm{\mid }}^2$ and every other diagonal entry is zero; off-diagonal entries within the selected $a$-subspace can be nonzero. Its trace is ${\sum }_b\mathrm{\mid }{c}_{a,b}{\mathrm{\mid }}^2$. For outcome $b$, $(I_A\otimes Q_b)\psi ={\sum }_a{c}_{a,b}{e}_a\otimes g_b$, so the diagonal entry at each coordinate $(a,b)$ is $\mathrm{\mid }{c}_{a,b}{\mathrm{\mid }}^2$ and every other diagonal entry is zero; off-diagonal entries within the selected $b$-subspace can be nonzero. Its trace is ${\sum }_a\mathrm{\mid }{c}_{a,b}{\mathrm{\mid }}^2$. These traces are the asserted probabilities by [F1].

For every operator $R$, cyclicity of trace and idempotence give ${\sum }_a\mathrm{tr}((P_a\otimes I_B)R(P_a\otimes I_B))=\mathrm{tr}\text{\hspace{0.17em}⁣}(R{\sum }_a(P_a\otimes I_B))=\mathrm{tr}(R)\mathrm{.}$ The same calculation gives ${\sum }_b\mathrm{tr}((I_A\otimes Q_b)R(I_A\otimes Q_b))=\mathrm{tr}(R)$. Together with step 2.1 these are the finite-instrument conditions of [F1].

If a branch vector $w=C\psi$ has positive probability $p={\sum }_i\mathrm{\mid }{w}_i{\mathrm{\mid }}^2$ from step 2.2, its conditional operator in [F1] is $\mathrm{\mid }(w\mathrm{/}\sqrt{p})⟩⟨(w\mathrm{/}\sqrt{p})\mathrm{\mid }$. Its coordinate quadratic form is nonnegative and its trace is ${\sum }_i\mathrm{\mid }{w}_i{\mathrm{\mid }}^2\mathrm{/}p=1$, so it is a density operator by [F6]–[F7]; a zero-probability branch has no conditional state by [F1].

For $a,b,c\in \{0,1\}$ set $d=a+b+c-(a\oplus b)-(a\oplus c)-(b\oplus c)+(a\oplus b\oplus c)$, with ordinary integer addition and subtraction. If exactly $k$ of $a,b,c$ equal $1$, then $d=0$ for $k=0,1,2$ and $d=4$ for $k=3$. Thus $d=4abc$.

Use one clean scratch bit $r$. Apply $T$ to each of the three data bits. For each of the three pair parities, compute that XOR into $r$ with two CNOTs, apply $T^{†}$ to $r$, and undo the same two CNOTs. Compute $a\oplus b\oplus c$ into $r$ with three CNOTs, apply $T$, and undo those three CNOTs. Each parity routine restores $r$ to zero and leaves the data bits unchanged. The total phase on $\mathrm{\mid }a,b,c⟩$ is ${\omega }^d=(-1{)}^{abc}$, so this circuit is CCZ; it uses seven $T$ or $T^{†}$ gates and eighteen CNOTs.

Conjugate this CCZ circuit by $H$ on the third data wire. If $ab=0$, CCZ is the identity on that wire; if $ab=1$, it applies $Z=T^4$, and direct multiplication of the displayed matrices gives $HZH=X$. The result is therefore $\mathrm{\mid }a,b,c⟩\mapsto \mathrm{\mid }a,b,c\oplus ab⟩$, the Toffoli action. The scratch wire is still zero, and the replacement uses $2+7+18=27$ QC14 gates.

Replace each $X$ in the reversible embedding by $H{T}^{4}H$, which equals $X$ because $T^4=Z$ and $HZH=X$; this uses six QC14 gates. Leave each CNOT unchanged and replace each Toffoli by step 3.1.

By [F2], the original macro list has at most $6S+4E+m$ occurrences. Each macro replacement has the same action on its data wires, returns the added scratch to zero, and uses at most $27$ gates, so the compiled list has at most $27(6S+4E+m)$ gates and at most $S+E+1$ clean work wires. The exact matrix identity on every computational-basis input extends by linearity to superpositions.

Traverse the explicit topological DAG once to produce the finite macro list of [F1], then replace each macro by its fixed gate sequence and fixed scratch-wire indices. Put each emitted gate in its own singleton layer, which satisfies the disjoint-support condition in [F4] and preserves the chronological product. Serialize this gate sequence using [F5], with the target wires as the ordered output tuple. The traversal and each replacement emit a constant number of records per node, port use, or output; every encoded wire index has $O(\log (n+S+E+m+2))$ bits. The unary wire header and all self-delimiting records consequently have polynomial total length and can be written in polynomial time. All gate-wire tuples have distinct entries, the input, target and work blocks are disjoint, and the output indices are distinct. Thus the singleton-layer circuit and its full-list code satisfy [F4]–[F5], with the action established in step 5.1.

Let $\mathrm{\Pi }=(Y,N)\in \mathrm{P}\mathrm{r}\mathrm{o}\mathrm{m}\mathrm{i}\mathrm{s}\mathrm{e}\mathrm{P}$ and choose its deterministic polynomial-time decider $M$ from [F1]. The Boolean circuit family of [F2] computes $M$; [F3] gives a polynomial-time full-list generator, and [F4] compiles each list into a QC14 family whose one-bit target is $1$ exactly when $M$ accepts. The two polynomial-time stages compose to one fixed deterministic multitape generator $G$ on input $1^n$: it emits the Boolean list and compiles that list to the complete QC14 description. Its intermediate list length and total running time are polynomial in $n$. Convert $G$ to one tape by storing the finitely many simulated tape contents in aligned tracks of a finite product alphabet, with one head marker per tape. During a computation of at most $P(n)$ steps, each track uses at most $n+P(n)+O(1)$ cells; a constant number of sweeps across this interval simulates each transition, so the one-tape time is $O(P(n)(n+P(n)))$. Write the generated circuit description on an output track starting at cell $0$; at halt, a cleanup sweep replaces each product symbol by its output-track component, leaving the exact binary description followed by blanks on the final tape. This is one fixed deterministic one-tape polynomial-time generator as required by [F5]. Use the target bit as the acceptance predicate. For every $x\in Y$ the acceptance probability is $1$, and for every $x\in N$ it is $0$, so $\mathrm{\Pi }\in \mathrm{E}\mathrm{Q}\mathrm{P}$.

If $\mathrm{\Pi }\in \mathrm{E}\mathrm{Q}\mathrm{P}$, take its witnessing family and define $D_n(x,z)=\mathrm{Y}\mathrm{E}\mathrm{S}$ when its acceptance predicate accepts and $D_n(x,z)=\mathrm{N}\mathrm{O}$ otherwise. This is a total polynomial-time decoder. The exact probabilities in [F5] make the wrong definite label have probability zero and the correct definite label have probability one on each promised side; therefore the same family witnesses $\mathrm{\Pi }\in \mathrm{Z}\mathrm{Q}\mathrm{P}$.

If $\mathrm{\Pi }\in \mathrm{Z}\mathrm{Q}\mathrm{P}$, keep its full-list family and define the BQP acceptance predicate to accept exactly when $D_n(x,z)=\mathrm{Y}\mathrm{E}\mathrm{S}$. On $Y$ this event has probability at least $2\mathrm{/}3$. On $N$ it has probability zero, since a wrong definite YES label is forbidden. By [F8] these event probabilities are normalized, and [F7] gives $\mathrm{\Pi }\in \mathrm{B}\mathrm{Q}\mathrm{P}$.

If $\mathrm{\Pi }\in \mathrm{P}\mathrm{r}\mathrm{o}\mathrm{m}\mathrm{i}\mathrm{s}\mathrm{e}\mathrm{P}$, run its deterministic decider as a PTM that ignores all random bits. Its acceptance probability is $1$ on $Y$ and $0$ on $N$, so it satisfies [F2]. Thus $\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{m}\mathrm{i}\mathrm{s}\mathrm{e}\mathrm{P}\subseteq \mathrm{P}\mathrm{r}\mathrm{o}\mathrm{m}\mathrm{i}\mathrm{s}\mathrm{e}\mathrm{B}\mathrm{P}\mathrm{P}$.

Now let $\mathrm{\Pi }\in \mathrm{P}\mathrm{r}\mathrm{o}\mathrm{m}\mathrm{i}\mathrm{s}\mathrm{e}\mathrm{B}\mathrm{P}\mathrm{P}$ be witnessed by a PTM $M$. Choose a strictly increasing positive integer polynomial $R(n)$ that bounds both its run time and the number of fair bits it can use on length-$n$ inputs. By [F3], using a uniform $R(n)$-bit string and ignoring its unused suffix preserves every acceptance probability.

For a binary word $w$ of length $m$, define one deterministic polynomial-time machine $M^{\mathrm{♯}}$ as follows. Search for an $n$ with $m=n+R(n)$; strict increase makes it unique if it exists. If none exists, output $0$. If it exists, split $w=x\mathrm{\parallel }r$ with $\mathrm{\mid }x\mathrm{\mid }=n$ and $\mathrm{\mid }r\mathrm{\mid }=R(n)$, simulate $M$ on $x$ using $r$ as its fair random tape, and output its accept bit. The search and simulation take polynomial time in $m$, since $n\le m$ and $R$ is a fixed polynomial. Whenever a fixed multitape stage in this construction or its later composition runs for at most $P(m)$ steps, a one-tape simulator stores its finitely many tape contents in aligned tracks of a finite product alphabet, with one head marker per tape. Each track uses at most $m+P(m)+O(1)$ cells, and a constant number of sweeps simulates each step in $O(m+P(m))$ time. Put the binary output on a designated track starting at cell $0$; a final cleanup sweep replaces each product symbol by its output-track component, leaving the exact output word followed by blanks on the final tape. Thus the construction has a one-tape polynomial-time implementation whenever that convention is needed.

Apply [F4] to $M^{\mathrm{♯}}$, then [F5] to emit the Boolean gate list at length $m(n)=n+R(n)$. Compose this generator with the polynomial-time map $n\mapsto m(n)$. Apply [F6] to that list. In the resulting QC14 family on input $x$, designate the next $R(n)$ auxiliary wires as the random register, apply $H$ to each from its initial zero state, and then run the reversible compiler on the $x$ and random registers with a zero target and clean work. Starting from the compiled list with $g$ gates, prefix Hadamard records on wire indices $n,\dots ,n+R(n)-1$, change the unary input-wire count to $n$, and rewrite the self-delimiting gate count to $g+R(n)$; retain the same total-wire count, target tuple and compiled gate records. The fixed composition of these list operations runs in polynomial time in $n$ because all intermediate Boolean and QC14 descriptions have polynomial length. The one-tape simulation described in step 2.1 therefore yields one fixed deterministic one-tape generator that leaves the complete QC14 description as its final tape word, as required for the full-list family.

By [F8]–[F9], the Hadamards prepare $2^{-R(n)\mathrm{/}2}{\sum }_{r\in \{0,1{\}}^{R(n)}}\mathrm{\mid }r⟩$ on the zero-initialized random register. For each basis $r$, the reversible circuit writes exactly the bit $M(x;r)$ into the target and returns its work to zero. Distinct $r$ values remain in orthogonal computational-basis states of the unmeasured random register. The one-tape generator from step 3.1 satisfies the full-list uniformity condition in [F7]. Therefore, by [F10], the target's acceptance probability is $2^{-R(n)}\mathrm{\#}\{r\in \{0,1{\}}^{R(n)}:M(x;r)\text{ accepts}\},$ which is exactly the PTM acceptance probability in [F3]. Its YES and NO bounds in [F2] are the BQP bounds in [F7]. Hence $\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{m}\mathrm{i}\mathrm{s}\mathrm{e}\mathrm{B}\mathrm{P}\mathrm{P}\subseteq \mathrm{B}\mathrm{Q}\mathrm{P}$.

For an ordinary language $L\in \mathrm{B}\mathrm{P}\mathrm{P}$, use the total promise pair $(L,\{0,1{\}}^{\ast }\setminus L)$. Its BPP PTM satisfies the PromiseBPP definition [F2], so step 4.1 gives a BQP family for the language. Thus $\mathrm{B}\mathrm{P}\mathrm{P}\subseteq \mathrm{B}\mathrm{Q}\mathrm{P}$.

Consider the finite input distribution that chooses YES or NO with probability $1\mathrm{/}2$. In the YES case choose a uniform permutation of $V_n$. In the NO case choose a uniform nonzero mask $s$, then a uniform injection from the $N\mathrm{/}2$ cosets $\{x,x\oplus s\}$ into the $N$ output labels. Every valid NO function has a unique mask, and each mask has the same number of such injections, so this is uniform over valid NO functions.

It suffices to bound every deterministic query strategy: any randomized strategy has finitely many possible histories and actions up to depth $T$, so its conditional action choices can be represented as a finite distribution over deterministic decision trees. Repeated queries can be removed by caching their earlier answer, so assume every queried address is fresh.

Fix a deterministic strategy and a query index $k\le T$. Since $N\ge 16$, the premise $T\le \sqrt{N}\mathrm{/}8$ implies $k\le N\mathrm{/}2$. Suppose its first $k-1$ distinct query addresses $x_1,\dots ,x_{k-1}$ have produced distinct outputs. Under a NO mask, this transcript is possible exactly when $s\mathrm{\ne }{x}_i\oplus x_j$ for every $i<j<k$. Thus at most $\left(\genfrac{}{}{0px}{}{k-1}{2}\right)$ of the $N-1$ nonzero masks are excluded. For every remaining mask, the queried addresses lie in distinct cosets; the number of injective assignments of output labels to the unqueried cosets is $\frac{(N-k+1)!}{(N\mathrm{/}2)!},$ independent of the mask. Hence, conditioned on this transcript, the mask is uniform among at least $N-1-\left(\genfrac{}{}{0px}{}{k-1}{2}\right)$ candidates.

The next address $x_k$ is determined by the transcript. At most $k-1$ candidate masks, namely $x_k\oplus x_j$ for $j<k$, make its output collide with a previous output. Therefore $\mathrm{Pr}[\text{first collision at query }k\mid \text{no earlier collision}]\le \frac{k-1}{N-1-\left(\genfrac{}{}{0px}{}{k-1}{2}\right)}\mathrm{.}$ If there is no collision, $x_k$ belongs to a new coset whose output label is uniform among the $N-k+1$ unused labels, exactly as the next output of a uniformly random permutation. Couple the two oracle transcripts to use the same unused label until a Simon collision occurs; the adaptive address choices then also agree up to that time.

For $T\le \sqrt{N}\mathrm{/}8$ and $N\ge 16$, each denominator in step 3.1 is at least $N-1-T^2\mathrm{/}2>N\mathrm{/}2$. Summing the conditional first-collision bounds gives ${\mathrm{Pr}}_{\mathrm{N}\mathrm{O}}[\text{a collision by query }T]\le {\sum }_{k=2}^T\frac{2(k-1)}{N}=\frac{T(T-1)}{N}\le \frac{1}{64}<\frac{1}{3}\mathrm{.}$ This also bounds the probability that the coupled transcripts differ.

Let $D$ be the deterministic decision bit, with $1$ meaning YES. Under the coupling, its outputs in the two cases differ with probability at most $1\mathrm{/}64$, so ${\mathrm{Pr}}_{\mathrm{Y}\mathrm{E}\mathrm{S}}[D=1]-{\mathrm{Pr}}_{\mathrm{N}\mathrm{O}}[D=1]\le \frac{1}{64}\mathrm{.}$ Its average success under the equal mixture is $\frac{1}{2}({\mathrm{Pr}}_{\mathrm{Y}\mathrm{E}\mathrm{S}}[D=1]+{\mathrm{Pr}}_{\mathrm{N}\mathrm{O}}[D=0])=\frac{1}{2}(1+{\mathrm{Pr}}_{\mathrm{Y}\mathrm{E}\mathrm{S}}[D=1]-{\mathrm{Pr}}_{\mathrm{N}\mathrm{O}}[D=1])\le \frac{1+1\mathrm{/}64}{2}<\frac{2}{3}\mathrm{.}$ By step 1.2 the same bound holds for every randomized algorithm. A worst-case error bound of $1\mathrm{/}3$ would imply average success at least $2\mathrm{/}3$, a contradiction. Therefore at least $\sqrt{N}\mathrm{/}8$ queries are required for all sufficiently large $n$, which is $\mathrm{\Omega }(2^{n\mathrm{/}2})$.

By the factorwise tensor rule [F5], $H^{\otimes n}\mathrm{\mid }x⟩=N^{-1\mathrm{/}2}{\sum }_{y\in V_n}(-1{)}^{x\cdot y}\mathrm{\mid }y⟩$. In particular the first Hadamards prepare $N^{-1\mathrm{/}2}{\sum }_{x\in V_n}\mathrm{\mid }x,0^n⟩$. After one query the state is $\mathrm{\mid }{\psi }_f⟩=N^{-1\mathrm{/}2}{\sum }_{x\in V_n}\mathrm{\mid }x,f(x)⟩\mathrm{.}$ For each function-register result $z$ in the image of $f$, [F4] gives probability $\mathrm{\mid }{f}^{-1}(z)\mathrm{\mid }\mathrm{/}N$ and the conditional input superposition that is uniform on that fiber.

If $f$ is YES, every fiber is a singleton $\{x\}$. The conditional input state is $\mathrm{\mid }x⟩$, and the second Hadamards give amplitude $N^{-1\mathrm{/}2}(-1{)}^{x\cdot y}$ at every $y\in V_n$. By the first-register instrument law [F4], its squared modulus is the conditional output probability $1\mathrm{/}N$, independent of the measured function-register value; hence the unconditional sample is uniform on $V_n$.

If $f$ is NO with mask $s\mathrm{\ne }0$, a positive-probability fiber has the form $\{x,x\oplus s\}$. Its conditional input state is $(\mathrm{\mid }x⟩+\mathrm{\mid }x\oplus s⟩)\mathrm{/}\sqrt{2}$. After the second Hadamards the amplitude at $y$ is $\frac{(-1{)}^{x\cdot y}}{\sqrt{2N}}(1+(-1{)}^{s\cdot y})\mathrm{.}$ It is zero when $s\cdot y=1$ and has squared modulus $2\mathrm{/}N$ when $s\cdot y=0$. By [F4], these squared moduli are the conditional output probabilities. Pairing $y$ with $y\oplus e_j$ for a coordinate $j$ with $s_j=1$ shows that exactly $N\mathrm{/}2$ strings lie in $s^{\perp }$. The conditional law is therefore uniform on $s^{\perp }$ and independent of the measured fiber label, so the unconditional law is the same.

In the NO case every sample lies in $s^{\perp }$, which is proper because $e_j\mathrm{\notin }{s}^{\perp }$ when $s_j=1$. The span of the samples is proper, so its rank is less than $n$ and the algorithm rejects. The elimination procedure preserves row span under row swaps and row XORs; at termination its nonzero rows have distinct pivot columns and are linearly independent. They still span the original rows, so the pivot count is the matrix rank. At most $n$ pivots each inspect and update $O(n+2)$ rows of $n$ bits, giving $O(n^3)$ bit operations.

Each run reinitializes both registers and uses no earlier outcome as an input. Thus the conditional law of the next sample given any previous transcript is the same one-run law; induction on the number of runs gives the product law, and [F7] identifies the coordinates as independent. In the YES case each sample is uniform on $V_n$ by step 2.1. Their matrix has rank below $n$ exactly when some nonzero $t\in V_n$ satisfies $t\cdot y_j=0$ for every row $j$: Gaussian elimination uses invertible row operations and produces fewer than $n$ pivot columns, so a free variable can be set to $1$ and the pivot variables solved backwards to give a nonzero solution of the homogeneous system. Conversely, if such a $t$ exists, every row lies in its kernel; a coordinate vector $e_k$ with $t_k=1$ is outside that kernel, so the rows cannot span $V_n$.

Fix $t\mathrm{\ne }0$ and choose $k$ with $t_k=1$. The involution $y\mapsto y\oplus e_k$ pairs vectors with opposite values of $t\cdot y$, so a uniform sample satisfies $t\cdot y=0$ with probability $1\mathrm{/}2$. Independence gives probability $2^{-m}$ that all $m$ samples are orthogonal to $t$. Pointwise, the indicator of the union over the $N-1$ nonzero $t$ is at most the sum of their indicators; summing over the finite probability space yields $\mathrm{Pr}[\mathrm{rank}<n]\le (N-1)2^{-m}=(2^n-1)2^{-(n+2)}<\frac{1}{4}\mathrm{.}$ Each of the $m=n+2$ runs in [F2] makes one oracle call, applies two layers of $n$ ordinary Hadamard gates, and performs two finite register readouts. Thus the totals are $n+2$ queries, $2n(n+2)$ Hadamard gates, and $2(n+2)$ readouts; step 3.1 gives the classical elimination cost.