Quantum-Classical Equivalence for AND-Functions

• URL: http://arxiv.org/abs/2606.03249v1
• Date: Tue, 02 Jun 2026 07:10:16 GMT
• Title: Quantum-Classical Equivalence for AND-Functions
• Abstract summary: A major open problem in quantum communication complexity is whether quantum protocols can be exponentially more efficient than classical protocols.<n>We show that for every Boolean function $f$, the bounded-error quantum and classical communication complexities are deterministicly related.
• Score: 4.0075720392218335
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A major open problem in quantum communication complexity is whether quantum protocols can be exponentially more efficient than classical protocols for computing total Boolean functions; the prevailing conjecture is that they cannot be so. In a seminal work, Razborov (2002) resolved this question for AND-functions of the form $$ F(x,y) = f(x_1 \land y_1, \ldots, x_n \land y_n), $$ when the outer function $f$ is symmetric, by proving that their bounded-error quantum and classical communication complexities are polynomially related. Since then, extending this result to all AND-functions has remained open and has been posed by several authors. In this work, we settle this problem in a strong way. We show that for every Boolean function $f$, the bounded-error quantum and classical deterministic communication complexities of the function $f \circ \mathrm{AND}_2$ are polynomially related, up to polylogarithmic factors in $n$. We prove this by showing that both are characterized--up to polynomial loss--by the logarithm of the De Morgan sparsity of $f$. Our results build on the recent work of Chattopadhyay, Dahiya, and Lovett (2025) on structural characterizations of non-sparse Boolean functions, which we extend to resolve the conjecture for general AND-functions.

Related papers

• Optimal Lower Bounds for Hamiltonian Simulation [42.227880669333835]
  For Hamiltonian $H = sum_j h_j$, we proveally tight lower bounds on the gate and query complexities of simulating time evolution on a quantum computer.<n>Our hold for arbitrary term norms $|h_j|$, time $t$, and trace-distance error $$.
  arXiv  Detail & Related papers  (2026-07-22T07:41:32Z)
• DQC1-completeness of normalized trace estimation for functions of log-local Hamiltonians [20.990700912031773]
  We study the computational complexity of estimating the normalized trace $2-nTr[f(A)]$ for a log-local Hamiltonian $A$ acting on $n$ qubits.<n>This problem arises naturally in the DQC1 model, yet its complexity is only understood for a limited class of functions $f(x)$.<n>We show that if $f(x)$ is a continuous function with approximate degree $(rm poly(n))$, then estimating $2-nTr[f(A)]$ up to constant additive error is
  arXiv  Detail & Related papers  (2026-04-02T01:15:12Z)
• Quantum oracles for the finite element method [45.200826131319815]
  This study examines the quantum routines required for the implementation of oracles used in the block-encoding of the $N times N stiffness and mass matrices.<n>We show how to construct the necessary oracles, which require the calculation of element geometry, square root and the implementation of conditional operations.
  arXiv  Detail & Related papers  (2025-04-28T14:28:31Z)
• Quantum computational complexity of matrix functions [2.7488316163114823]
  We study the computational complexity of two primitive problems.<n>We consider four functions -- monomials, Chebyshevs, the time evolution function, and the inverse function.<n>We identify BQP-complete forms of both problems for each function.
  arXiv  Detail & Related papers  (2024-10-17T18:00:03Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer.<n>Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model.<n>We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
  arXiv  Detail & Related papers  (2024-05-14T15:28:37Z)
• A one-query lower bound for unitary synthesis and breaking quantum cryptography [7.705803563459633]
  The Unitary Synthesis Problem asks whether any $n$qubit unitary $U$ can be implemented by an efficient quantum $A$ augmented with an oracle that computes an arbitrary Boolean function $f$. In this work, we prove unitary synthesis as an efficient challenger-ad game, which enables proving lower bounds by analyzing the maximum success probability of an adversary $Af$.
  arXiv  Detail & Related papers  (2023-10-13T05:39:42Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
  arXiv  Detail & Related papers  (2022-04-22T12:37:56Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  We study the exploration-exploitation tradeoff at the core of reinforcement learning. In particular, we prove that the complexity of the function class $mathcalF$ characterizes the complexity of the function. Our regret bounds are independent of the number of episodes.
  arXiv  Detail & Related papers  (2020-11-09T18:32:22Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• Lower Bounds for XOR of Forrelations [7.510385608531827]
  We study the XOR of $k$ independent copies of the Forrelation function. We also show that any constant-depth circuit of quasipolynomial size has quasipolynomially small advantage over a random guess.
  arXiv  Detail & Related papers  (2020-07-07T17:05:09Z)
• Exponential quantum communication reductions from generalizations of the Boolean Hidden Matching problem [0.05076419064097732]
  First communication problem in the one-way model to demonstrate an exponential classical-quantum communication separation. Efficient communication protocols are presented depending on the sign-degree of $f$.
  arXiv  Detail & Related papers  (2020-01-15T21:05:32Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.