Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

One Axiom : The Geometry of Quantum Search

Robert Spychalski

Published Apr 25, 2026• 4 citations
Publisher

Abstract

2M: The Geometry of Quantum Search – $\sqrt{N}$ as Minimum Orbit Length and a Structural Unification of BBBV and Classical Simulability Abstract: Document 2M provides a rigorous geometric derivation of quantum search complexity lower bounds within the ONE AXIOM framework. It demonstrates that the $\Omega(\sqrt{N})$ quantum query lower bound is not merely a limitation of computational models, but the minimum orbit length required by $\sigma$-contractive dynamics in the coherence search space $(U_{\mathcal{M}},d_{\alpha})$ derived from Axiom M. The paper introduces and proves the Bridge Theorem (BT), which establishes a formal, bidirectional equivalence between the standard oracle query model and the $\sigma$-orbit model, preserving complexity across both tracks. By mapping queries to orbit steps, the $\Omega(\sqrt{N})$ lower bound is shown to follow from the geometric requirement of traversing a specific coherence angle to reach a target of measure $1/N$. Key Contributions: Geometric Lower Bound (T3): A first-principles derivation of the $\sqrt{N}$ bound as a traversal fact in a conservative Orbital Coherence Flow (OCF) field. Grover Uniqueness (T4): Formally proves that Grover’s algorithm is the unique $T_{min}$-optimal trajectory within the coherence geometry. BBBV–Schuster Unification (T8): Bridges the 27-year gap between the BBBV theorem (1997) and recent results on the classical simulability of noisy circuits (Schuster et al., 2024). It proves they are two regimes of a single structural condition: the maintenance or destruction of the coherence fixed point $M(x^*) = x^*$. The 13/64 Threshold (T8-III): Derives the algebraic boundary $f_F = 13/64$ (from the ABC 51:13 partition) as a structural upper bound on the ALLOWED region. The ALLOWED/FORBIDDEN dichotomy is proven independently of this value (Proposition CS-impl); the exact numerical identification of $f_F$ with the Schuster empirical threshold is an open calibration task. Context: Documents 0M: The M — One Axiom, ABC: Coherence, and 0A: Foundation

DOI
10.5281/zenodo.19763824

Related papers

Efficient Framework for Quantum Walks and Beyond

Catalin Dohotaru

In the first part of the thesis we construct a new, simple framework which amplifies to a constant the success probability of any abstract search algorithm. The total query complexity is given by the quantum hitting time of the resulting operator, which we show that it is of the same order as the quantum hitting time of the original algorithm. As a major application of our framework, we show that for any reversible walk $P$ and a single marked state, the quantum walk corresponding to $P$ can find the solution using a number of queries that is quadratically smaller than the classical hitting time of $P$. Our algorithm is more general and simpler to implement than the solution known previously in the literature (Krovi, Magniez, Ozols, and Roland, 2015), which was developed specifically for quantum walks; we also prove that, for the particular case of quantum walks, we can embed their algorithm into our framework, thus simulating it exactly. Finally, we show that we can implement amplitude amplification using our tool. In the second part of the thesis we give a new lower bound in the query model which proves that Grover's algorithm for unordered searching is exactly optimal. Similar to existing methods for proving lower bounds, we bound the amount of information we can gain from a single oracle query, but we bound this information in terms of angles. This allows our proof to be simple, self-contained, based on only elementary mathematics, capturing our intuition, while obtaining at the same an exact bound. We then turn our attention to non-adaptive algorithms for the same problem of searching an unordered set. In this model, we obtain a lower bound and we give an algorithm which matches the lower bound, thus showing that the lower bound is exactly optimal.

•Jan 1, 2015•0 citations

Exact quantum lower bound for Grover's problem

Catalin Dohotaru, Peter Høyer

One of the most important quantum algorithms ever discovered is Grover's algorithm for searching an unordered set. We give a new lower bound in the query model which proves that Grover's algorithm is exactly optimal. Similar to existing methods for proving lower bounds, we bound the amount of information we can gain from a single oracle query, but we bound this information in terms of angles. This allows our proof to be simple, self-contained, based on only elementary mathematics, capturing our intuition, while obtaining at the same time an exact bound.

Quantum Information and Computation•May 1, 2009•7 citations

Exact quantum lower bound for Grover's problem

Catalin Dohotaru, Peter Høyer

