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

arXiv:2605.13980

From Hilbert's Tenth Problem to Quantum Speedup: Explicit Oracles for Bounded Diophantine Systems

Gabriel Escrig, M. A. Martin-Delgado

quant-phmath.NTSubmitted May 13, 2026• Announced May 15, 2026• 0 citations
arXivHTMLPDF

Abstract

Solving non-linear Diophantine systems lies at the mathematical core of integer optimization and cryptography. While the general unbounded problem is undecidable, even over bounded integer domains it remains classically intractable in the worst case. In this work, we introduce a fully reversible quantum algorithmic framework tailored to solve arbitrary polynomial Diophantine equations over bounded integer domains. The core of our approach is the explicit, gate-level synthesis of an evaluation oracle for amplitude amplification. By coherently evaluating polynomial constraints via in-place two's complement arithmetic and routing operations into a single recycled accumulator, this garbage-free strategy achieves a compact and scalable synthesis of the underlying non-linear arithmetic. Through analytical derivations and empirical circuit simulations, we prove that the overall spatial complexity is bounded by $q = \mathcal{O}((n + d^2)\log_2 N)$ logical qubits for $n$ variables, maximum degree $d$, and interval length $N$. The non-Clifford Toffoli depth is upper-bounded by $\mathcal{O}(q^2)$. This structural scaling exponent remains invariant to the variable count, modulated linearly only by the coefficients' Hamming weights. By moving beyond abstract black-box assumptions, this explicit architectural synthesis guarantees that the necessary quantum arithmetic acts as a bounded polynomial overhead. This ensures a quadratic speedup over classical exhaustive search, whether retrieving a unique assignment or dynamically enumerating an unknown number of solutions.

Comments
19 pages, 7 figures, 1 table

Related papers

Quantum Algorithms for Magic Square Diophantine Equations

Dimitrios Thanos, Marcello Bonsangue, Alfons Laarman

Magic-square constraints define Diophantine systems whose solutions, in several natural families, exhibit rigid periodic structure. We study this structure in an oracle setting, where a marked set of integers is given by black-box access and the goal is to decide whether it encodes a magic square. For $3\times 3$ magic squares and weighted variants, we prove explicit periodic characterizations that reduce detection to period finding. For larger orders, we identify a class of solutions built from repeated arithmetic patterns, which can be detected via the quantum Fourier transform. We then introduce a shifted-oracle method, based on interference between an oracle and its translates, that helps reconstruct solutions in structured cases. Together, these ingredients give a quantum framework for detecting and reconstructing certain magic-square solutions under suitable assumptions. We also derive finite bounds that make some instances exhaustively solvable and obtain Shor-based criteria for certifying non-existence in restricted number-theoretic settings. As an application, we sketch a quantum communication protocol based on an oracle encoding of a large magic-square solution.

quant-pharXiv:2605.04106•May 5, 2026•0 citations

Quantum Search without Global Diffusion

John Burke, Ciaran McGoldrick

Quantum search is among the most important algorithms in quantum computing. At its core is quantum amplitude amplification, a technique that achieves a quadratic speedup over classical search by combining two global reflections: the oracle, which marks the target, and the diffusion operator, which reflects about the initial state. We show that this speedup can be preserved when the oracle is the only global operator, with all other operations acting locally on non-overlapping partitions of the search register. We present a recursive construction that, when the initial and target states both decompose as tensor products over these chosen partitions, admits an exact closed-form solution for the algorithm's dynamics. This is enabled by an intriguing degeneracy in the principal angles between successive reflections, which collapse to just two distinct values governed by a single recursively defined angle. Applied to unstructured search, a problem that naturally satisfies the tensor decomposition, the approach retains the $O(\sqrt{N})$ oracle complexity of Grover search when each partition contains at least $\log_2(\log_2 N)$ qubits. On an 18-qubit search problem, partitioning into two stages reduces the non-oracle circuit depth by as much as 51%-96% relative to Grover, requiring up to 9% additional oracle calls. For larger problem sizes this oracle overhead rapidly diminishes, and valuable depth reductions persist when the oracle circuit is substantially deeper than the diffusion operator. More broadly, these results show that a global diffusion operator is not necessary to achieve the quadratic speedup in quantum search, offering a new perspective on this foundational algorithm. Moreover, the scalar reduction at the heart of our analysis inspires and motivates new directions and innovations in quantum algorithm design and evaluation.

quant-pharXiv:2604.15435•Apr 20, 2026•2 citations

