Related papers: Experimental factoring integers using fixed-point-QAOA with a trapped-ion quantum processor

Experimental factoring integers using fixed-point-QAOA with a trapped-ion quantum processor

URL: http://arxiv.org/abs/2503.10588v1
Date: Thu, 13 Mar 2025 17:40:07 GMT
Title: Experimental factoring integers using fixed-point-QAOA with a trapped-ion quantum processor
Authors: Ilia V. Zalivako, Andrey Yu. Chernyavskiy, Anastasiia S. Nikolaeva, Alexander S. Borisenko, Nikita V. Semenin, Kristina P. Galstyan, Andrey E. Korolkov, Sergey V. Grebnev, Evgeniy O. Kiktenko, Ksenia Yu. Khabarova, Aleksey K. Fedorov, Ilya A. Semerikov, Nikolay N. Kolachevsky,
Abstract summary: We experimentally demonstrate factoring of the integer with a trapped ion quantum processor using the Schnorr approach and a modified version of quantum approximate optimization algorithm (QAOA)<n>We present experimental results on factoring $1591=37times43$ using 6 qubits as well as simulation results for $746579521times7817$ with 10 qubits and $35183361263263=4194191times8388593$ with 15 qubits.
Score: 30.867632812964743
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Factoring integers is considered as a computationally-hard problem for classical methods, whereas there exists polynomial-time Shor's quantum algorithm for solving this task. However, requirements for running the Shor's algorithm for realistic tasks, which are beyond the capabilities of existing and upcoming generations of quantum computing devices, motivates to search for alternative approaches. In this work, we experimentally demonstrate factoring of the integer with a trapped ion quantum processor using the Schnorr approach and a modified version of quantum approximate optimization algorithm (QAOA). The key difference of our approach in comparison with the recently proposed QAOA-based factoring method is the use of the fixed-point feature, which relies on the use of universal parameters. We present experimental results on factoring $1591=37\times43$ using 6 qubits as well as simulation results for $74425657=9521\times7817$ with 10 qubits and $35183361263263=4194191\times8388593$ with 15 qubits. Alongside, we present all the necessary details for reproducing our results and analysis of the performance of the factoring method, the scalability of this approach both in classical and quantum domain still requires further studies.

Related papers

Fast Expectation Value Calculation Speedup of Quantum Approximate Optimization Algorithm: HoLCUs QAOA [55.2480439325792]
We present a new method for calculating expectation values of operators that can be expressed as a linear combination of unitary (LCU) operators.<n>This method is general for any quantum algorithm and is of particular interest in the acceleration of variational quantum algorithms.
arXiv Detail & Related papers (2025-03-03T17:15:23Z)
Bias-Field Digitized Counterdiabatic Quantum Algorithm for Higher-Order Binary Optimization [39.58317527488534]
We present an enhanced bias-field digitized counterdiabatic quantum optimization (BF-DCQO) algorithm to address higher-order unconstrained binary optimization (HUBO) problems. Our protocol is experimentally validated using 156 qubits on an IBM quantum processor with a heavy-hex architecture.
arXiv Detail & Related papers (2024-09-05T17:38:59Z)
Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
arXiv Detail & Related papers (2024-08-14T19:04:13Z)
Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
arXiv Detail & Related papers (2024-01-17T18:59:38Z)
Integer Factorization through Func-QAOA [0.0]
No efficient classical algorithm for cryptographic-time integer factorization has been found. We present the Func-QAOA approach for factorization, which premises overcoming some of the limitations of previous approaches.
arXiv Detail & Related papers (2023-09-26T18:00:25Z)
Pitfalls of the sublinear QAOA-based factorization algorithm [0.8987776881291144]
The prime factorization problem is at the heart of widely deployed public-key cryptographic tools. The implementation of Shor's quantum factorization algorithm requires significant resources scaling linearly with the number size. Recent proposal by Yan et al. claims a possibility of solving the factorization problem with sublinear quantum resources.
arXiv Detail & Related papers (2023-03-08T15:23:50Z)
Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
arXiv Detail & Related papers (2022-06-30T03:15:23Z)
Using Shor's algorithm on near term Quantum computers: a reduced version [0.0]
We introduce a reduced version of Shor's algorithm that proposes a step forward in increasing the range of numbers that can be factorized on noisy Quantum devices. In particular, we have found noteworthy results in most cases, often being able to factor the given number with only one of the proposed algorithm.
arXiv Detail & Related papers (2021-12-23T15:36:59Z)
Optimization and Noise Analysis of the Quantum Algorithm for Solving One-Dimensional Poisson Equation [17.65730040410185]
We propose an efficient quantum algorithm for solving one-dimensional Poisson equation. We further develop this algorithm to make it closer to the real application on the noisy intermediate-scale quantum (NISQ) devices. We analyze the effect of common noise existing in the real quantum devices on our algorithm using the IBM Qiskit toolkit.
arXiv Detail & Related papers (2021-08-27T09:44:41Z)
Quantum mean value approximator for hard integer value problems [19.4417702222583]
We show that an optimization can be improved substantially by using an approximation rather than the exact expectation. Together with efficient classical sampling algorithms, a quantum algorithm with minimal gate count can thus improve the efficiency of general integer-value problems.
arXiv Detail & Related papers (2021-05-27T13:03:52Z)
Analyzing the Performance of Variational Quantum Factoring on a Superconducting Quantum Processor [0.0]
We study a QAOA-based quantum optimization algorithm by implementing the Variational Quantum Factoring (VQF) algorithm. We demonstrate the impact of different noise sources on the performance of QAOA and reveal the coherent error caused by the residual ZZ-coupling between qubits.
arXiv Detail & Related papers (2020-12-14T18:58:30Z)
Efficient phase-factor evaluation in quantum signal processing [1.3614427997190908]
Quantum signal processing (QSP) is a powerful quantum algorithm to exactly implement matrixs on quantum computers. There is so far no classically stable algorithm allowing computation of the phase factors that are needed to build QSP circuits. We present here an optimization based method that can accurately compute the phase factors using standard double precision arithmetic operations.
arXiv Detail & Related papers (2020-02-26T17:23:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.