Q The Query Complexity Zoo
\(\mathrm{PostQ}_{\varepsilon}(f)\)

Post-selected quantum query complexity

Quantum queries when the algorithm may post-select on an exponentially unlikely event.

Definition

The algorithm may condition on a measurement outcome of arbitrarily small probability (the class $\mathsf{PostBQP}$ analogue). Mahadev-de Wolf showed this is exactly characterised by rational approximation: $$\mathrm{PostQ}_\varepsilon(f) = \Theta(\mathrm{rdeg}_\varepsilon(f)).$$

Parameters

\(\varepsilon\) (eps) default \(1/3\)

Basic facts

  • Post-selection and bounded error are incomparable resources: for partial functions there are unbounded separations between $\mathrm{rdeg}$ and $\widetilde{\deg}$ in both directions [IJKKKSWW23].

Equivalent / near-equivalent measures

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{PostQ}_{\varepsilon}(f)\). “\(\mathrm{PostQ}_{\varepsilon}(f)\) in terms of it” is the pair with \(\mathrm{PostQ}_{\varepsilon}(f)\) on the left (the matrix row); the other column is the reverse. Each cell gives, per setting, the exponent range a,b of the best bounds known — \(\mathrm{M_1} = \Omega(\mathrm{M_2}^{a})\) below and \(\mathrm{M_1} = O(\mathrm{M_2}^{b})\) above, so \(a = b\) means settled — or a glyph where no polynomial bound exists at all. These are derived, not just read off the exponent table, so they are present for pairs the table does not cover. A cell with no entry for a setting is one where the zoo has nothing at that setting, and a — one where the ordered pair is empty in all three; derived marks a direction with no hand-written relation record behind it, which is the common case and not a hole.