One of the most important quantum algorithms ever discovered is Grover's algorithm for searching an unordered set. We give a new lower bound in the query model which proves that Grover's algorithm is exactly optimal. Similar to existing methods for proving lower bounds, we bound the amount of information we can gain from a single oracle query, but we bound this information in terms of angles. This allows our proof to be simple, self-contained, based on only elementary mathematics, capturing our intuition, while obtaining at the same time an exact bound.

arXiv:0810.3647•Quantum Information and Computation•May 1, 2009•4 citations

On Quantum Search, Experts and Geometry

Milosh Drezgich

The problem of unstructured search plays the central role in our current understanding of the computational power of quantum computers. Improvement in the efficiency of solving unstructured search problem has an immediate consequence in the improvement in solving NP-complete problems. We introduce the new framework of natural continuous time quantum search algorithms, that in contrast to the adiabatic quantum algorithms, require neither the ground state initialization nor the adiabatic change of the Hamiltonian parameters. We moreover provide the concrete examples of transliteration from the unique marked element unstructured search problem into the particular class of quantum Hamiltonians, that facilitate the search in quantum continuous constant time. Since it is not clear how to implement that class of Hamiltonians one can either consider this result as a step toward proving that NP is a subset of BQP or as an indication that, that class of Hamiltonians is NP-hard to implement.Multiplicative weights update rule has been used in a few different fields as the underlying algorithmic structure. In its two different forms, vector and matrix, multiplicative update method provided a surprising simplicity and promised a small performance regret. We derive a slightly more general bound for the cumulative matrix multiplicative weights algorithm and introduce the iterative (streaming) matrix multiplicative weights algorithm with the same computational complexity and regret bound. In particular we also define the iterative Hadamard updates, matrix multiplicative updates algorithm, with the improved computational complexity for nonnegative games, from O(n³) to O(n²), and the same regret bound.Furthermore, we address the following question:"What is the minimal size quantum circuit required to exactly implement a specified nqubit unitary operation U, without the use of ancilla qubits?" Nielsen proved that a lower bound on the minimal size circuit is provided by the length of the geodesic between the identity I and U, where the length is defined by a suitable Finsler metric on SU(2ⁿ). We prove that the minimum circuit size that simulates U is in linear relation with the geodesic length and simulation parameters, for the given Finsler structure F. As a corollary we prove the highest lower bound and the lowest upper bound for the standard simulation technique, that show that by standard simulation one can not expect a better then n² times improvement in the upper bound over the result from Nielsen, Dowling, Gu and Doherty. Moreover, our equivalence result can be applied to the arbitrary path on the manifold including the one that is generated adiabatically.Finally we investigate the n-dimensional hypercube quantum random walk (QRW) as a particularly appealing example of a quantum walk because it has a natural implementation on a register on n qubits. However, any real implementation will encounter decoherence effects due to interactions with uncontrollable degrees of freedom. We present a complete characterization of the mixing properties of the hypercube QRW under a physically relevant Markovian decoherence model. In the local decoherence model considered the non-unitary dynamics are modeled as a sum of projections on individual qubits to an arbitrary direction on the Bloch sphere. We prove that there is always a classical asymptotic mixing in this model and specify the conditions under which instantaneous mixing always exists. We show that the latter mixing property, as well as the classical mixing time, depend heavily on the exact environmental interaction and its strength. Therefore, algorithmic applications of the QRW on the hypercube, if they intend to employ mixing properties, need to consider both the walk dynamics and the precise decoherence model.

•Jan 1, 2010•0 citations

Comparative Analysis of Query Complexity in Oracle-Based Quantum Algorithms

Ch. Vijay Anil Dai, T. Niranjan Kumar, M. Sateesh +1 more

