The Aaronson-Ambainis conjecture (Theory of Computing '14) says that every low-degree bounded polynomial on the Boolean hypercube has an influential variable. This conjecture, if true, would imply that the acceptance probability of every
d-query quantum algorithm can be well-approximated almost everywhere (i.e., on almost all inputs) by a
poly(d)-query classical algorithm. We prove a special case of the conjecture: in every completely bounded degree-
d block-multilinear form with constant variance, there always exists a variable with influence at least
1/poly(d). In a certain sense, such polynomials characterize the acceptance probability of quantum query algorithms, as shown by Arunachalam, Briët and Palazuelos (SICOMP '19). As a corollary we obtain efficient classical almost-everywhere simulation for a particular class of quantum algorithms that includes for instance
k-fold Forrelation. Our main technical result relies on connections to free probability theory.
In an attempt to show that the acceptance probability of a quantum query algorithm making
q queries can be well-approximated almost everywhere by a classical decision tree of depth
≤poly(q), Aaronson and Ambainis proposed the following conjecture: let
f:{±1}n→[0,1] be a degree
d polynomial with variance
≥ε. Then, there exists a coordinate of
f with influence
≥poly(ε,1/d). We show that for any polynomial
f:{±1}n→[0,1] of degree
d (d≥2) and variance
Var[f]≥1/d, if
ρ denotes a random restriction with survival probability
C1dlog(d),
Pr[fρ has a coordinate with influence≥dC2Var[f]2]≥50C1dVar[f]log(d) where
C1,C2>0 are universal constants. Thus, Aaronson-Ambainis conjecture is true for a non-negligible fraction of random restrictions of the given polynomial assuming its variance is not too low.
Existing schemes for synthesizing graph states in quantum networks are essentially edge-by-edge constructions, so quantities such as the time-slot depth and the resource overhead grow significantly with the edge density of the target graph. This paper proposes a new method. Exploiting the mathematical equivalence between joint Pauli-X measurements and graph pivot operations, we formulate graph state synthesis as a rank-2 reduction process of a difference matrix over GF(2), and give an upper bound floor(N/2) on the number of steps for synthesizing an arbitrary N-node graph state, independent of the edge density of the target graph state. At the physical level, the joint Pauli-X measurement of each step is mapped to a dual-star concurrent distribution. We model the protocol on Waxman physical topologies with fiber attenuation and give a heuristic algorithm, and evaluate it against a strengthened Steiner baseline through Monte Carlo experiments. The experimental results show that our protocol is superior in time-slot depth almost everywhere. The entanglement resource overhead, the total number of CZ gates, and the number of Pauli measurements drop below the baseline near edge density p approximately 0.3, and are superior across the board thereafter. The denser the target graph state, the more significant the advantage.