Unbounded quantum-classical separation in sample complexity for sphere center finding

DOI10.1016/J.IC.2025.105361MaRDI QIDQ6884309zbMATH OpenFDO

Authors Guanzhong Li, Lvzhou Li

Publication date 15 December 2025

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IC.2025.105361

zbMATH Keywords

quantum algorithmsquantum walkssample complexitysphere-center finding

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Quantum computation (81P68)

Cites work

• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 1516803 (Why is no real title available?)
• scientific article; zbMATH DE number 3106184 (Why is no real title available?)
• (Sub)Exponential advantage of adiabatic Quantum computation with no sign problem
• A New Proof of Warning's Second Theorem
• Adiabatic quantum state generation and statistical zero knowledge
• Bemerkung zur vorstehenden Arbeit von Herrn Chevalley
• Coins make quantum walks faster
• Exponential algorithmic speedup by a quantum walk
• Exponential quantum speedup in simulating coupled classical oscillators
• Finite analogues of Euclidean space
• Learning DNF over the Uniform Distribution Using a Quantum Example Oracle
• Learning functions of \(k\) relevant variables
• Multidimensional quantum walks
• On A Theorem of von Neumann
• One-dimensional quantum walks
• Optimal deterministic quantum algorithm for the promised element distinctness problem
• Optimal quantum sample complexity of learning algorithms
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum Algorithms for the Triangle Problem
• Quantum Walk Algorithm for Element Distinctness
• Quantum algorithms for learning and testing juntas
• Quantum complexity of testing group commutativity
• Quantum verification of matrix products
• Quantum walks can find a marked element on any graph
• Quantum walks on graphs
• Recovering the original simplicity: succinct and deterministic quantum algorithm for the welded tree problem
• Search via Quantum Walk
• Spatial search and the Dirac equation
• Symmetries, graph properties, and quantum speedups
• Verifiable quantum advantage without structure
• Warning's second theorem with relaxed outputs
• Warning's second theorem with restricted variables
• Zur Theorie der Gesellschaftsspiele.

This page was built for publication: Unbounded quantum-classical separation in sample complexity for sphere center finding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6884309)