Computational Complexity · arXiv:2611.16412 v1 · submitted 12 Nov 2026 · 26 references
Exact Quantum Algorithms for Composed Boolean Functions
The paper says
“We study exact quantum algorithms for block compositions of total Boolean functions.”
more of the abstract
For an outer function f of degree D and an inner function g on m bits, we prove $$ Q_E(f\circ g)=O\!\left(mD+Q_E(f)Q_{1/(4D)}(g)\right). $$ The algorithm combines approximate inner evaluations with a finite exact correction. Its two costs are governed by different parameters of the outer function: exact query complexity determines the cost of simulation, whereas polynomial degree determines the number of inner blocks used in the correction. We first establish the construction with an arity-dependent error threshold and then obtain the degree-dependent threshold above. For recursive ternary not-all-equal, this gives an exact algorithm using (3/√2)k(1 + o(1)) queries asymptotically. More generally, for every fixed nonconstant total gadget h, we determine the exact recursive rate as max{deg(h),Adv±(h)} and prove $Q_E(h^{\circ k})=\widetilde O_h(R(h^{\circ k})^2)$. The composition limit also allows to transfer separations from Qε and deg to exact quantum query complexity QE (similar to fractional block sensitivity to block sensitivity transfer in Tal and Kulkarni 2016, Chicago Journal of Theoretical Computer Science). We construct a family with s = bs = fbs ≥ QE3/2−o(1), improving the previous exponent 1.1527…. A second construction gives R ≥ QE2−o(1), improving the previous exponent 3/2. We also allow different inner functions and give analogous quantitative separations in quantum communication.
from the abstract
Pith says
Machine review · deepseek-v4-flash · 13 Nov 2026 · what was read was not recorded · not checked by a person
It can be wrong. Challenge this review or reply to it.
Holds up. Strong paper: general composition theorem for exact quantum query complexity, improved separations, rigorous proofs. Soft spots are openly discussed and minor. This line is wrong
3 major objections · 6 minor
How often objections from reviews like this one are right: not yet measured
Not checked: figures, code, what the 26 references say.
The paper says, at §4.5, Eq. (4.14)
The review did not quote this passage.
Pith says: Objection 1 of 3 · major
The construction for implementing the truncated operator expansion assumes that each positive-order factor's dilation can be applied with cost 2m queries by reading the selected input block. However, the dilation matrix D(K_{u,k}) depends on K_{u,k}, which in turn depends on the error probability p_u and the state |r_u⟩ (see §4.2).
more of objection 1
The authors state that this table is fixed in advance and that controlled application is input-independent once the string u is known. This is correct in the query model, but the description could be clarified: the dilation for each possible u and k is precomputed, and the query to u is used to select the appropriate unitary. The cost analysis (2m per positive-order factor) is sound and standard. I find no issue here.
This objection may describe the copy Pith gave the reviewer, not the paper.
The paper says, at §4.4, Lemma 4.4
The review did not quote this passage.
Pith says: Objection 2 of 3 · major
The proof that the return amplitude P_x(λ) equals H(b+λe) relies on the joint spectral decomposition of commuting reflections V_i(λ). Since the V_i(λ) act on disjoint registers and each is Hermitian, they indeed commute and share a simultaneous eigenbasis. The averaging over signs is then justified by the initial product state. This reasoning is correct and elegantly avoids analyzing the operator expansion directly.
The paper says, at §6.1, Eq. (6.6)
The review did not quote this passage.
Pith says: Objection 3 of 3 · major
The recurrence T_d ≤ C (δ^k r^{d-k} + k T_k A^{d-k}) is derived from Theorem 4.1, but the constant C and the factor k in the second term need justification. From Theorem 4.1, the additive term is 12 Q_E(F_k) Q_{1/(4 deg(F_k))}(H_ℓ).
more of objection 3
Using Q_E(F_k)=T_k and deg(F_k)=δ^k, and the error reduction cost for H_ℓ is O(k A^ℓ) (since log(1/ε)=O(k) and Q(H_ℓ)=Θ(A^ℓ)), we get factor k from log(1/ε). The constant C can be chosen to absorb the O(k) factor and the constants from error reduction. This is valid and standard; the induction then handles the growth. The paper's analysis is sound.
6 minor objections
The paper says, at §3.2, Eq. (3.3)
Pith says: minor objection 1 of 6
The Taylor expansion (3.3) uses ∂_S H(b) without factorial factors because H is multilinear. It might be helpful to explicitly note that ∂_S H(b) = Σ_{T⊇S} Ĥ(T) b^{T\S}, which is indeed the coefficient without factorial. The current text says 'There are also no factorials, since a variable occurs at most once in each monomial.' This is clear enough.
The paper says, at §3.3, proof of Lemma 3.3
Pith says: minor objection 2 of 6
The construction B_S is described as a tensor product of A_i (for i∉S) and Hadamard gates (for i∈S). However, the Hadamard gate on the answer qubit q_i produces the uniform superposition state, which gives Y_i = ±1 with equal probability. This matches the distribution needed in Lemma 3.2. The verification that P_S = ∏_{i∈S} Z_{q_i} provides the correct parity is correct. The query-by-query implementation is clearly explained.
show 4 more
The paper says, at §4.5, line after Eq. (4.15)
Pith says: minor objection 3 of 6
The computation of L uses the bound (1 + Σ w_k)^{T} ≤ e^{16 E_f √ε}. Since T = 2E_f, this is e^{2E_f ln(1+8√ε)} ≤ e^{2E_f * 8√ε} = e^{16 E_f √ε}. With ε = 1/(1024 E_f^2), √ε = 1/(32 E_f), so the exponent is 16/32 = 1/2.
more of objection 3
This is correct. However, the step 'using the uniform majorant from Lemma 4.3' implicitly assumes that the wk are the same for all positions, which is true as they depend only on ε. The sum over k≥1 wk ≤ 8√ε is from Lemma 4.3. The inequality (1+8√ε)^T ≤ exp(8√ε T) uses (1+x)≤e^x; 8√ε T = 8*(1/(32 E_f))*2E_f = 8/16 = 1/2. So L ≤ e^{1/2} < 2. This is correct.
The paper says, at §5, Eq. (5.2)
Pith says: minor objection 4 of 6
The recurrence uses the factor k (from error reduction) multiplied by E_k A^{d-k}. The constant C is absolute. Later, in the induction (5.4), the factor d appears (since k ≈ β d). The analysis correctly accounts for the depth-dependent overhead.
The paper says, at §6.1, last paragraph before §6.2
Pith says: minor objection 5 of 6
The induction for the degree-dominated case uses the choice ℓ = ⌈ log(2Cd) / log(δ/A) ⌉ and shows u_d ≤ C_2 (d+1)^p + ½ u_{d-ℓ}. This is standard. The induction base is chosen large enough. The bound is correct.
The paper says, at §8, Eq. (8.6)
Pith says: minor objection 6 of 6
The claim that s(G_k) = N_k uses that each input bit is sensitive at zero. This holds because flipping any bit in any OR block changes that OR output, and F_k is fully sensitive at zero to changes in the outer bits. The reasoning is sound.
What would settle it
Reproduce Theorem 4.1's operator expansion for a concrete small case, e.g., f=AND_2 on n=2 bits (deg=2, Ef=2) and g=OR_2 on m=2 bits. Implement the truncated circuit as described (with error threshold 1/(1024·4)=1/4096) and verify by simulation or analysis that the return amplitude equals (-1)^{f∘g(x)} exactly for all 4 inputs. If the construction fails on any input, the interpolation argument in §4.4 would be invalid.
from the skeptic's reading
How the review went
4 readings by deepseek-v4-flash · 13 Nov 2026
- Reader holds up
- Skeptic agrees
- Editor wrote the verdict above
- Referee accept: 3 major objections, 6 minor
Not run on this paper: the simulated authors' defence.
Pith did not check this review's objections against the paper.
The review in full
The review in brief, machine-written
This is a serious piece of work. The core result is a composition theorem for exact quantum query complexity that separates the cost of simulating the outer algorithm from the cost of correcting approximate inner evaluations. The degree-dependent error threshold (Theorem 4.1) is clever and yields a unified framework that determines the exact recursive rate for any fixed gadget. The payoffs are real: the sensitivity vs QE exponent moves from 1.1527 to 3/2, and the randomized vs QE exponent goes from 1.5 to nearly 2. The transfer principles cleanly convert these single-gadget gains into universal statements. The communication applications are a nice bonus.
The paper earns its length. The constructions are worked out in detail, the counting arguments are solid, and the authors are honest about what remains open. They explicitly flag the obstacle to replacing m by QE(g) in the correction cost (§12) and acknowledge the polylog overhead in some recursive bounds. They also give an open problem that would settle the tight complexity for recursive NAE. The AI statement is transparent and doesn't affect the science.
My only caveat is a disappointment rather than a flaw: the correction cost still reads full inner blocks rather than exploiting an exact inner algorithm. The authors know this and leave it as a conjecture. The paper also depends on [22] (Pednekar–Podder), an unpublished manuscript, but the authors provide their own derivation and do not rely on it for load-bearing claims. The clean-phase assumption is standard and the factor-2 overhead is accounted for.
This paper is for the query complexity community. It advances the state of the art and will be a reference for composition and separations. It deserves a serious referee and, after a normal review, should be accepted.
The strongest objection
After careful review, I find no unresolved load-bearing concern. The central composition bounds (Theorems 3.1 and 4.1) are supported by rigorous constructions that account for the clean-phase requirement (standard, with factor-2 overhead, explicitly noted in §2.1), the use of approximate inner evaluations, the exact algebraic correction, and the norm bounds. The recursive applications and separation results follow logically from these bounds. The AI statement is noted but does not affect correctness. The paper's own limitations (§12) discuss open improvements rather than gaps. I cannot identify a concrete technical flaw that would undermine the central claims.
The reader's verdict (ACCEPT, high confidence, medium correctness risk) aligns with my analysis. The weakest assumption identified (clean-phase outer algorithm) is standard and explicitly handled via factor-2 overhead. The paper provides detailed proofs, explicit constructions, and acknowledges its own limitations. I find no internal inconsistency or missing step that would warrant a different verdict.
The referee's report
If the results are correct, they represent a substantial advance in exact quantum query complexity. The composition theorem is the first to exploit degree rather than exact query complexity for the correction cost, leading to optimal recursive rates for any gadget. The separations improve long-standing bounds in query and communication complexity. The transfer principles provide a clean criterion for universal bounds, unifying several known results. The proofs are rigorous and detailed, using established tools but delivering new algorithmic constructions.
Pith's reading of the paper (a machine's summary, not the authors')
This paper establishes that the exact quantum query complexity of a composed Boolean function $f \circ g$ can be bounded by $O(m \deg(f) + Q_E(f) Q_{1/(4 \deg(f))}(g))$, where the first term pays for reading a few inner blocks to correct errors, and the second pays for simulating the outer algorithm with approximate inner queries. The authors develop two constructions: one using a Taylor expansion in the biases of approximate inner algorithms, and one using an operator interpolation whose return amplitude is a polynomial of degree at most $\deg(f)$. This leads to exact algorithms for recursive functions whose exponential growth rate is exactly $\max\{\deg(h), \operatorname{Adv}^{\pm}(h)\}$. Using these tools, the authors derive transfer principles that convert gadget-level inequalities into universal exact-query bounds, and construct explicit families: one separating sensitivity (and block sensitivity) from exact quantum queries with exponent $3/2$, improving the previous $1.1527\ldots$ exponent, and another separating randomized query complexity from exact quantum queries with exponent $2 - o(1)$, improving the previous $3/2$ exponent. The results apply also to quantum communication via AND lifts and inner-product lifts.
What carries the argument. The main machinery is a composition algorithm that first uses an approximate quantum algorithm for the inner function $g$ with error $\varepsilon = 1/(4\deg(f))$, then corrects the resulting bias coherently using an exact multilinear expansión of the outer function $f$. The correction reads at most $\deg(f)$ inner blocs entirely (cost $O(m \deg(f))$) and combines them via a suposición with input-independent weights. A second construction interpolates the inner reflection operators and truncates the Taylor series at order $\deg(f)$; the return amplitude is exactly $H(b+\lambda(z-b)$, a polynomial of degree $\deg(f)$. Both methods use exact amplitude amplification to convert the known magnitude amplitude into the exact phase.
Core claim. The paper proves that for any nonconstant total Boolean functions $f$ on $n$ bits and $g$ on $m$ bits, $Q_E(f \circ g) = O(m \deg(f) + Q_E(f) Q_{1/(4 \deg(f))}(g))$, and this allows exponential exact quantum improvements for recursive functions. For a fixed nonconstant $h$, the exact quantum query complexity of $h^{\circ k}$ grows as $\max\{\deg(h), \operatorname{Adv}^{\pm}(h)\}^k$ up to subexponential factors, giving a composition limit. This is used to prove transfer principles: a universal bound $L(F) = O(Q_E(F)^\alpha)$ for a composable measure $L$ holds iff $L(f) \leq \max\{\deg(f), \operatorname{Adv}^{\pm}(f)\}^\alpha$ for all $f$. The paper then constructs explicit total Boolean functions that achieve improved separations: $s = \operatorname{bs} = \operatorname{fbs} \geq Q_E^{3/2 - o(1)}$ (exponent $3/2$), and $R \geq Q_E^{2 - o(1)$ (near quadratic randomized-exact gap). These separations carry over to quantum communication complexity.
The premise it rests on. The construction assumes that the outer function f has an exact quantum algorithm that returns a clean phase, which can always be achieved with a factor-2 overhead, and that the inner algorithm g can be run with error probability at most 1/(4 deg(f)).
If the paper is right (Pith's inferences, not the authors')
For any recursive function $h^{\circ k}$, the exact quantum query complexity is $\tilde O_h(R(h^{\circ k})^2)$, so bounded-error randomized query complexity gives a quadratic upper bound on exact quantum query complexity for these iterated functions.
The transfer principle reduces many universal exact-query lower bound problems to checking a finite condition on individual gadgets; for example, $s(F) = O(Q_E(F)^\alpha)$ for all $F$ iff $\operatorname{fbs}(f) \leq \max\{\deg(f), \operatorname{Adv}^{\pm}(f)\}^\alpha$ for all $f$.
The exponent-$3/2$ separation between sensitivity and exact quantum queries (and the nearly quadratic separation between randomized and exact quantum queries) are the strongest known, and the methods suggest possible routes to further improvements.
In quantum communication complexity, the same techniques yield analogous separations: $R^{cc}_{1/3}(HG_k) \geq (Q^{cc}_E(HG_k))^{3/2 - o(1)}$ and $R^{cc}_{1/3} \geq (Q^{cc}_E)^{2 - o(1)}$ for appropriate families.
The bound $Q_E(f \circ g) = O(m \deg(f) + Q_E(f) Q_{1/(4\deg(f))}(g))$ suggests that the naive multiplicative simulation $Q_E(f \circ g) = \Theta(Q_E(f)Q_E(g))$ can be broken whenever $\deg(f)$ is small compared to $Q_E(f)$ and $g$ has efficient approximate algorithms. This opens the door to many non-multiplicative compositions.
The transfer principles imply that proving a universal quadratic bound $Q_E(F) = O(R(F)^2)$ for all total $F$ would be equivalent to proving $\max\{\deg(f), \operatorname{Adv}^{\pm}(f)\} = O(R(f))$ for all $f$, which is already known up to constants; thus the quadratic bound might hold universally, but the proof would need to avoid the fixed-gadget restriction.
The cheat-sheet gadget together with the recursive exact algorithm provides a template for constructing total functions with near-quadratic randomized-exact quantum gap. The remaining polylogarithmic loss might be removable by a more direct exact correction that does not read entire inner blocks, perhaps using an exact inner algorithm instead of approximate one.
Check this review
Pith stored no record of this review's passes and took no fingerprint of it. Reviews made by code from 13 Nov 2026 on carry both.
How often reviews like this one are right
Reviews like this one: written by deepseek-v4-flash, where what was read was not recorded.
How often objections from reviews like this one are right: not yet measured
Reviews by people
This review was written by a machine. No person has reviewed this paper on Pith yet. A scientist listed on Pith can review it for a fee, and their review is published here whatever it concludes.
The paper
Abstract
We study exact quantum algorithms for block compositions of total Boolean functions. For an outer function f of degree D and an inner function g on m bits, we prove $$ Q_E(f\circ g)=O\!\left(mD+Q_E(f)Q_{1/(4D)}(g)\right). $$ The algorithm combines approximate inner evaluations with a finite exact correction. Its two costs are governed by different parameters of the outer function: exact query complexity determines the cost of simulation, whereas polynomial degree determines the number of inner blocks used in the correction. We first establish the construction with an arity-dependent error threshold and then obtain the degree-dependent threshold above. For recursive ternary not-all-equal, this gives an exact algorithm using (3/√2)k(1 + o(1)) queries asymptotically. More generally, for every fixed nonconstant total gadget h, we determine the exact recursive rate as max{deg(h),Adv±(h)} and prove $Q_E(h^{\circ k})=\widetilde O_h(R(h^{\circ k})^2)$. The composition limit also allows to transfer separations from Qε and deg to exact quantum query complexity QE (similar to fractional block sensitivity to block sensitivity transfer in Tal and Kulkarni 2016, Chicago Journal of Theoretical Computer Science). We construct a family with s = bs = fbs ≥ QE3/2−o(1), improving the previous exponent 1.1527…. A second construction gives R ≥ QE2−o(1), improving the previous exponent 3/2. We also allow different inner functions and give analogous quantitative separations in quantum communication.
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. No sentence in this record was written by a model.
abstract compiled · 2026-11-13
The authors' main claim, as the classifier picked it out 0.92
“For an outer function $f$ of degree $D$ and an inner function $g$ on $m$ bits, we prove $$ Q_E(f\circ g)=O\!\left(mD+Q_E(f)Q_{1/(4D)}(g)\right).”
How the main claim is stated: asserted 1.00
What the abstract itself states, as probabilities: claims first 0.07 · states limitation 0.16 · human participants 0.01 · controlled comparison 0.03 · randomized assignment 0.01 · states quantitative result 0.98 · compares with prior results 0.96 · mentions code or data availability 0.02
The abstract, sentence by sentence
This table labels the abstract only (arXiv listing abstract v1). The number is the probability the classifier gave the label.
| Sentence | Role | The authors' own work | States the main conclusion | Strength |
|---|---|---|---|---|
| We study exact quantum algorithms for block compositions of total Boolean functions. | contribution 0.62 | 0.75 | 0.05 | asserted 0.55 |
| For an outer function $f$ of degree $D$ and an inner function $g$ on $m$ bits, we prove $$ Q_E(f\circ g)=O\!\left(mD+Q_E(f)Q_{1/(4D)}(g)\right). | result 0.99 | 0.94 | 0.72 | asserted 1.00 |
| $$ The algorithm combines approximate inner evaluations with a finite exact correction. | method 1.00 | 0.87 | 0.06 | asserted 1.00 |
| Its two costs are governed by different parameters of the outer function: exact query complexity determines the cost of simulation, whereas polynomial degree determines the number of inner blocks used in the correction. | interpretation 0.70 | 0.89 | 0.11 | asserted 1.00 |
| We first establish the construction with an arity-dependent error threshold and then obtain the degree-dependent threshold above. | method 0.96 | 0.93 | 0.05 | asserted 1.00 |
| For recursive ternary not-all-equal, this gives an exact algorithm using $(3/\sqrt2)^{k(1+o(1))}$ queries asymptotically. | result 1.00 | 0.93 | 0.07 | asserted 1.00 |
| More generally, for every fixed nonconstant total gadget $h$, we determine the exact recursive rate as $\max\{\textrm{deg}(h),\operatorname{Adv}^{\pm}(h)\}$ and prove $Q_E(h^{\circ k})=\widetilde O_h(R(h^{\circ k})^2)$. | result 0.97 | 0.95 | 0.21 | asserted 1.00 |
| The composition limit also allows to transfer separations from $Q_{\varepsilon}$ and $\deg$ to exact quantum query complexity $Q_E$ (similar to fractional block sensitivity to block sensitivity transfer in Tal and Kulkarni 2016, Chicago Journal of Theoretical Computer Science). | interpretation 0.90 | 0.73 | 0.10 | asserted 0.88 |
| We construct a family with $s=\operatorname{bs}=\operatorname{fbs}\ge Q_E^{3/2-o(1)}$, improving the previous exponent $1.1527\ldots$. | result 0.97 | 0.95 | 0.08 | asserted 1.00 |
| A second construction gives $R \ge Q_E^{2-o(1)}$, improving the previous exponent $3/2$. | result 0.96 | 0.95 | 0.08 | asserted 1.00 |
| We also allow different inner functions and give analogous quantitative separations in quantum communication. | contribution 0.79 | 0.93 | 0.05 | asserted 0.96 |
What kind of paper the classifier reports this is: theoretical result 0.91 · evidence from proof or derivation 1.00
What was examined, and what was not
Sources read
- arXiv listing abstract v1
Not examined
- full text
- figures and tables
- references and citing sentences
- relations to other papers
Levels run
- P abstract
Not run
- S sections
- T body sentences
- C citations
- R cross-paper relations
How the labels were made
Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-11-13: 1 request, 8,470 input tokens.
Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. This record as JSON
References (26)
- [1] S. Aaronson, S. Ben-David, and R. Kothari. Separations in query complexity using cheat sheets. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 863–876. ACM, 2016. doi: 10.1145/2897518.2897644. URLhttps://arxiv.org/abs/1511.01937v2. T... on PithPith's reviewarXiv
- [2] B. Al-Dhalaan and S. Ben-David. Monte carlo to las vegas for recursively composed functions. arXiv:2601.08073, 2026. URLhttps://arxiv.org/abs/2601.08073 on PitharXiv
- [3] A. Ambainis. Superlinear advantage for exact quantum algorithms. InProceedings of the Forty- Fifth Annual ACM Symposium on Theory of Computing (STOC), pages 891–900. ACM, 2013. doi: 10.1145/2488608.2488721. URLhttps://doi.org/10.1145/2488608.2488721 on Pithdoi:10.1145/2488608.2488721
- [4] A. Ambainis. Superlinear advantage for exact quantum algorithms.SIAM Journal on Computing, 45(2): 617–631, 2016. doi: 10.1137/130939043. URLhttps://arxiv.org/abs/1211.0721v6 on PithPith's reviewarXiv
- [5] A. Ambainis, K. Balodis, A. Belovs, T. Lee, M. Santha, and J. Smotrovs. Separations in query complexity based on pointer functions.Journal of the ACM, 64(5), 2017. doi: 10.1145/3106234. URL https://arxiv.org/abs/1506.04719. Article 32 on PithPith's reviewarXiv
- [6] A. Anshu, A. Belovs, S. Ben-David, M. Göös, R. Jain, R. Kothari, T. Lee, and M. Santha. Separations in communication complexity using cheat sheets and information complexity. InProceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 555–5... on PithPith's reviewarXiv
- [7] R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf. Quantum lower bounds by polynomials. Journal of the ACM, 48(4):778–797, 2001. doi: 10.1145/502090.502097. URLhttps://arxiv.org/abs/ quant-ph/9802049 on PithPith's reviewarXiv
- [8] S. Ben-David and R. Kothari. Randomized query complexity of sabotaged and composed functions. Theory of Computing, 14(5):1–27, 2018. doi: 10.4086/toc.2018.v014a005. URLhttps://theoryofcomp uting.org/articles/v014a005/ on Pithdoi:10.4086/toc.2018.v014a005
- [9] G. Brassard, P. Høyer, M. Mosca, and A. Tapp. Quantum amplitude amplification and estimation. In S. J. Lomonaco, Jr. and H. E. Brandt, editors,Quantum Computation and Information, volume 305 of Contemporary Mathematics, pages 53–74. American Mathematical Society, 2002. doi: 10... on PithPith's reviewarXiv
- [10] H. Buhrman and R. de Wolf. Communication complexity lower bounds by polynomials. InProceedings of the 16th Annual IEEE Conference on Computational Complexity (CCC), pages 120–130. IEEE, 2001. doi: 10.1109/CCC.2001.933879. URLhttps://arxiv.org/abs/cs/9910010 on PithPith's reviewarXiv
- [11] H. Buhrman and R. de Wolf. Complexity measures and decision tree complexity: A survey.Theoretical Computer Science, 288(1):21–43, 2002. doi: 10.1016/S0304-3975(01)00144-X. URLhttps://homepage s.cwi.nl/~rdewolf/publ/other/tcs.pdf on Pithdoi:10.1016/s0304-3975(01)00144-x
- [12] H. Buhrman, R. Cleve, and A. Wigderson. Quantum vs. classical communication and computation. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing (STOC), pages 63–68. ACM, 1998. doi: 10.1145/276698.276713. URLhttps://arxiv.org/abs/quant-ph/9802040 on PithPith's reviewarXiv
- [13] H. Buhrman, R. Cleve, R. de Wolf, and C. Zalka. Bounds for small-error and zero-error quantum algorithms. InProceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 358–368. IEEE, 1999. doi: 10.1109/SFFCS.1999.814607. URLhttps://arxiv.org/... on PithPith's reviewarXiv
- [14] A. Chattopadhyay, Y. Filmus, S. Koroth, O. Meir, and T. Pitassi. Query-to-communication lifting using low-discrepancy gadgets.SIAM Journal on Computing, 50(1):171–210, 2021. doi: 10.1137/19M1310153. URLhttps://arxiv.org/abs/1904.13056 on PithPith's reviewarXiv
- [15] R. de Wolf. A note on quantum algorithms and the minimal degree ofε-error polynomials for symmetric functions. arXiv:0802.1816v2, 2008. URLhttps://arxiv.org/abs/0802.1816v2 on PithPith's reviewarXiv
- [16] J. Gilmer, M. Saks, and S. Srinivasan. Composition limits and separating examples for some Boolean function complexity measures. arXiv:1306.0630, 2013. URL https://arxiv.org/abs/1306.0630 . Conference version in CCC 2013 on PithPith's reviewarXiv
- [17] H. Huang. Induced subgraphs of hypercubes and a proof of the sensitivity conjecture.Annals of Mathematics, 190(3):949–955, 2019. doi: 10.4007/annals.2019.190.3.6. URLhttps://annals.math.pr inceton.edu/2019/190-3/p06 on Pithdoi:10.4007/annals.2019.190.3.6
- [18] R. Kulkarni and A. Tal. On fractional block sensitivity.Chicago Journal of Theoretical Computer Science, 2016(8):1–16, 2016. doi: 10.4086/cjtcs.2016.008. URLhttps://eccc.weizmann.ac.il/repo rt/2013/168/ on Pithdoi:10.4086/cjtcs.2016.008
- [19] T. Lee, R. Mittal, B. W. Reichardt, R. Špalek, and M. Szegedy. Quantum query complexity of state conversion. InProceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 344–353. IEEE, 2011. doi: 10.1109/FOCS.2011.75. URLhttps://arxiv.org/ab... on Pithdoi:10.1109/focs.2011.75
- [21] N. Nisan. CREW PRAMs and decision trees.SIAM Journal on Computing, 20(6):999–1007, 1991. doi: 10.1137/0220062. URLhttps://doi.org/10.1137/0220062 on Pithdoi:10.1137/0220062
show 6 more
- [23] A. A. Razborov. On the distributional complexity of disjointness.Theoretical Computer Science, 106(2): 385–390, 1992. doi: 10.1016/0304-3975(92)90260-M. URL https://people.cs.uchicago.edu/~razbo rov/files/dis.pdf on Pithdoi:10.1016/0304-3975(92)90260-m
- [24] B. W. Reichardt. Reflections for quantum query algorithms. InProceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 560–569. SIAM, 2011. URL https://arxiv.org/abs/1005.1601 on PithPith's reviewarXiv
- [25] B. W. Reichardt and R. Špalek. Span-program-based quantum algorithm for evaluating formulas.Theory of Computing, 8(13):291–319, 2012. doi: 10.4086/toc.2012.v008a013. URLhttps://theoryofcomputin g.org/articles/v008a013/. Conference version in STOC 2008. 45 on Pithdoi:10.4086/toc.2012.v008a013
- [26] A. Tal. Properties and applications of Boolean function composition. InProceedings of the 4th Innovations in Theoretical Computer Science Conference (ITCS), pages 441–454, 2013. doi: 10.1145/2422436.2422485. URL https://eccc.weizmann.ac.il/report/2012/163/. Claim numbering fol... on Pithdoi:10.1145/2422436.2422485
- [2004] URLhttps://arxiv.org/abs/quant-ph/0403168 on PithPith's reviewarXiv
- [2026] URLhttps://arxiv.org/abs/2609.30139v2. Version 2, October 23, 2026 on PithPith's reviewarXiv
Challenges and discussion
Disagree with the review, or know something it missed? Leave a comment, or challenge this review formally: a challenge becomes a permanent entry in this paper's record, and its decision is published here.
Come back by email
A short list of the week's newly reviewed papers. Nothing is sent until you confirm from your inbox, and every email has a link that stops it. No account.
No comments yet.
Sign in to comment