Quantum algorithms

Pawan Kumar Verma, Mohit Kumar, Saurabh Singhal +1 more

This chapter highlights quantum algorithms as a gate-based computational framework that exploits superposition, entanglement, and phase-coherent interference to realize demonstrable complexity reductions on selected problems. It begins by formally distinguishing quantum algorithms from classical deterministic and randomized computation through reversible unitary evolution, oracle-based problem access, and the measurement constraint that collapses quantum state information, thereby motivating amplitude-engineering strategies that amplify correct outcomes while suppressing incorrect ones. This chapter then surveys quantum speedup as a nuanced concept, clarifying that advantage is problem-dependent, often derived under idealized fault-tolerant assumptions, and practically bounded in noisy intermediate-scale quantum devices by decoherence, gate infidelity, circuit-depth overhead, and benchmarking/verification limitations. Two canonical algorithmic families are developed in depth: Shor’s algorithm, framed as reduction of integer factorization to order/period finding via coherent modular exponentiation and the quantum Fourier transform with explicit resource and cryptographic implications; and Grover’s algorithm, formulated as optimal unstructured search through oracle phase marking, diffusion (inversion about the mean), and its generalization to amplitude amplification as a reusable primitive. Building on these exemplars, this chapter distills design principles for constructing effective quantum algorithms, including superposition management, oracle synthesis and state manipulation, and systematic minimization of gate count, depth, and expensive non-Clifford resources under hardware constraints. It concludes by mapping these foundations to active research directions—quantum approximation methods such as quantum approximate optimization algorithm, hybrid quantum–classical variational workflows, and quantum machine learning—highlighting how practical progress depends on hardware-aware compilation, resource optimization, and interference-driven algorithm design.

CRC Press eBooks•Nov 6, 2026•0 citations

Resource-Scalable Fully Quantum Metropolis-Hastings for Integer Linear Programming

Gabriel Escrig, Roberto Campos, M. A. Martin-Delgado

Integer linear programming (ILP) remains computationally challenging due to its NP-complete nature despite its central role in scheduling, logistics, and design optimization. We introduce a fully quantum Metropolis-Hastings algorithm for ILP that implements a coherent random walk over the discrete feasible region using only reversible quantum circuits, without quantum-RAM assumptions or classical pre/post-processing. Each walk step is a unitary update that prepares coherent candidate moves, evaluates the objective and constraints reversibly -- including a constraint-satisfaction counter to enforce feasibility -- and encodes Metropolis acceptance amplitudes via a low-overhead linearized rule. At the logical level, the construction uses $\mathcal{O}(n\log_2 N)$ qubits to represent $n$ integer variables over the interval $[-N,\,N-1]$, and the Toffoli-equivalent cost per Metropolis step grows linearly with the total logical qubit count. Using explicit ripple-carry adder constructions, we support linear objectives and mixed equality/inequality constraints. Numerical circuit-level simulations on a broad ensemble of randomly generated instances validate the predicted linear resource scaling and exhibit progressive thermalization toward low-cost feasible solutions under the annealing schedule. Overall, the method provides a coherent, resource-characterized baseline for fully quantum constraint programming and a foundation for incorporating additional quantum speedups in combinatorial optimization.

quant-pharXiv:2602.11285•Feb 13, 2026•1 citation

Depth-Optimal Quantum Compilation

Francisca Vasconcelos

We achieve the first constant-depth circuit for arbitrary single-qubit gate synthesis. Unlike prior approaches, the construction is fully unitary and requires no pre-supplied catalyst. For any constant $δ>0$, it $\varepsilon$-approximates an arbitrary single-qubit gate using $O(\log^{1+δ}(1/\varepsilon))$ clean ancillae, Hadamard and $T$ single-qubit gates, $O(\log(1/\varepsilon))$-width generalized Toffoli gates, and sublogarithmic-width Fan-Out gates. We further eliminate Fan-Out entirely, showing that Hadamard, $T$, and generalized Toffoli gates alone suffice for constant-depth synthesis. When restricted to the standard bounded-width gate model, our construction has depth $O(\log\log(1/\varepsilon))$, and we prove a matching $Ω(\log\log(1/\varepsilon))$-depth lower bound. Overall, we establish that $Θ(\log\log(1/\varepsilon))$-depth is unavoidable with only bounded-width gates, yet allowing even logarithmic-width multi-qubit gates suffices to achieve constant-depth synthesis. These results also reveal new structure in shallow quantum circuit complexity. We give a depth-preserving real simulation of bounded-error decision computation, showing that every depth-$d$ QAC circuit can be simulated in depth $O(d)$ using only Hadamard, $X$, and generalized Toffoli gates. Thus arbitrary single-qubit rotations and complex amplitudes do not increase the bounded-error decision power of QAC, even at constant depth. In particular, this reduces the long-standing conjecture Parity$\notin$QAC$^0$ to proving a Parity lower bound against circuits consisting only of Hadamard, $X$, and generalized Toffoli gates. More generally, this real normal form exposes a direct correspondence between the standard shallow-depth quantum circuit hierarchy and a hierarchy of Forrelation circuits with restricted oracle families.

