For every constant k>=2, the k+1st level of the Fourier hierarchy is strictly more powerful than the kth level relative to an oracle, resolving a conjecture of Shi.
Average-case complexity versus approximate simulation of commuting quantum computations
6 Pith papers cite this work, alongside 312 external citations. Polarity classification is still indexing.
6
Pith papers citing it
312
external citations · external index
representative citing papers
Deciding circuit width w(f) ≤ k for degree-3 polynomials with no constant term is NP-complete, with 49/48-ε inapproximability, ETH lower bounds, and FPT algorithms.
Depolarizing noise cuts one-dimensional shallow quantum circuits into independent logarithmic pieces, enabling a parallel sampler with doubly-logarithmic runtime and an AC^0 simulation that rules out any superconstant classical depth advantage on a line.
Sparse qubit connectivity inflates compiled circuit depth, pushing noisy IQP sampling implementations closer to the classically simulatable regime, whereas all-to-all architectures preserve a positive simulatability margin at current error rates.
A quantum algorithm simulates unital dephasing dynamics by sampling stochastic unitaries and decouples coupled fermion-boson dephasing into an IQP circuit that controls the fermion evolution.
QAIS uses a parameterized quantum circuit to allocate Monte Carlo samples along a learned non-separable density and achieves VEGAS-competitive or better accuracy on correlated integrands in simulation.
citing papers explorer
-
Oracle Separations in the Fourier Hierarchy
For every constant k>=2, the k+1st level of the Fourier hierarchy is strictly more powerful than the kth level relative to an oracle, resolving a conjecture of Shi.
-
On the Complexity of the Circuit Width Problem
Deciding circuit width w(f) ≤ k for degree-3 polynomials with no constant term is NP-complete, with 49/48-ε inapproximability, ETH lower bounds, and FPT algorithms.
-
Parallel classical simulation of noisy shallow circuits: no quantum advantage in 1D
Depolarizing noise cuts one-dimensional shallow quantum circuits into independent logarithmic pieces, enabling a parallel sampler with doubly-logarithmic runtime and an AC^0 simulation that rules out any superconstant classical depth advantage on a line.
-
The Impact of Qubit Connectivity on Quantum Advantage in Noisy IQP Circuits
Sparse qubit connectivity inflates compiled circuit depth, pushing noisy IQP sampling implementations closer to the classically simulatable regime, whereas all-to-all architectures preserve a positive simulatability margin at current error rates.
-
Quantum algorithm for dephasing of coupled systems: decoupling and IQP duality
A quantum algorithm simulates unital dephasing dynamics by sampling stochastic unitaries and decouples coupled fermion-boson dephasing into an IQP circuit that controls the fermion evolution.
-
Unlocking Multidimensional Integration with Quantum Adaptive Importance Sampling
QAIS uses a parameterized quantum circuit to allocate Monte Carlo samples along a learned non-separable density and achieves VEGAS-competitive or better accuracy on correlated integrands in simulation.