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
- \(\mathrm{rdeg}_{\varepsilon}(f)\) $\mathrm{PostQ}_\varepsilon(f)=\Theta(\mathrm{rdeg}_\varepsilon(f))$ -- bounded error on both sides MahadevdeWolf15 IJKKKSWW23
- \(\mathrm{rdeg}(f)\) $\mathrm{PostQ}_{\mathrm{E}}(f) = \Theta(\mathrm{rdeg}(f))$ -- the exact-error versions of both. Not an equivalence between $\mathrm{PostQ}_{1/3}$ and $\mathrm{rdeg}_0$, which are genuinely different quantities. MahadevdeWolf15 IJKKKSWW23
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.
The 4 above are this entry’s hand-picked neighbours; the other 89 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| 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 |