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:2312.10054

Efficient Quantum Oracle for Solving Bilinear Diophantine Equations on Digital Quantum Computers

S. Whitlock, Tien D. Kieu

Published Dec 3, 2023• 0 citations
arXivHTMLPDF

Abstract

We present a concrete oracle construction for bilinear Diophantine equations of the form $f(x,y) = Axy + Bx + Cy + D$, together with its application as a scalable, hardware-agnostic benchmark for digital quantum computers. The oracle can be used in a Grover search algorithm in two variants suitable for both noisy-intermediate scale quantum devices and early fault-tolerant quantum processors. Applied to integer factoring via a residue-class encoding, the circuit requires $2n-5$ qubits or fewer to factor an $n$-bit biprime $N = pq$; for $N = 143$ requiring as few as 7 qubits and 135 two-qubit gates compared to 19 qubits and 51,048 two-qubit gates for a qubit-efficient variant of Shor's algorithm. Large-scale simulations confirm a success probability approaching 100\% for $>$800 randomly selected biprimes with $5 \leq n \leq 35$. The circuit family provides a scalable, deterministically convergent and easily verifiable benchmark in a range accessible to near term quantum hardware.

DOI
10.48550/arxiv.2312.10054

Related papers

Efficient Quantum Circuit Synthesis for SAT-Oracle With Limited Ancillary Qubit

Shuai Yang, Wei Zi, Bujiao Wu +3 more

One of the main concerns in the era of noisy intermediate-scale quantum (NISQ) computing and fault-tolerant quantum computing is the optimization of circuit implementation for quantum oracles, particularly with limited resources. Synthesizing a satisfiability (SAT) oracle, a crucial component in solving SAT problems, presents a significant challenge. The current state-of-the-art implementation of an$m$-clause SAT-oracle necessitates$2m-1$ancillary qubits and a linear number of elementary gates. We develop two efficient and ancilla-adjustable synthesis algorithms to reduce the overall quantum resource usage. Our first quantum oracle algorithm achieves quadratic optimization in the number of ancillary qubits with merely eight times increased circuit size. We also show that using only three ancillary qubits with quadratic circuit size expansion is enough. Our second algorithm optimizes the circuit depth of the SAT oracle to$\tilde {O}(\log m)$using$m$ancillary qubits. By running our algorithms on classical intractable SAT instances featured in SAT competitions, the experiment results show that our required quantum resources align well with our theoretical analysis. Our algorithms highlight the scalability of SAT-oracle-based algorithms in near-term quantum devices, such as Grover’s algorithm.

arXiv:2101.05430•IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•Oct 19, 2023•3 citations

Solving the integer case constraint satisfiability problem using Grover's algorithm

Gayathree M. Vinod, Anil Shaji

Constraint satisfiability problems, crucial to several applications, are solved on a quantum computer using the Grover's search algorithm, leading to a quadratic improvement over the classical case. The solutions are obtained with high probability for several cases and are illustrated for the cases involving 2 variables for both 3-bit and 4-bit numbers. Methods are defined for inequality comparisons and these are combined according to the form of the satisfiability formula, to form the oracle for the algorithm. The circuit is constructed using IBM Qiskit and is verified on an IBM simulator. It is further executed on one of the Noisy Intermediate-Scale Quantum (NISQ) processors from IBM on the cloud. Noise levels in the processor at present are found to be too high for successful execution. Running the algorithm on the simulator with a custom noise model lets us identify the noise threshold for successful execution.

•Jun 18, 2021•0 citations

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

Finding Solutions to the Integer Case Constraint Satisfiability Problem Using Grover’s Algorithm

Gayathree M. Vinod, Anil Shaji

Constraint satisfiability problems, crucial to several applications, are solved on a quantum computer using Grover's search algorithm, leading to a quadratic improvement over the classical case. The solutions are obtained with high probability for several cases and are illustrated for the cases involving two variables for both 3- and 4-bit numbers. Methods are defined for inequality comparisons, and these are combined according to the form of the satisfiability formula, to form the oracle for the algorithm. The circuit is constructed using IBM Qiskit and is verified on an IBM simulator. It is further executed on one of the Noisy Intermediate-Scale Quantum (NISQ) processors from IBM on the cloud. Noise levels in the processor at present are found to be too high for successful execution. Running the algorithm on the simulator with a custom noise model lets us identify the noise threshold for successful execution.

