No low-degree tests for quantum states

• URL: http://arxiv.org/abs/2608.00265v1
• Date: Fri, 31 Jul 2026 20:15:08 GMT
• Title: No low-degree tests for quantum states
• Abstract summary: It is not known whether quantum tests exist.<n>Any tester requires $(binomlfloor m/2rfloorlfloor (d-1)/2 rfloor)$ copies to determine whether a given state is a degree-$d$ phase state or is far from every such state.
• Score: 4.832453524102334
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of testing low-degree phase states, namely m-qudit quantum states of the form $q^{-m/2} \sum_{x \in \mathbb{F}_q^m} ω^{f(x)} |x>$, where $f$ is a degree-$d$ polynomial. In contrast to the classical setting, where low-degree polynomials admit highly efficient classical testers, it is not known whether analogous quantum tests exist. We show that no such quantum low-degree test exists: any tester requires $Ω(\binom{\lfloor m/2\rfloor}{\lfloor (d-1)/2 \rfloor})$ copies to determine whether a given state is a degree-$d$ phase state or is far from every such state. Our results follow from a general framework that relates quantum testing of codeword phase states to classical decoding properties of the dual code, which allows us to leverage known bounds on the tolerance of high-rate Reed--Muller codes to random errors.

Related papers

• Verifiable quantum advantage in extremely low depth [52.51019642214249]
  We give a problem that is solvable by shallow quantum circuits, hard for computation in time under lattice-based assumptions.<n>We prove that shallow quantum circuits have sufficient structure to solve certain classically hard tasks whose solutions can be verified efficiently.
  arXiv  Detail & Related papers  (2026-09-01T15:54:34Z)
• Hamiltonian Decoded Quantum Interferometry [69.7049555871155]
  We introduce Hamiltonian Decoded Quantum Interferometry (HDQI)<n>HDQI utilizes coherent measurements and the symplectic representation of the Pauli group to reduce Gibbs sampling and Hamiltonian Bellians.<n>We show that HDQI efficiently prepares Gibbs states at arbitrary temperatures for a class of physically motivated commuting Hamiltonians.
  arXiv  Detail & Related papers  (2025-10-09T08:06:15Z)
• Quantum Sequential Universal Hypothesis Testing [62.751483592497806]
  Quantum hypothesis testing (QHT) concerns the statistical inference of unknown quantum states.<n>We introduce the quantum sequential universal test (QSUT), a novel framework for sequential QHT in the general case of composite hypotheses.<n> QSUT builds on universal inference, and it alternates between adaptive local measurements aimed at exploring the hypothesis space and joint measurements optimized for maximal discrimination.
  arXiv  Detail & Related papers  (2025-08-29T12:50:04Z)
• Shallow quantum circuit for generating O(1)-entangled approximate state designs [6.161617062225404]
  We find a new ensemble of quantum states that serve as an $epsilon$-approximate state $t$-design while possessing extremely low entanglement, magic, and coherence.<n>These resources can reach their theoretical lower bounds, $Omega(log (t/epsilon))$, which are also proven in this work.<n>A class of quantum circuits proposed in our work offers reduced cost for classical simulation of random quantum states.
  arXiv  Detail & Related papers  (2025-07-23T18:56:19Z)
• Topological control of quantum speed limits [55.2480439325792]
  We show that even if the quantum state is completely dispersionless, QFI in this state remains momentum-resolved.<n>We find bounds on quantum speed limit which scales as $sqrt|C|$ in a (dispersionless) topological phase.
  arXiv  Detail & Related papers  (2025-07-21T18:00:07Z)
• Testing classical properties from quantum data [0.22940141855172033]
  We introduce quantum algorithms that test properties of $f$ solely from quantum data in the form of copies of the function state $|frangle propto sum_x|x,f(x)rangle$.<n>For three well-established properties--monotonicity, symmetry, and triangle-freeness--we show that the speedup lost when restricting classical testers to sampled data can be recovered by quantum algorithms operating solely from quantum data.
  arXiv  Detail & Related papers  (2024-11-19T18:52:55Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• Lower Bounds for Unitary Property Testing with Proofs and Advice [0.0]
  In unitary property testing a quantum algorithm, also known as a tester, is given query access to a black-box unitary.<n>We propose a new technique for proving lower bounds on the quantum query of unitary property testing.
  arXiv  Detail & Related papers  (2024-01-15T19:00:36Z)
• Sparse random Hamiltonians are quantumly easy [105.6788971265845]
  A candidate application for quantum computers is to simulate the low-temperature properties of quantum systems. This paper shows that, for most random Hamiltonians, the maximally mixed state is a sufficiently good trial state. Phase estimation efficiently prepares states with energy arbitrarily close to the ground energy.
  arXiv  Detail & Related papers  (2023-02-07T10:57:36Z)
• Multi-state Swap Test Algorithm [2.709321785404766]
  Estimating the overlap between two states is an important task with several applications in quantum information. We design a quantum circuit to measure overlaps of multiple quantum states.
  arXiv  Detail & Related papers  (2022-05-15T03:31:57Z)
• Efficient Verification of Anticoncentrated Quantum States [0.38073142980733]
  I present a novel method for estimating the fidelity $F(mu,tau)$ between a preparable quantum state $mu$ and a classically specified target state $tau$. I also present a more sophisticated version of the method, which uses any efficiently preparable and well-characterized quantum state as an importance sampler.
  arXiv  Detail & Related papers  (2020-12-15T18:01:11Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

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.