Efficient Quantum Oracle for Solving Bilinear Diophantine Equations on Digital Quantum Computers
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915996294447104 |
|---|---|
| author | Whitlock, S. Kieu, T. D. |
| author_facet | Whitlock, S. Kieu, T. D. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_10054 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Efficient Quantum Oracle for Solving Bilinear Diophantine Equations on Digital Quantum Computers Whitlock, S. Kieu, T. D. General Physics 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. |
| title | Efficient Quantum Oracle for Solving Bilinear Diophantine Equations on Digital Quantum Computers |
| topic | General Physics |
| url | https://arxiv.org/abs/2312.10054 |