arXiv:2106.09976•IEEE Transactions on Quantum Engineering•Jan 1, 2021•12 citations

Automated quantum oracle synthesis with a minimal number of qubits

Jessie M. Henderson, Elena R. Henderson, Aviraj Sinha +2 more

Several prominent quantum computing algorithms—including Grover’s search algorithm and Shor’s algorithm for finding the prime factorization of an integer—employ subcircuits termed ‘oracles’ that embed a specific instance of a mathematical function into a corresponding bijective function that is then realized as a quantum circuit representation. Designing oracles, and particularly, designing them to be optimized for a particular use case, can be a non-trivial task. For example, the challenge of implementing quantum circuits in the current era of NISQ-based quantum computers generally dictates that they should be designed with a minimal number of qubits, as larger qubit counts increase the likelihood that computations will fail due to one or more of the qubits decohering. However, some quantum circuits require that function domain values be preserved, which can preclude using the minimal number of qubits in the oracle circuit. Thus, quantum oracles must be designed with a particular application in mind. In this work, we present two methods for automatic quantum oracle synthesis. One of these methods uses a minimal number of qubits, while the other preserves the function domain values while also minimizing the overall required number of qubits. For each method, we describe known quantum circuit use cases, and illustrate implementation using an automated quantum compilation and optimization tool to synthesize oracles for a set of benchmark functions; we can then compare the methods with metrics including required qubit count and quantum circuit complexity.

arXiv:2304.03829•Jun 13, 2023•8 citations

Automatic Generation of Grover Quantum Oracles for Arbitrary Data Structures

Raphael Seidel, Colin Kai‐Uwe Becker, Bock, Sebastian +3 more

The steadily growing research interest in quantum computing - together with the accompanying technological advances in the realization of quantum hardware - fuels the development of meaningful real-world applications, as well as implementations for well-known quantum algorithms. One of the most prominent examples till today is Grover's algorithm, which can be used for efficient search in unstructured databases. Quantum oracles that are frequently masked as black boxes play an important role in Grover's algorithm. Hence, the automatic generation of oracles is of paramount importance. Moreover, the automatic generation of the corresponding circuits for a Grover quantum oracle is deeply linked to the synthesis of reversible quantum logic, which - despite numerous advances in the field - still remains a challenge till today in terms of synthesizing efficient and scalable circuits for complex boolean functions. In this paper, we present a flexible method for automatically encoding unstructured databases into oracles, which can then be efficiently searched with Grover's algorithm. Furthermore, we develop a tailor-made method for quantum logic synthesis, which vastly improves circuit complexity over other current approaches. Finally, we present another logic synthesis method that considers the requirements of scaling onto real world backends. We compare our method with other approaches through evaluating the oracle generation for random databases and analyzing the resulting circuit complexities using various metrics.

