Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userQuantum Annealing for Prime Factorization
101
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We have developed a framework to convert an arbitrary integer factorization problem to an executable Ising model by first writing it as an optimization function and then transforming the k-bit coupling ($kgeq 3$) terms to quadratic terms using ancillary variables. The method is efficient and uses $mathcal{O}(text{log}^2(N))$ binary variables (qubits) for finding the factors of integer $N$. The method was tested using the D-Wave 2000Q for finding an embedding and determining the prime factors for a given composite number. As examples, we present quantum annealing results for factoring 15, 143, 59989, and 376289 using 4, 12, 59, and 94 logical qubits respectively. The method is general and could be used to factor larger numbers
rate research
Read More
We investigate prime factorization from two perspectives: quantum annealing and computational algebraic geometry, specifically Grobner bases. We present a novel scalable algorithm which combines the two approaches and leads to the factorization of all bi-primes up to just over $200 , 000$, the largest number factored to date using a quantum processor.
We propose a prime factorizer operated in a framework of quantum annealing (QA). The idea is inverse operation of a multiplier implemented with QA-based Boolean logic circuits. We designed the QA machine on an application-specific-annealing-computing architecture which efficiently increases available hardware budgets at the cost of restricted functionality. The invertible operation of QA logic gates consisting of superconducting flux qubits was confirmed by circuit simulation with classical noise sources. The circuits were implemented and fabricated by using superconducting integrated circuit technologies with Nb/AlOx/Nb Josephson junctions. We also propose a 2.5Dimensional packaging scheme of a qubit-chip/interpose /package-substrate structure for realizing practically large-scale QA systems.
The road to computing on quantum devices has been accelerated by the promises that come from using Shors algorithm to reduce the complexity of prime factorization. However, this promise hast not yet been realized due to noisy qubits and lack of robust error correction schemes. Here we explore a promising, alternative method for prime factorization that uses well-established techniques from variational imaginary time evolution. We create a Hamiltonian whose ground state encodes the solution to the problem and use variational techniques to evolve a state iteratively towards these prime factors. We show that the number of circuits evaluated in each iteration scales as O(n^{5}d), where n is the bit-length of the number to be factorized and $d$ is the depth of the circuit. We use a single layer of entangling gates to factorize several numbers represented using 7, 8, and 9-qubit Hamiltonians. We also verify the methods performance by implementing it on the IBMQ Lima hardware.
New annealing schedules for quantum annealing are proposed based on the adiabatic theorem. These schedules exhibit faster decrease of the excitation probability than a linear schedule. To derive this conclusion, the asymptotic form of the excitation probability for quantum annealing is explicitly obtained in the limit of long annealing time. Its first-order term, which is inversely proportional to the square of the annealing time, is shown to be determined only by the information at the initial and final times. Our annealing schedules make it possible to drop this term, thus leading to a higher order (smaller) excitation probability. We verify these results by solving numerically the time-dependent Schrodinger equation for small size systems
Classical and quantum annealing are two heuristic optimization methods that search for an optimal solution by slowly decreasing thermal or quantum fluctuations. Optimizing annealing schedules is important both for performance and fair comparisons between classical annealing, quantum annealing, and other algorithms. Here we present a heuristic approach for the optimization of annealing schedules for quantum annealing and apply it to 3D Ising spin glass problems. We find that if both classical and quantum annealing schedules are similarly optimized, classical annealing outperforms quantum annealing for these problems when considering the residual energy obtained in slow annealing. However, when performing many repetitions of fast annealing, simulated quantum annealing is seen to outperform classical annealing for our benchmark problems.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