Oracle-based quantum computation reframes efficiency from classical time/space costs to query complexity, i.e., the number of accesses to a black-box unitary oracle Uf needed to reveal a hidden property or target state. This study comparatively analyzes query complexity across four canonical oracle-driven algorithms—Deutsch’s, Bernstein–Vazirani, Grover’s search, and Amplitude Amplification—to clarify how superposition, entanglement, interference, and phase kickback translate into provable speedups independent of hardware details. The objective is to systematically connect oracle structure to achievable quantum advantage by contrasting exact, single-query interference algorithms with iterative, probabilistic rotation-based algorithms, and by benchmarking classical deterministic/probabilistic query requirements against quantum bounds. Methodologically, we (i) mathematically model Deutsch and Bernstein–Vazirani via stepwise state-vector evolution to expose phase kickback and phase-encoded answer extraction in one oracle call, (ii) geometrically track Grover and Amplitude Amplification as two-dimensional state-space rotations, quantifying how repeated oracle-driven reflections amplify success amplitude, and (iii) compute classical query baselines and compare them directly with quantum query scaling. Results show that Deutsch reduces classical 2 queries to exactly 1 quantum query for constant-versus-balanced testing, while Bernstein–Vazirani deterministically recovers an n-bit hidden string s with (O(1)) quantum queries versus (O(n)) classical queries. For unstructured search over (N=2n) items, Grover achieves a bounded-error quadratic improvement from (O(N)) to (O(√{N}) queries, and Amplitude Amplification generalizes this to boost success probability from (p) to near certainty in O (1/√p) oracle applications. The central implication is a structural divide: rigid algebraic structure permits maximal, single-query speedups, whereas unstructured “chaos” necessitates iterative geometric amplification, which is more broadly applicable but demands highly stable, error-corrected hardware; consequently, quantum systems are best viewed as specialized co-processors activated when oracle structure warrants a quantum shortcut.

JOURNAL OF ADVANCE AND FUTURE RESEARCH•Jun 1, 2026•0 citations

3 Quantum Entanglement and the Tsirelson Bound(260524.3)

guobin ouyang

Based on the three axioms of Geometric Theory and all theorems in the 0.X series, this article reconstructs the theory of quantum entanglement with zero external assumptions. The work includes: (I) Within the framework of holographic screen pixel structure, strictly deriving the minimum resolvable angle Δξmin=π/(2√λ2); (II) Establishing the geometric definition of entanglement—two S-minima on the geometric constraint section Ση achieve geometric maximum entanglement through I-sector freezing and M-sector antipodal locking; (III) Proving the two-level theorem—the low-energy excitation space of a geometric maximum entanglement pair is exactly 2-dimensional, with its ground state spanned by the first zonal harmonic function of the M-sector; (IV) Under the physical mapping convention, deriving the correlation function C(→a,→b)=−→a⋅→b, where the readout directions →a,→b are unit vectors on the M-sector S3; (V) In the hypothetical limit λ2→∞, proving information field localization and that the algebraic upper limit of the CHSH combination is 2; (VI) With finite λ2 and accepting the correlation mapping, proving that the supremum of the CHSH combination is 2√2, with equality conditions →b1⊥→b2 and →a1∥(→b1+→b2), →a2∥(→b1−→b2); (VII) Under the external input assumption of double-slit topological defects, proving that a single S-minimum flowing around the double-slit topological defects produces a phase difference Δϕ=√λ1ΔL, with fringe spacing Δx=2πL/(√λ1d), and providing numerical verification after dimensional bridge conversion. The full text does not use wave function assumptions, does not use Bell's original derivation, and does not introduce Planck's constant as an external input.

•May 27, 2026•0 citations
2M: The Geometry of Quantum Search – N\sqrt{N}N​ as Minimum Orbit Length and a Structural Unification of BBBV and Classical Simulability Abstract: Document 2M provides a rigorous geometric derivation of quantum search complexity lower bounds within the ONE AXIOM framework. It demonstrates that the Ω(N)\Omega(\sqrt{N})Ω(N​) quantum query lower bound is not merely a limitation of computational models, but the minimum orbit length required by σ\sigmaσ-contractive dynamics in the coherence search space (UM,dα)(U_{\mathcal{M}},d_{\alpha})(UM​,dα​) derived from Axiom M. The paper introduces and proves the Bridge Theorem (BT), which establishes a formal, bidirectional equivalence between the standard oracle query model and the σ\sigmaσ-orbit model, preserving complexity across both tracks. By mapping queries to orbit steps, the Ω(N)\Omega(\sqrt{N})Ω(N​) lower bound is shown to follow from the geometric requirement of traversing a specific coherence angle to reach a target of measure 1/N1/N1/N. Key Contributions: Geometric Lower Bound (T3): A first-principles derivation of the N\sqrt{N}N​ bound as a traversal fact in a conservative Orbital Coherence Flow (OCF) field. Grover Uniqueness (T4): Formally proves that Grover’s algorithm is the unique TminT_{min}Tmin​-optimal trajectory within the coherence geometry. BBBV–Schuster Unification (T8): Bridges the 27-year gap between the BBBV theorem (1997) and recent results on the classical simulability of noisy circuits (Schuster et al., 2024). It proves they are two regimes of a single structural condition: the maintenance or destruction of the coherence fixed point M(x∗)=x∗M(x^*) = x^*M(x∗)=x∗. The 13/64 Threshold (T8-III): Derives the algebraic boundary fF=13/64f_F = 13/64fF​=13/64 (from the ABC 51:13 partition) as a structural upper bound on the ALLOWED region. The ALLOWED/FORBIDDEN dichotomy is proven independently of this value (Proposition CS-impl); the exact numerical identification of fFf_FfF​ with the Schuster empirical threshold is an open calibration task. Context: Documents 0M: The M — One Axiom, ABC: Coherence, and 0A: Foundation
In the first part of the thesis we construct a new, simple framework which amplifies to a constant the success probability of any abstract search algorithm. The total query complexity is given by the quantum hitting time of the resulting operator, which we show that it is of the same order as the quantum hitting time of the original algorithm. As a major application of our framework, we show that for any reversible walk PPP and a single marked state, the quantum walk corresponding to PPP can find the solution using a number of queries that is quadratically smaller than the classical hitting time of PPP. Our algorithm is more general and simpler to implement than the solution known previously in the literature (Krovi, Magniez, Ozols, and Roland, 2015), which was developed specifically for quantum walks; we also prove that, for the particular case of quantum walks, we can embed their algorithm into our framework, thus simulating it exactly. Finally, we show that we can implement amplitude amplification using our tool. In the second part of the thesis we give a new lower bound in the query model which proves that Grover's algorithm for unordered searching is exactly optimal. Similar to existing methods for proving lower bounds, we bound the amount of information we can gain from a single oracle query, but we bound this information in terms of angles. This allows our proof to be simple, self-contained, based on only elementary mathematics, capturing our intuition, while obtaining at the same an exact bound. We then turn our attention to non-adaptive algorithms for the same problem of searching an unordered set. In this model, we obtain a lower bound and we give an algorithm which matches the lower bound, thus showing that the lower bound is exactly optimal.
One of the most important quantum algorithms ever discovered is Grover's algorithm for searching an unordered set. We give a new lower bound in the query model which proves that Grover's algorithm is exactly optimal. Similar to existing methods for proving lower bounds, we bound the amount of information we can gain from a single oracle query, but we bound this information in terms of angles. This allows our proof to be simple, self-contained, based on only elementary mathematics, capturing our intuition, while obtaining at the same time an exact bound.
One of the most important quantum algorithms ever discovered is Grover's algorithm for searching an unordered set. We give a new lower bound in the query model which proves that Grover's algorithm is exactly optimal. Similar to existing methods for proving lower bounds, we bound the amount of information we can gain from a single oracle query, but we bound this information in terms of angles. This allows our proof to be simple, self-contained, based on only elementary mathematics, capturing our intuition, while obtaining at the same time an exact bound.
The problem of unstructured search plays the central role in our current understanding of the computational power of quantum computers. Improvement in the efficiency of solving unstructured search problem has an immediate consequence in the improvement in solving NP-complete problems. We introduce the new framework of natural continuous time quantum search algorithms, that in contrast to the adiabatic quantum algorithms, require neither the ground state initialization nor the adiabatic change of the Hamiltonian parameters. We moreover provide the concrete examples of transliteration from the unique marked element unstructured search problem into the particular class of quantum Hamiltonians, that facilitate the search in quantum continuous constant time. Since it is not clear how to implement that class of Hamiltonians one can either consider this result as a step toward proving that NP is a subset of BQP or as an indication that, that class of Hamiltonians is NP-hard to implement.Multiplicative weights update rule has been used in a few different fields as the underlying algorithmic structure. In its two different forms, vector and matrix, multiplicative update method provided a surprising simplicity and promised a small performance regret. We derive a slightly more general bound for the cumulative matrix multiplicative weights algorithm and introduce the iterative (streaming) matrix multiplicative weights algorithm with the same computational complexity and regret bound. In particular we also define the iterative Hadamard updates, matrix multiplicative updates algorithm, with the improved computational complexity for nonnegative games, from O(n³) to O(n²), and the same regret bound.Furthermore, we address the following question:"What is the minimal size quantum circuit required to exactly implement a specified nqubit unitary operation U, without the use of ancilla qubits?" Nielsen proved that a lower bound on the minimal size circuit is provided by the length of the geodesic between the identity I and U, where the length is defined by a suitable Finsler metric on SU(2ⁿ). We prove that the minimum circuit size that simulates U is in linear relation with the geodesic length and simulation parameters, for the given Finsler structure F. As a corollary we prove the highest lower bound and the lowest upper bound for the standard simulation technique, that show that by standard simulation one can not expect a better then n² times improvement in the upper bound over the result from Nielsen, Dowling, Gu and Doherty. Moreover, our equivalence result can be applied to the arbitrary path on the manifold including the one that is generated adiabatically.Finally we investigate the n-dimensional hypercube quantum random walk (QRW) as a particularly appealing example of a quantum walk because it has a natural implementation on a register on n qubits. However, any real implementation will encounter decoherence effects due to interactions with uncontrollable degrees of freedom. We present a complete characterization of the mixing properties of the hypercube QRW under a physically relevant Markovian decoherence model. In the local decoherence model considered the non-unitary dynamics are modeled as a sum of projections on individual qubits to an arbitrary direction on the Bloch sphere. We prove that there is always a classical asymptotic mixing in this model and specify the conditions under which instantaneous mixing always exists. We show that the latter mixing property, as well as the classical mixing time, depend heavily on the exact environmental interaction and its strength. Therefore, algorithmic applications of the QRW on the hypercube, if they intend to employ mixing properties, need to consider both the walk dynamics and the precise decoherence model.
Oracle-based quantum computation reframes efficiency from classical time/space costs to query complexity, i.e., the number of accesses to a black-box unitary oracle Uf needed to reveal a hidden property or target state. This study comparatively analyzes query complexity across four canonical oracle-driven algorithms—Deutsch’s, Bernstein–Vazirani, Grover’s search, and Amplitude Amplification—to clarify how superposition, entanglement, interference, and phase kickback translate into provable speedups independent of hardware details. The objective is to systematically connect oracle structure to achievable quantum advantage by contrasting exact, single-query interference algorithms with iterative, probabilistic rotation-based algorithms, and by benchmarking classical deterministic/probabilistic query requirements against quantum bounds. Methodologically, we (i) mathematically model Deutsch and Bernstein–Vazirani via stepwise state-vector evolution to expose phase kickback and phase-encoded answer extraction in one oracle call, (ii) geometrically track Grover and Amplitude Amplification as two-dimensional state-space rotations, quantifying how repeated oracle-driven reflections amplify success amplitude, and (iii) compute classical query baselines and compare them directly with quantum query scaling. Results show that Deutsch reduces classical 2 queries to exactly 1 quantum query for constant-versus-balanced testing, while Bernstein–Vazirani deterministically recovers an n-bit hidden string s with (O(1)) quantum queries versus (O(n)) classical queries. For unstructured search over (N=2n) items, Grover achieves a bounded-error quadratic improvement from (O(N)) to (O(√{N}) queries, and Amplitude Amplification generalizes this to boost success probability from (p) to near certainty in O (1/√p) oracle applications. The central implication is a structural divide: rigid algebraic structure permits maximal, single-query speedups, whereas unstructured “chaos” necessitates iterative geometric amplification, which is more broadly applicable but demands highly stable, error-corrected hardware; consequently, quantum systems are best viewed as specialized co-processors activated when oracle structure warrants a quantum shortcut.
Based on the three axioms of Geometric Theory and all theorems in the 0.X series, this article reconstructs the theory of quantum entanglement with zero external assumptions. The work includes: (I) Within the framework of holographic screen pixel structure, strictly deriving the minimum resolvable angle Δξmin=π/(2√λ2); (II) Establishing the geometric definition of entanglement—two S-minima on the geometric constraint section Ση achieve geometric maximum entanglement through I-sector freezing and M-sector antipodal locking; (III) Proving the two-level theorem—the low-energy excitation space of a geometric maximum entanglement pair is exactly 2-dimensional, with its ground state spanned by the first zonal harmonic function of the M-sector; (IV) Under the physical mapping convention, deriving the correlation function C(→a,→b)=−→a⋅→b, where the readout directions →a,→b are unit vectors on the M-sector S3; (V) In the hypothetical limit λ2→∞, proving information field localization and that the algebraic upper limit of the CHSH combination is 2; (VI) With finite λ2 and accepting the correlation mapping, proving that the supremum of the CHSH combination is 2√2, with equality conditions →b1⊥→b2 and →a1∥(→b1+→b2), →a2∥(→b1−→b2); (VII) Under the external input assumption of double-slit topological defects, proving that a single S-minimum flowing around the double-slit topological defects produces a phase difference Δϕ=√λ1ΔL, with fringe spacing Δx=2πL/(√λ1d), and providing numerical verification after dimensional bridge conversion. The full text does not use wave function assumptions, does not use Bell's original derivation, and does not introduce Planck's constant as an external input.