arXiv:2110.07545•Oct 14, 2021•2 citations
We present a concrete oracle construction for bilinear Diophantine equations of the form f(x,y)=Axy+Bx+Cy+Df(x,y) = Axy + Bx + Cy + Df(x,y)=Axy+Bx+Cy+D, together with its application as a scalable, hardware-agnostic benchmark for digital quantum computers. The oracle can be used in a Grover search algorithm in two variants suitable for both noisy-intermediate scale quantum devices and early fault-tolerant quantum processors. Applied to integer factoring via a residue-class encoding, the circuit requires 2n−52n-52n−5 qubits or fewer to factor an nnn-bit biprime N=pqN = pqN=pq; for N=143N = 143N=143 requiring as few as 7 qubits and 135 two-qubit gates compared to 19 qubits and 51,048 two-qubit gates for a qubit-efficient variant of Shor's algorithm. Large-scale simulations confirm a success probability approaching 100% for >>>800 randomly selected biprimes with 5≤n≤355 \leq n \leq 355≤n≤35. The circuit family provides a scalable, deterministically convergent and easily verifiable benchmark in a range accessible to near term quantum hardware.
One of the main concerns in the era of noisy intermediate-scale quantum (NISQ) computing and fault-tolerant quantum computing is the optimization of circuit implementation for quantum oracles, particularly with limited resources. Synthesizing a satisfiability (SAT) oracle, a crucial component in solving SAT problems, presents a significant challenge. The current state-of-the-art implementation of anmmm-clause SAT-oracle necessitates2m−12m-12m−1ancillary qubits and a linear number of elementary gates. We develop two efficient and ancilla-adjustable synthesis algorithms to reduce the overall quantum resource usage. Our first quantum oracle algorithm achieves quadratic optimization in the number of ancillary qubits with merely eight times increased circuit size. We also show that using only three ancillary qubits with quadratic circuit size expansion is enough. Our second algorithm optimizes the circuit depth of the SAT oracle toO~(log⁡m)\tilde {O}(\log m)O~(logm)usingmmmancillary qubits. By running our algorithms on classical intractable SAT instances featured in SAT competitions, the experiment results show that our required quantum resources align well with our theoretical analysis. Our algorithms highlight the scalability of SAT-oracle-based algorithms in near-term quantum devices, such as Grover’s algorithm.
Constraint satisfiability problems, crucial to several applications, are solved on a quantum computer using the Grover's search algorithm, leading to a quadratic improvement over the classical case. The solutions are obtained with high probability for several cases and are illustrated for the cases involving 2 variables for both 3-bit and 4-bit numbers. Methods are defined for inequality comparisons and these are combined according to the form of the satisfiability formula, to form the oracle for the algorithm. The circuit is constructed using IBM Qiskit and is verified on an IBM simulator. It is further executed on one of the Noisy Intermediate-Scale Quantum (NISQ) processors from IBM on the cloud. Noise levels in the processor at present are found to be too high for successful execution. Running the algorithm on the simulator with a custom noise model lets us identify the noise threshold for successful execution.
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.
Constraint satisfiability problems, crucial to several applications, are solved on a quantum computer using Grover's search algorithm, leading to a quadratic improvement over the classical case. The solutions are obtained with high probability for several cases and are illustrated for the cases involving two variables for both 3- and 4-bit numbers. Methods are defined for inequality comparisons, and these are combined according to the form of the satisfiability formula, to form the oracle for the algorithm. The circuit is constructed using IBM Qiskit and is verified on an IBM simulator. It is further executed on one of the Noisy Intermediate-Scale Quantum (NISQ) processors from IBM on the cloud. Noise levels in the processor at present are found to be too high for successful execution. Running the algorithm on the simulator with a custom noise model lets us identify the noise threshold for successful execution.
Several prominent quantum computing algorithms—including Grover’s search algorithm and Shor’s algorithm for finding the prime factorization of an integer—employ subcircuits termed ‘oracles’ that embed a specific instance of a mathematical function into a corresponding bijective function that is then realized as a quantum circuit representation. Designing oracles, and particularly, designing them to be optimized for a particular use case, can be a non-trivial task. For example, the challenge of implementing quantum circuits in the current era of NISQ-based quantum computers generally dictates that they should be designed with a minimal number of qubits, as larger qubit counts increase the likelihood that computations will fail due to one or more of the qubits decohering. However, some quantum circuits require that function domain values be preserved, which can preclude using the minimal number of qubits in the oracle circuit. Thus, quantum oracles must be designed with a particular application in mind. In this work, we present two methods for automatic quantum oracle synthesis. One of these methods uses a minimal number of qubits, while the other preserves the function domain values while also minimizing the overall required number of qubits. For each method, we describe known quantum circuit use cases, and illustrate implementation using an automated quantum compilation and optimization tool to synthesize oracles for a set of benchmark functions; we can then compare the methods with metrics including required qubit count and quantum circuit complexity.
The steadily growing research interest in quantum computing - together with the accompanying technological advances in the realization of quantum hardware - fuels the development of meaningful real-world applications, as well as implementations for well-known quantum algorithms. One of the most prominent examples till today is Grover's algorithm, which can be used for efficient search in unstructured databases. Quantum oracles that are frequently masked as black boxes play an important role in Grover's algorithm. Hence, the automatic generation of oracles is of paramount importance. Moreover, the automatic generation of the corresponding circuits for a Grover quantum oracle is deeply linked to the synthesis of reversible quantum logic, which - despite numerous advances in the field - still remains a challenge till today in terms of synthesizing efficient and scalable circuits for complex boolean functions. In this paper, we present a flexible method for automatically encoding unstructured databases into oracles, which can then be efficiently searched with Grover's algorithm. Furthermore, we develop a tailor-made method for quantum logic synthesis, which vastly improves circuit complexity over other current approaches. Finally, we present another logic synthesis method that considers the requirements of scaling onto real world backends. We compare our method with other approaches through evaluating the oracle generation for random databases and analyzing the resulting circuit complexities using various metrics.