quant-pharXiv:2609.34659•Sep 29, 2026•1 citation

Opening the Black Box inside Grover’s Algorithm

Edwin Miles Stoudenmire, Xavier Waintal

Grover’s algorithm is one of the primary algorithms offered as evidence that quantum computers can provide an advantage over classical computers. It involves an “oracle” (external quantum subroutine), which must be specified for a given application and whose internal structure is not part of the formal scaling of the quadratic quantum speedup guaranteed by the algorithm. Grover’’s algorithm also requires exponentially many calls to the quantum oracle (approximately 2 n calls where n is the number of qubits) to succeed, raising the question of its implementation on both noisy and error-corrected quantum computers. In this work, we construct a quantum-inspired algorithm executable on a classical computer that performs Grover’s task in a linear number of calls to (simulations of) the oracle—an exponentially smaller number than Grover’s algorithm—and demonstrate this algorithm explicitly for Boolean satisfiability problems. The complexity of our algorithm depends on the cost to simulate the oracle once, which may or may not be exponential, depending on its internal structure. Indeed, Grover’s algorithm does not have an quantum speedup as soon as one is given access to the “source code” of the oracle, which may reveal an internal structure of the problem. Our findings illustrate this point explicitly, as our algorithm exploits the structure of the quantum circuit used to program the quantum computer to speed up the search. There are still problems where Grover’s algorithm would provide an asymptotic speedup if it could be run accurately for large enough sizes. Our quantum-inspired algorithm provides lower bounds, in terms of the quantum-circuit complexity, for the quantum hardware to beat classical approaches for these problems. These estimates, combined with the unfavorable scaling of the success probability of Grover’s algorithm, which in the presence of noise decays as the exponential of the exponential of the number of qubits, makes a practical speedup unrealistic even under extremely optimistic assumptions of the evolution of both hardware quality and availability. Published by the American Physical Society 2024