Other measure \(\mathrm{PostQ}_{\varepsilon}(f)\) in terms of it It in terms of \(\mathrm{PostQ}_{\varepsilon}(f)\)
\(\mathrm{rdeg}(f)\) Rational degree total1,1 partial1,1 derived open pair → total∞ partial∞ derived open pair →
\(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree total1,1 partial1,1 open pair → total1,1 partial1,1 derived open pair →
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity total1,1 partial1,1 derived open pair → total∞ partial∞ derived open pair →
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree total1,1 partial1,1 derived open pair → total∞ partial∞ derived open pair →

The 4 above are this entry’s hand-picked neighbours; the other 89 are everything else in the zoo, by category.

Known values

FunctionValueNotes
OR total \(\Theta(1)\) $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon)$, and $\mathrm{rdeg}_\varepsilon(\mathrm{OR}) = 1$. Postselection makes unstructured search free: prepare a uniform superposition, query once, and postselect on the answer bit being $1$. MahadevdeWolf15 Aaronson05postbqp
AND total \(\Theta(1)\) Dual to \(\mathrm{OR}_n\). MahadevdeWolf15
PARITY total \(\Theta(n)\) From $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon) = \Theta(n)$. Even $\mathsf{PostBQP}$ needs to read essentially the whole input. MahadevdeWolf15
MAJORITY total \(\Theta(\log n)\) Aaronson gave the first postselected majority algorithm; Mahadev-de Wolf made it optimal and observed that reading the algorithm backwards reproves Newman's theorem. MahadevdeWolf15 Aaronson05postbqp
Threshold total \(O(\log n)\) $\mathrm{PostQ}_{\varepsilon}(f) = \Theta(\mathrm{rdeg}_{\varepsilon}(f))$, and the \(\mathrm{rdeg}_{\varepsilon}(f)\) line above gives $O(\log n)$. Postselection collapses the whole threshold family to polylogarithmic cost, against $\mathrm{Q} = \Theta(\sqrt{k(n-k+1)})$. MahadevdeWolf15
EXACT-HALF total \(O(1)\) $\mathrm{PostQ}_{\varepsilon}(f) = \Theta(\mathrm{rdeg}_{\varepsilon}(f))$ [MahadevdeWolf15] applied to the \(\mathrm{rdeg}_{\varepsilon}(f)\) line: a postselecting quantum algorithm decides $\mathrm{EH}_n$ with $O(1)$ queries while $\mathrm{Q} = \Theta(n)$, the largest possible separation. MahadevdeWolf15
ODD-MAX-BIT total \(\Theta(1)\) $\mathrm{PostQ}_{\varepsilon}(f) = \Theta(\mathrm{rdeg}_{\varepsilon}(f))$ [MahadevdeWolf15], and $\mathrm{rdeg}_{\varepsilon} = 1$ on the \(\mathrm{rdeg}_{\varepsilon}(f)\) line. Postselection collapses OMB entirely, against $\mathrm{Q} = \Theta(\sqrt n)$ and $\mathrm{D} = n$ -- the largest gap in this file after \(\mathrm{EH}_n\). MahadevdeWolf15
ADDRESS / multiplexer total \(\Theta(k)\) $\mathrm{PostQ}_{\varepsilon}(f) = \Theta(\mathrm{rdeg}_{\varepsilon}(f)) = \Theta(k)$. MahadevdeWolf15
Binary tree navigation total \(\Theta(k)\) $\mathrm{PostQ}_{\varepsilon}(f) = \Theta(\mathrm{rdeg}_{\varepsilon}(f)) = \Theta(k)$. MahadevdeWolf15
TRIBES total \(O(\log n)\) $\mathrm{PostQ}_{\varepsilon}(f) = \Theta(\mathrm{rdeg}_{\varepsilon}(f))$ [MahadevdeWolf15] applied to the \(\mathrm{rdeg}_{\varepsilon}(f)\) line, hence an upper bound only. Postselection brings TRIBES from $\mathrm{R} = \Theta(n)$ down to at most $O(\log n)$. MahadevdeWolf15
AND-OR tree (depth 2) total \(O(n)\) $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon)$ [MahadevdeWolf15], and \(\mathrm{rdeg}_{\varepsilon}(f)\) gives $\mathrm{rdeg}_{1/3} = O(n)$. Whether post-selection beats the ordinary quantum $\Theta(n)$ on this function is open, since no lower bound on $\mathrm{rdeg}_{1/3}$ is known here. MahadevdeWolf15
NAND tree (balanced AND-OR formula) total \(O(\sqrt N)\) $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon) \le O(\mathrm{rdeg}) = O(\sqrt N)$ [MahadevdeWolf15]. Since $\mathrm{Q} = \Theta(\sqrt N)$ already, post-selection can save at most a constant factor unless $\mathrm{rdeg}_{1/3} \ll \mathrm{rdeg}$ here. MahadevdeWolf15
Recursive MAJORITY-of-3 total \(O(2^d)\) $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon)$ [MahadevdeWolf15] and $\mathrm{rdeg}_{1/3} \le \mathrm{rdeg} \le 2^d$; since $\mathrm{Q} = \Theta(2^d)$ already, post-selection saves at most a constant factor unless the approximate rational degree drops below the exact one. MahadevdeWolf15
Kushilevitz's function (iterated) total \(O(N^{0.6131})\) $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon)$ [MahadevdeWolf15], bounded by the \(\mathrm{rdeg}_{\varepsilon}(f)\) entry. MahadevdeWolf15
Rubinstein's function total \(O(\sqrt N)\) $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon)$ [MahadevdeWolf15] and $\mathrm{rdeg}_{1/3} \le \widetilde{\deg} = O(\sqrt N)$; since $\mathrm{Q} = \Theta(\sqrt N)$, post-selection saves at most a constant factor unless the approximate rational degree collapses further. MahadevdeWolf15
Ambainis-Sun function total \(O(N^{3/4})\) $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon) \le O(\widetilde{\deg}) = O(N^{3/4})$ [MahadevdeWolf15]. MahadevdeWolf15
AND composed with NOT-EXACT-HALF total \(O(n) = O(\sqrt N)\) $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon)$ [MahadevdeWolf15], and $\mathrm{rdeg}_{1/3} \le \mathrm{rdeg} = \Theta(n)$. So post-selection gives a genuine polynomial speed-up over ordinary quantum queries on this function: $O(\sqrt N)$ against $\mathrm{Q} = \Theta(N^{3/4})$. MahadevdeWolf15 IJKKKSWW23
Meiburg's tournament-subcube function total \(O(7923.9^{\,d})\) putative $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon)$ [MahadevdeWolf15], bounded by the \(\mathrm{rdeg}_{\varepsilon}(f)\) entry. Contrast the recorded $\mathrm{Q} = \Omega(118.3^{\,d})$: post-selection is not known to help or hurt on this family. MahadevdeWolf15
Pointer functions total \(\widetilde O(n^{1/4})\) Variant $\tilde h_{1,m,m}$: $\mathrm{PostQ}_\varepsilon=\Theta(\mathrm{rdeg}_\varepsilon)$ [MahadevdeWolf15] applied to the $\mathrm{ardeg}$ line. Post-selection buys nothing beyond bounded-error quantum here. MahadevdeWolf15
Cheat-sheet functions total \(\widetilde O(\sqrt n)\) Squeeze: $\mathrm{PostQ}_\varepsilon=\Theta(\mathrm{rdeg}_\varepsilon)$ [MahadevdeWolf15] applied to the $\mathrm{ardeg}$ line. Against $\mathrm{Q}=\widetilde\Theta(n)$ this is a total function on which post-selection gives a quadratic speedup over bounded-error quantum queries. MahadevdeWolf15
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde O(n^{2/3})\) Squeeze: $\mathrm{PostQ}_\varepsilon=\Theta(\mathrm{rdeg}_\varepsilon)$ [MahadevdeWolf15] applied to the $\mathrm{ardeg}$ line. Against $\mathrm{C}=\widetilde\Theta(n^2)$ this is a cubic $\mathrm{C}$-vs-$\mathrm{PostQ}$ gap. MahadevdeWolf15
Goos-Pitassi-Watson partition-number function total \(\widetilde O(\sqrt n)\) Squeeze: $\mathrm{PostQ}_\varepsilon=\Theta(\mathrm{rdeg}_\varepsilon)$ [MahadevdeWolf15] applied to the $\mathrm{ardeg}$ line, giving a quadratic $\mathrm{D}$-vs-$\mathrm{PostQ}$ gap. MahadevdeWolf15
Goos-Jayram-Pitassi-Watson function total \(\widetilde O(n^{1/3})\) Squeeze: $\mathrm{PostQ}_\varepsilon=\Theta(\mathrm{rdeg}_\varepsilon)$ [MahadevdeWolf15] applied to the $\mathrm{ardeg}$ line; against $\mathrm{R}=\widetilde\Theta(n^{2/3})$ this is a quadratic $\mathrm{R}$-vs-$\mathrm{PostQ}$ gap. MahadevdeWolf15
Ambainis' exact-quantum function total \(O(2^d)\) Squeeze: $\mathrm{PostQ}_\varepsilon=\Theta(\mathrm{rdeg}_\varepsilon)$ [MahadevdeWolf15] and $\mathrm{rdeg}_{1/3}\le\deg=2^d$. Not enough to decide whether post-selection beats $\mathrm{Q}=\Theta(2.1213^d)$ on this function, which would need a rational approximation genuinely below the real degree. MahadevdeWolf15
FORRELATION partial \(\Theta(1)\) $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon) = \Theta(1)$. Post-selection is of no use on a problem already solved by one query.
k-FORRELATION partial \(O(k)\) $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon) = O(k)$: post-selection is worth no more than $O(k)$ queries here, while randomness is worth $\widetilde\Theta(n^{1-1/k})$.
Simon's problem partial \(O(n)\) $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon) = O(n)$.
Deutsch-Jozsa partial \(\Theta(1)\) $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon) = \Theta(1)$.
Marked bit partial \(\Theta(1)\) $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon) = \Theta(1)$: guess a cell, read it, postselect on it being marked. MahadevdeWolf15
Dense marked bit partial \(\Theta(1)\) $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon) = \Theta(1)$. MahadevdeWolf15
Unstructured search (relation) relation \(\Theta(1)\)· putative Postselection trivialises search. Prepare $\sum_{i} \alpha_i |i\rangle + \varepsilon|\bot\rangle$ with $\alpha_i = n^{-1/2}$, query $x_i$ into a flag qubit (flag $= x_i$ on the $|i\rangle$ branches, flag $= 1$ on the $|\bot\rangle$ branch), and postselect on flag $= 1$. With $\varepsilon = 1/n$ the surviving state is a uniform superposition over $\{i : x_i = 1\}$ plus a $|\bot\rangle$ component of weight $\varepsilon^2/(\varepsilon^2 + |x|/n) \le 1/n$, so on any $x \ne 0^n$ the measurement returns a valid index, and on $x = 0^n$ only $|\bot\rangle$ survives. One query. Against $\mathrm{R} = \Theta(n)$ and $\mathrm{Q} = \Theta(\sqrt n)$ this is an unbounded gap. MahadevdeWolf15
FIND-1 under a density promise relation \(\Theta(1)\) At most $\mathrm{Q} = \Theta(1)$, and at least $1$: there is nothing for postselection to buy.
Approximate Hamming weight relation \(\Theta(1)\) At most $\mathrm{Q} = \Theta(1)$, and at least $1$.
SearchCNF relation \(\Theta(1)\) At most $\mathrm{Q} = \Theta(1)$, and at least $1$.
Gap-Majority partial \(O(\min(n, 1/\delta))\) $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon) = O(\min(n,1/\delta))$; postselection does not obviously help a problem that amplitude estimation already solves at that cost. MahadevdeWolf15
Gap-Majority at constant gap partial \(O(1)\) $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon) = O(1)$. MahadevdeWolf15
Parity-labelled FIND-1 partial \(\Theta(1)\) At most $\mathrm{Q} = \Theta(1)$, and at least $1$.
Approximate index partial \(\Theta(1)\) $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon) = \Theta(1)$. A postselecting algorithm guesses a cell, reads it, and postselects on not seeing $2$ -- against $\mathrm{R} = \Theta(\sqrt{k\log k})$ this is an unbounded gap, and it is the mirror image of the $\mathrm{noisyR}$ story: both models can afford to guess the address. MahadevdeWolf15
Collision problem partial \(O(n^{1/3})\) $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon) = O(n^{1/3})$. MahadevdeWolf15
Element distinctness total \(O(n^{2/3})\) $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon) = O(n^{2/3})$; post-selection buys nothing beyond the ordinary quantum walk here. MahadevdeWolf15
Ambainis-Belovs function partial \(O(1)\) $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon) = O(1)$ against $\mathrm{Q} = \Omega(n^{1/3})$. Post-selection is not the resource being separated -- rather, every polynomial-flavoured measure is blind to this function, which is precisely the failure of the polynomial method that [AmbainisBelovs23] exhibits. MahadevdeWolf15
Yamakawa-Zhandry problem relation \(\mathrm{poly}(n)\) At most $\mathrm{Q} = \mathrm{poly}(n)$: postselection can only help, so the exponential quantum advantage survives in this model too.
Surjectivity total \(\tilde\Omega(\sqrt n),\ \tilde O(n^{3/4})\) $\mathrm{PostQ}_\varepsilon(f)=\Theta(\mathrm{rdeg}_\varepsilon(f))$ [MahadevdeWolf15], and the \(\mathrm{rdeg}_{\varepsilon}(f)\) entry places approximate rational degree between $\tilde\Omega(\sqrt n)$ and $\tilde O(n^{3/4})$. MahadevdeWolf15
$k$-distinctness total \(O\!\big(n^{3/4 - 1/(4(2^k-1))}\big)\) $\mathrm{PostQ}_\varepsilon=\Theta(\mathrm{rdeg}_\varepsilon)$ [MahadevdeWolf15]; see \(\mathrm{rdeg}_{\varepsilon}(f)\). Equivalently, post-selection is at least as strong as the plain quantum algorithm, whose cost is $\Theta(n^{3/4-1/(4(2^k-1))})$. MahadevdeWolf15
Triangle finding total \(O(m^{5/4})\) $\mathrm{PostQ}_\varepsilon=\Theta(\mathrm{rdeg}_\varepsilon)$ [MahadevdeWolf15]; see \(\mathrm{rdeg}_{\varepsilon}(f)\). Post-selection is in particular at least as strong as the $O(m^{5/4})$ quantum walk. MahadevdeWolf15
Recursive Fourier sampling partial \(O(2^{\ell})\) Post-selection can only help, so $\mathrm{PostQ}\le\mathrm{Q}=\Theta(2^{\ell})$; equivalently $\mathrm{PostQ}_\varepsilon=\Theta(\mathrm{rdeg}_\varepsilon)$ [MahadevdeWolf15] and \(\mathrm{rdeg}_{\varepsilon}(f)\) is $O(2^{\ell})$. MahadevdeWolf15
Welded trees relation \(O(n)\) Post-selection can only help, so $\mathrm{PostQ}\le\mathrm{Q}=\Theta(n)$. Whether it helps at all here is open; the quantum walk already runs in linear time.
Local search on the hypercube relation \(O(2^{n/3}n^{1/6})\) Post-selection can only help, so $\mathrm{PostQ}\le\mathrm{Q}=\Theta(2^{n/3}n^{1/6})$.
Local search on the grid relation \(O(k^{d/3})\ (d \ge 6)\) Post-selection can only help, so $\mathrm{PostQ}\le\mathrm{Q}=\Theta(k^{d/3})$.
Fourier fishing relation \(\Theta(1)\) $1\le\mathrm{PostQ}\le\mathrm{Q}=1$: one Fourier sample already solves the problem, and no problem with a nonconstant answer is solved with zero queries. Post-selection has nothing left to buy -- the interest of this family is entirely on the classical side.
Ordered search partial \(\Theta(1)\) $\mathrm{PostQ}_\varepsilon=\Theta(\mathrm{rdeg}_\varepsilon)=\Theta(1)$ [MahadevdeWolf15]. Post-selection collapses ordered search: $\mathrm{Q}=\Theta(\log n)$ but a post-selected algorithm needs only a constant number of queries. MahadevdeWolf15
Tseitin search on an expander relation \(O(\sqrt n)\) Post-selection can only help, so $\mathrm{PostQ}\le\mathrm{Q}=O(\sqrt n)$.
Inner product mod 2 total \(\Theta(n)\) $\mathrm{PostQ}_{\varepsilon}(f) = \Theta(\mathrm{rdeg}_{\varepsilon}(f))$ [MahadevdeWolf15], and the approximate rational degree is $\Theta(n)$ here. MahadevdeWolf15
Minsky-Papert one-in-a-box total \(\Omega(m),\ O(m^{3/2})\) $\mathrm{PostQ}_{\varepsilon}(f) = \Theta(\mathrm{rdeg}_{\varepsilon}(f))$ [MahadevdeWolf15], and the approximate rational degree sits in $[\Omega(m), O(m^{3/2})]$ here; see \(\mathrm{rdeg}_{\varepsilon}(f)\). So it is open whether post-selection beats plain quantum on the one-in-a-box function, and the whole question is the constant-vs-$\sqrt m$ gap in that window. MahadevdeWolf15