Results on quantum query algorithms, amplitude amplification, the adversary bound, and the comparison of randomized and quantum query complexity

The course proves the statements below; each link leads to the statement with its assumptions and its proof. The lessons are self-checked by the writing AI; independent mathematical review is not complete.

• An exact Boolean circuit for the Forrelation function — Lemma 4.1. For fixed k >= 2 and every power of four m there is a Boolean circuit with gates of at most two inputs and size at most C_k m (log m)^2 with two outputs d, b: d = 1 exactly if the k-fold Forrelation function with thresholds delta = 2^(-5k) and delta/2 is defined on the input, and then b is its value.
• A winner at a given address is recognized by local tests — Lemma 6.1. For the function F_(k,m), a column i and an address s: i wins at s if and only if K = m + (m-1) + r(S+2) tests pass, each of which reads at most log2(m) + 1 input bits.
• Measurements during a computation can be deferred — Theorem 3.2. A quantum query procedure given by a finite tree of unitary maps, queries and measurements with outcome-dependent continuation, with at most T queries on every path, is simulated by a query algorithm with T queries (unitary maps, queries, one measurement at the end) with the same output probabilities on every input.
• Read queries at computed positions — Lemma 4.1. For a function loc from the labels of a register to the positions, the map |c, b> -> |c, b + x_loc(c)> is obtained with one query and permutation maps, with the index and bit registers restored.
• Phase queries and conditional queries — Lemma 4.2. The map |c> -> (-1)^(x_loc(c)) |c>, and the read query applied only for c in a given subset, are each obtained with two queries and one ancilla bit that is restored.
• Decision trees in superposition — Lemma 5.1. For decision trees A_c of depth at most q, c in a finite set: a query circuit with q queries maps |c>|0>|y> to |c>|answers>|y + A_c(x)> for all c and x.
• The rotation of amplitude amplification — Lemma 1.1. For a preparation A with success probability sin^2(theta) in (0,1), successful state g and unsuccessful state b, and G = A S_0 A^(-1) S: G^l A|0> = sin((2l+1) theta) g + cos((2l+1) theta) b.
• Amplification with a fixed successful state — Lemma 1.2. For a preparation with c queries, 0 < gamma <= 1/2 and 0 < eta < 1/2 there is a procedure with at most 88 c gamma^(-1/2) log2(1/eta) queries on every path that fails always if p = 0, fails with probability at most eta if p >= gamma, and whenever it succeeds holds the successful state g of the preparation.
• The Forrelation test — Lemma 2.1. A preparation with k phase queries has success probability Phi(z_1, ..., z_k)^2, where Phi = u^T D_(z_1) H D_(z_2) H ... H D_(z_k) u.
• The Forrelation function with bounded error — Lemma 2.2. For 0 < eta < 1/2 a query circuit with at most 384 k 2^(10k) log2(1/eta) queries, independent of m, has an answer bit that equals the Forrelation function with probability at least 1 - eta on every input of its domain.
• A tournament for probabilistic comparisons — Proposition 2.1. Let a comparison circuit with c queries have win probabilities a_ij with a_ij + a_ji = 1. With T = ceil(log2(1000 m)) and eps = 1/(1000 T), a procedure with at most 63 c sqrt(m) T^2 log2(1000 T) queries returns a list of at most T candidates that contains every candidate i with a_ij >= 1 - eps for all j, with probability at least 1 - 3/1000. No transitivity is assumed.
• The quantum query complexity of F_(k,m) — Theorem 5.1. For every k >= 2 there is C_k with Q(F_(k,m)) <= C_k sqrt(m) (log2 m)^4 for all powers of four m >= 4. No hypothesis.
• Guessing the answers of several independent inputs — Lemma 2.1. Let every decision tree of depth at most L compute P with probability at most beta under mu. A decision tree on r independent inputs with law mu that makes at most L queries to each input, with adaptive interleaving and independent side information, outputs all r values of P with probability at most beta^r.
• The randomized query complexity of F_(k,m) — Proposition 4.1. Assume the hypothesis (BS) (Bansal and Sinha's lower bound for Forrelation; not proved in the programme). For k >= 2 and all large powers of four m: R(F_(k,m)) > floor(m L / 100) with L = floor(m^(1-1/k) / (log2 m)^2).
• The adversary bound with nonnegative weights — Lemma 2.1. For a nonconstant total Boolean function f and a nonzero symmetric matrix Gamma >= 0 indexed by inputs with Gamma_xy = 0 when f(x) = f(y): Q(f) >= c_0 ||Gamma|| / max_i ||Gamma_i||, c_0 = (3 - 2 sqrt 2)/6, where Gamma_i keeps the entries with x_i different from y_i.
• Block sensitivity and the sensitivity graph against quantum queries — Corollary 2.2. For nonconstant total f: bs(f) <= Q(f)^2 / c_0^2 and lambda(f) <= Q(f) / c_0, where lambda(f) is the norm of the adjacency matrix of the sensitivity graph.
• Degree and the sensitivity graph (Huang) — Lemma 3.2. For every total Boolean function: deg(f) <= lambda(f)^2. In particular a set of more than half of the vertices of the d-cube induces a graph whose adjacency matrix has norm at least sqrt(d).
• Deterministic queries, block sensitivity and degree — Lemma 4.1. For every total Boolean function: D(f) <= bs(f) deg(f).
• The quartic bound — Theorem 5.1. For every total Boolean function: R(f) <= D(f) <= c_0^(-4) Q(f)^4 <= 1.5 * 10^6 Q(f)^4. No hypothesis.

Reading order

Six lessons, to be read in order. Lessons 2, 3 and 6 are of general use: the quantum query model, amplitude amplification, and the quartic inequality with the adversary bound and Huang's theorem; they are proved in full. Lessons 1, 4 and 5 treat the functions F_(k,m): their quantum complexity is proved in full, their randomized complexity under the named hypothesis (BS), the lower bound of Bansal and Sinha for the Forrelation function, which is not proved in the programme.