arXiv:2303.11317•Physical Review X•Nov 1, 2024•56 citations
Solving non-linear Diophantine systems lies at the mathematical core of integer optimization and cryptography. While the general unbounded problem is undecidable, even over bounded integer domains it remains classically intractable in the worst case. In this work, we introduce a fully reversible quantum algorithmic framework tailored to solve arbitrary polynomial Diophantine equations over bounded integer domains. The core of our approach is the explicit, gate-level synthesis of an evaluation oracle for amplitude amplification. By coherently evaluating polynomial constraints via in-place two's complement arithmetic and routing operations into a single recycled accumulator, this garbage-free strategy achieves a compact and scalable synthesis of the underlying non-linear arithmetic. Through analytical derivations and empirical circuit simulations, we prove that the overall spatial complexity is bounded by q=O((n+d2)log⁡2N)q = \mathcal{O}((n + d^2)\log_2 N)q=O((n+d2)log2​N) logical qubits for nnn variables, maximum degree ddd, and interval length NNN. The non-Clifford Toffoli depth is upper-bounded by O(q2)\mathcal{O}(q^2)O(q2). This structural scaling exponent remains invariant to the variable count, modulated linearly only by the coefficients' Hamming weights. By moving beyond abstract black-box assumptions, this explicit architectural synthesis guarantees that the necessary quantum arithmetic acts as a bounded polynomial overhead. This ensures a quadratic speedup over classical exhaustive search, whether retrieving a unique assignment or dynamically enumerating an unknown number of solutions.
Magic-square constraints define Diophantine systems whose solutions, in several natural families, exhibit rigid periodic structure. We study this structure in an oracle setting, where a marked set of integers is given by black-box access and the goal is to decide whether it encodes a magic square. For 3×33\times 33×3 magic squares and weighted variants, we prove explicit periodic characterizations that reduce detection to period finding. For larger orders, we identify a class of solutions built from repeated arithmetic patterns, which can be detected via the quantum Fourier transform. We then introduce a shifted-oracle method, based on interference between an oracle and its translates, that helps reconstruct solutions in structured cases. Together, these ingredients give a quantum framework for detecting and reconstructing certain magic-square solutions under suitable assumptions. We also derive finite bounds that make some instances exhaustively solvable and obtain Shor-based criteria for certifying non-existence in restricted number-theoretic settings. As an application, we sketch a quantum communication protocol based on an oracle encoding of a large magic-square solution.
Quantum search is among the most important algorithms in quantum computing. At its core is quantum amplitude amplification, a technique that achieves a quadratic speedup over classical search by combining two global reflections: the oracle, which marks the target, and the diffusion operator, which reflects about the initial state. We show that this speedup can be preserved when the oracle is the only global operator, with all other operations acting locally on non-overlapping partitions of the search register. We present a recursive construction that, when the initial and target states both decompose as tensor products over these chosen partitions, admits an exact closed-form solution for the algorithm's dynamics. This is enabled by an intriguing degeneracy in the principal angles between successive reflections, which collapse to just two distinct values governed by a single recursively defined angle. Applied to unstructured search, a problem that naturally satisfies the tensor decomposition, the approach retains the O(N)O(\sqrt{N})O(N​) oracle complexity of Grover search when each partition contains at least log⁡2(log⁡2N)\log_2(\log_2 N)log2​(log2​N) qubits. On an 18-qubit search problem, partitioning into two stages reduces the non-oracle circuit depth by as much as 51%-96% relative to Grover, requiring up to 9% additional oracle calls. For larger problem sizes this oracle overhead rapidly diminishes, and valuable depth reductions persist when the oracle circuit is substantially deeper than the diffusion operator. More broadly, these results show that a global diffusion operator is not necessary to achieve the quadratic speedup in quantum search, offering a new perspective on this foundational algorithm. Moreover, the scalar reduction at the heart of our analysis inspires and motivates new directions and innovations in quantum algorithm design and evaluation.
This chapter highlights quantum algorithms as a gate-based computational framework that exploits superposition, entanglement, and phase-coherent interference to realize demonstrable complexity reductions on selected problems. It begins by formally distinguishing quantum algorithms from classical deterministic and randomized computation through reversible unitary evolution, oracle-based problem access, and the measurement constraint that collapses quantum state information, thereby motivating amplitude-engineering strategies that amplify correct outcomes while suppressing incorrect ones. This chapter then surveys quantum speedup as a nuanced concept, clarifying that advantage is problem-dependent, often derived under idealized fault-tolerant assumptions, and practically bounded in noisy intermediate-scale quantum devices by decoherence, gate infidelity, circuit-depth overhead, and benchmarking/verification limitations. Two canonical algorithmic families are developed in depth: Shor’s algorithm, framed as reduction of integer factorization to order/period finding via coherent modular exponentiation and the quantum Fourier transform with explicit resource and cryptographic implications; and Grover’s algorithm, formulated as optimal unstructured search through oracle phase marking, diffusion (inversion about the mean), and its generalization to amplitude amplification as a reusable primitive. Building on these exemplars, this chapter distills design principles for constructing effective quantum algorithms, including superposition management, oracle synthesis and state manipulation, and systematic minimization of gate count, depth, and expensive non-Clifford resources under hardware constraints. It concludes by mapping these foundations to active research directions—quantum approximation methods such as quantum approximate optimization algorithm, hybrid quantum–classical variational workflows, and quantum machine learning—highlighting how practical progress depends on hardware-aware compilation, resource optimization, and interference-driven algorithm design.
Integer linear programming (ILP) remains computationally challenging due to its NP-complete nature despite its central role in scheduling, logistics, and design optimization. We introduce a fully quantum Metropolis-Hastings algorithm for ILP that implements a coherent random walk over the discrete feasible region using only reversible quantum circuits, without quantum-RAM assumptions or classical pre/post-processing. Each walk step is a unitary update that prepares coherent candidate moves, evaluates the objective and constraints reversibly -- including a constraint-satisfaction counter to enforce feasibility -- and encodes Metropolis acceptance amplitudes via a low-overhead linearized rule. At the logical level, the construction uses O(nlog⁡2N)\mathcal{O}(n\log_2 N)O(nlog2​N) qubits to represent nnn integer variables over the interval [−N, N−1][-N,\,N-1][−N,N−1], and the Toffoli-equivalent cost per Metropolis step grows linearly with the total logical qubit count. Using explicit ripple-carry adder constructions, we support linear objectives and mixed equality/inequality constraints. Numerical circuit-level simulations on a broad ensemble of randomly generated instances validate the predicted linear resource scaling and exhibit progressive thermalization toward low-cost feasible solutions under the annealing schedule. Overall, the method provides a coherent, resource-characterized baseline for fully quantum constraint programming and a foundation for incorporating additional quantum speedups in combinatorial optimization.
We achieve the first constant-depth circuit for arbitrary single-qubit gate synthesis. Unlike prior approaches, the construction is fully unitary and requires no pre-supplied catalyst. For any constant δ>0δ>0δ>0, it ε\varepsilonε-approximates an arbitrary single-qubit gate using O(log⁡1+δ(1/ε))O(\log^{1+δ}(1/\varepsilon))O(log1+δ(1/ε)) clean ancillae, Hadamard and TTT single-qubit gates, O(log⁡(1/ε))O(\log(1/\varepsilon))O(log(1/ε))-width generalized Toffoli gates, and sublogarithmic-width Fan-Out gates. We further eliminate Fan-Out entirely, showing that Hadamard, TTT, and generalized Toffoli gates alone suffice for constant-depth synthesis. When restricted to the standard bounded-width gate model, our construction has depth O(log⁡log⁡(1/ε))O(\log\log(1/\varepsilon))O(loglog(1/ε)), and we prove a matching Ω(log⁡log⁡(1/ε))Ω(\log\log(1/\varepsilon))Ω(loglog(1/ε))-depth lower bound. Overall, we establish that Θ(log⁡log⁡(1/ε))Θ(\log\log(1/\varepsilon))Θ(loglog(1/ε))-depth is unavoidable with only bounded-width gates, yet allowing even logarithmic-width multi-qubit gates suffices to achieve constant-depth synthesis. These results also reveal new structure in shallow quantum circuit complexity. We give a depth-preserving real simulation of bounded-error decision computation, showing that every depth-ddd QAC circuit can be simulated in depth O(d)O(d)O(d) using only Hadamard, XXX, and generalized Toffoli gates. Thus arbitrary single-qubit rotations and complex amplitudes do not increase the bounded-error decision power of QAC, even at constant depth. In particular, this reduces the long-standing conjecture Parity∉\notin∈/QAC0^00 to proving a Parity lower bound against circuits consisting only of Hadamard, XXX, and generalized Toffoli gates. More generally, this real normal form exposes a direct correspondence between the standard shallow-depth quantum circuit hierarchy and a hierarchy of Forrelation circuits with restricted oracle families.
Grover’s algorithm is one of the primary algorithms offered as evidence that quantum computers can provide an advantage over classical computers. It involves an “oracle” (external quantum subroutine), which must be specified for a given application and whose internal structure is not part of the formal scaling of the quadratic quantum speedup guaranteed by the algorithm. Grover’’s algorithm also requires exponentially many calls to the quantum oracle (approximately 2 n calls where n is the number of qubits) to succeed, raising the question of its implementation on both noisy and error-corrected quantum computers. In this work, we construct a quantum-inspired algorithm executable on a classical computer that performs Grover’s task in a linear number of calls to (simulations of) the oracle—an exponentially smaller number than Grover’s algorithm—and demonstrate this algorithm explicitly for Boolean satisfiability problems. The complexity of our algorithm depends on the cost to simulate the oracle once, which may or may not be exponential, depending on its internal structure. Indeed, Grover’s algorithm does not have an quantum speedup as soon as one is given access to the “source code” of the oracle, which may reveal an internal structure of the problem. Our findings illustrate this point explicitly, as our algorithm exploits the structure of the quantum circuit used to program the quantum computer to speed up the search. There are still problems where Grover’s algorithm would provide an asymptotic speedup if it could be run accurately for large enough sizes. Our quantum-inspired algorithm provides lower bounds, in terms of the quantum-circuit complexity, for the quantum hardware to beat classical approaches for these problems. These estimates, combined with the unfavorable scaling of the success probability of Grover’s algorithm, which in the presence of noise decays as the exponential of the exponential of the number of qubits, makes a practical speedup unrealistic even under extremely optimistic assumptions of the evolution of both hardware quality and availability. Published by the American Physical Society 2024