We investigate the performance of a streamlined version of Shor's algorithm in which the quantum Fourier transform is replaced by a banded version that, for each qubit, retains only coupling to its $b$ nearest neighbors. Defining the performance $P(n,b)$ of the $n$ -qubit algorithm for bandwidth $b$ as the ratio of the success rates of Shor's algorithm equipped with the banded and the full-bandwidth ($b=n\ensuremath{-}1$) versions of the quantum Fourier transform, our numerical simulations show that $P(n,b)\ensuremath{\approx}\mathrm{exp}[\ensuremath{-}{\ensuremath{\varphi}}_{\mathrm{max}}^{2}(n,b)/100]$ for $n<{n}_{t}(b)$ (nonexponential regime) and $P(n,b)\ensuremath{\approx}{2}^{\ensuremath{-}{\ensuremath{\xi}}_{b}(n\ensuremath{-}8)}$ for $n>{n}_{t}(b)$ (exponential regime), where ${n}_{t}(b)$ , the location of the transition, is approximately given by ${n}_{t}(b)\ensuremath{\approx}b+5.9+\sqrt{7.7(b+2)\ensuremath{-}47}$ for $b\ensuremath{\gtrsim}8$, ${\ensuremath{\varphi}}_{\mathrm{max}}(n,b)=2\ensuremath{\pi}[{2}^{\ensuremath{-}b\ensuremath{-}1}(n\ensuremath{-}b\ensuremath{-}2)+{2}^{\ensuremath{-}n}]$, and ${\ensuremath{\xi}}_{b}\ensuremath{\approx}1.1\ifmmode\times\else\texttimes\fi{}{2}^{\ensuremath{-}2b}$. Analytically we obtain $P(n,b)\ensuremath{\approx}\mathrm{exp}[\ensuremath{-}{\ensuremath{\varphi}}_{\mathrm{max}}^{2}(n,b)/64]$ for $n<{n}_{t}(b)$ and $P(n,b)\ensuremath{\approx}{2}^{\ensuremath{-}{\ensuremath{\xi}}_{b}^{(a)}n}$ for $n>{n}_{t}(b)$ , where ${\ensuremath{\xi}}_{b}^{(a)}\ensuremath{\approx}\frac{{\ensuremath{\pi}}^{2}}{12\mathrm{ln}(2)}\ifmmode\times\else\texttimes\fi{}{2}^{\ensuremath{-}2b}\ensuremath{\approx}1.19\ifmmode\times\else\texttimes\fi{}{2}^{\ensuremath{-}2b}$. Thus, our analytical results predict the ${\ensuremath{\varphi}}_{\mathrm{max}}^{2}$ scaling ( $n<{n}_{t}$ ) and the ${2}^{\ensuremath{-}2b}$ scaling ( $n>{n}_{t}$ ) of the data perfectly. In addition, in the large- $n$ regime, the prefactor in ${\ensuremath{\xi}}_{b}^{(a)}$ is close to the results of our numerical simulations, and in the low- $n$ regime, the numerical scaling factor in our analytical result is within a factor 2 of its numerical value. As an example we show that $b=8$ is sufficient for factoring RSA-2048 with a 95 $%$ success rate.We investigate the performance of a streamlined version of Shor's algorithm in which the quantum Fourier transform is replaced by a banded version that, for each qubit, retains only coupling to its $b$ nearest neighbors. Defining the performance $P(n,b)$ of the $n$-qubit algorithm for bandwidth $b$ as the ratio of the success rates of Shor's algorithm equipped with the banded and the full-bandwidth ($b=n\ensuremath{-}1$) versions of the quantum Fourier transform, our numerical simulations show that $P(n,b)\ensuremath{\approx}\mathrm{exp}[\ensuremath{-}{\ensuremath{\varphi}}_{\mathrm{max}}^{2}(n,b)/100]$ for $n<{n}_{t}(b)$ (nonexponential regime) and $P(n,b)\ensuremath{\approx}{2}^{\ensuremath{-}{\ensuremath{\xi}}_{b}(n\ensuremath{-}8)}$ for $n>{n}_{t}(b)$ (exponential regime), where ${n}_{t}(b)$, the location of the transition, is approximately given by ${n}_{t}(b)\ensuremath{\approx}b+5.9+\sqrt{7.7(b+2)\ensuremath{-}47}$ for $b\ensuremath{\gtrsim}8$, ${\ensuremath{\varphi}}_{\mathrm{max}}(n,b)=2\ensuremath{\pi}[{2}^{\ensuremath{-}b\ensuremath{-}1}(n\ensuremath{-}b\ensuremath{-}2)+{2}^{\ensuremath{-}n}]$, and ${\ensuremath{\xi}}_{b}\ensuremath{\approx}1.1\ifmmode\times\else\texttimes\fi{}{2}^{\ensuremath{-}2b}$. Analytically we obtain $P(n,b)\ensuremath{\approx}\mathrm{exp}[\ensuremath{-}{\ensuremath{\varphi}}_{\mathrm{max}}^{2}(n,b)/64]$ for $n<{n}_{t}(b)$ and $P(n,b)\ensuremath{\approx}{2}^{\ensuremath{-}{\ensuremath{\xi}}_{b}^{(a)}n}$ for $n>{n}_{t}(b)$, where ${\ensuremath{\xi}}_{b}^{(a)}\ensuremath{\approx}\frac{{\ensuremath{\pi}}^{2}}{12\mathrm{ln}(2)}\ifmmode\times\else\texttimes\fi{}{2}^{\ensuremath{-}2b}\ensuremath{\approx}1.19\ifmmode\times\else\texttimes\fi{}{2}^{\ensuremath{-}2b}$. Thus, our analytical results predict the ${\ensuremath{\varphi}}_{\mathrm{max}}^{2}$ scaling ($n<{n}_{t}$) and the ${2}^{\ensuremath{-}2b}$ scaling ($n>{n}_{t}$) of the data perfectly. In addition, in the large-$n$ regime, the prefactor in ${\ensuremath{\xi}}_{b}^{(a)}$ is close to the results of our numerical simulations, and in the low-$n$ regime, the numerical scaling factor in our analytical result is within a factor 2 of its numerical value. As an example we show that $b=8$ is sufficient for factoring RSA-2048 with a 95$%$ success rate.

arXiv:1302.5844Physical Review AMar 27, 201323 citations

Algorithm for Quantum Factorization

Samuel Čarnoký

Jan 1, 20080 citations

phase2: full-state vector simulation of quantum time evolution at scale

Marek Miller, Jakob Günther, Freek Witteveen +5 more

Abstract Large-scale classical simulation of quantum computers is crucial for benchmarking quantum algorithms, establishing boundaries of quantum advantage and exploring heuristic quantum algorithms. We present a full-state vector simulation algorithm and software implementation designed to perform HPC simulation of layers of rotations around a string of Pauli operators. We demonstrate robust scalability of the simulation method on large distributed CPU and GPU systems. Our distributed computation harnessed up to 16384 CPU cores and 512 NVIDIA H100 GPUs, using 32 TB of memory. The simulator significantly outperforms other high-performance libraries, showing a typical speedup of 10-100 for large-scale multi-GPU workloads. As a first application of our approach, we report a numerical experiment aimed at simulating exactly Hamiltonian dynamics of up to 40 qubits to investigate the Trotter error for a quantum chemistry problem. Bounding the Trotter error is important for evaluating the cost of quantum algorithms for chemistry, and rigorous bounds are often conservative, as our simulations confirm. Our software, specifically designed for quantum time evolution applications, is also well equipped to manage circuits that utilize standard gate sets.Abstract Large-scale classical simulation of quantum computers is crucial for benchmarking quantum algorithms, establishing boundaries of quantum advantage and exploring heuristic quantum algorithms. We present a full-state vector simulation algorithm and software implementation designed to perform HPC simulation of layers of rotations around a string of Pauli operators. We demonstrate robust scalability of the simulation method on large distributed CPU and GPU systems. Our distributed computation harnessed up to 16384 CPU cores and 512 NVIDIA H100 GPUs, using 32 TB of memory. The simulator significantly outperforms other high-performance libraries, showing a typical speedup of 10-100 for large-scale multi-GPU workloads. As a first application of our approach, we report a numerical experiment aimed at simulating exactly Hamiltonian dynamics of up to 40 qubits to investigate the Trotter error for a quantum chemistry problem. Bounding the Trotter error is important for evaluating the cost of quantum algorithms for chemistry, and rigorous bounds are often conservative, as our simulations confirm. Our software, specifically designed for quantum time evolution applications, is also well equipped to manage circuits that utilize standard gate sets.

arXiv:2504.17881Communications AI & ComputingJul 14, 20262 citations

A Numerical Simulation of Quantum Factorization Success Probability

Piotr Zawadzki

Advances in intelligent and soft computingJan 1, 20095 citations

Streamlining Shor's algorithm for potential hardware savings

Yunseong Nam, R. Blümel

We constructed a virtual quantum computer by running a complete, scaling, quantum-gate--by--quantum-gate implementation of Shor's algorithm on a 128-core classical cluster computer. In mode A [quantum period finding (PF) only, supplied with classical results for the modular exponentiation (ME) part of Shor's algorithm], factoring semiprimes up to $N=557\phantom{\rule{0.16em}{0ex}}993$ with up to $n=39$ qubits, we confirm earlier, smaller- $n$ results concerning the performance scaling of Shor's algorithm equipped with a truncated (banded) quantum Fourier transform. Running our virtual quantum computer in mode B (full quantum implementation of ME and PF), we find that a large number of gates may be discarded in a scalable way in both the ME and PF parts of Shor's algorithm in exchange for only a small reduction in performance. We explicitly state the associated scaling laws. Implying significant savings in quantum gates, we suggest that these results are of importance for future experimental and technical large- $n$ implementations of quantum computers.We constructed a virtual quantum computer by running a complete, scaling, quantum-gate--by--quantum-gate implementation of Shor's algorithm on a 128-core classical cluster computer. In mode A [quantum period finding (PF) only, supplied with classical results for the modular exponentiation (ME) part of Shor's algorithm], factoring semiprimes up to $N=557\phantom{\rule{0.16em}{0ex}}993$ with up to $n=39$ qubits, we confirm earlier, smaller-$n$ results concerning the performance scaling of Shor's algorithm equipped with a truncated (banded) quantum Fourier transform. Running our virtual quantum computer in mode B (full quantum implementation of ME and PF), we find that a large number of gates may be discarded in a scalable way in both the ME and PF parts of Shor's algorithm in exchange for only a small reduction in performance. We explicitly state the associated scaling laws. Implying significant savings in quantum gates, we suggest that these results are of importance for future experimental and technical large-$n$ implementations of quantum computers.

Physical Review AJun 26, 20136 citations

We investigate the performance of a streamlined version of Shor's algorithm in which the quantum Fourier transform is replaced by a banded version that, for each qubit, retains only coupling to its

b

nearest neighbors. Defining the performance

P(n,b)

of the

n

-qubit algorithm for bandwidth

b

as the ratio of the success rates of Shor's algorithm equipped with the banded and the full-bandwidth ($b=n\ensuremath{-}1$) versions of the quantum Fourier transform, our numerical simulations show that $P(n,b)\ensuremath{\approx}\mathrm{exp}[\ensuremath{-}{\ensuremath{\varphi}}_{\mathrm{max}}^{2}(n,b)/100]$ for

n<{n}_{t}(b)

(nonexponential regime) and $P(n,b)\ensuremath{\approx}{2}^{\ensuremath{-}{\ensuremath{\xi}}_{b}(n\ensuremath{-}8)}$ for

n>{n}_{t}(b)

(exponential regime), where

{n}_{t}(b)

, the location of the transition, is approximately given by ${n}_{t}(b)\ensuremath{\approx}b+5.9+\sqrt{7.7(b+2)\ensuremath{-}47}$ for $b\ensuremath{\gtrsim}8$, ${\ensuremath{\varphi}}_{\mathrm{max}}(n,b)=2\ensuremath{\pi}[{2}^{\ensuremath{-}b\ensuremath{-}1}(n\ensuremath{-}b\ensuremath{-}2)+{2}^{\ensuremath{-}n}]$, and ${\ensuremath{\xi}}_{b}\ensuremath{\approx}1.1\ifmmode\times\else\texttimes\fi{}{2}^{\ensuremath{-}2b}$. Analytically we obtain $P(n,b)\ensuremath{\approx}\mathrm{exp}[\ensuremath{-}{\ensuremath{\varphi}}_{\mathrm{max}}^{2}(n,b)/64]$ for

n<{n}_{t}(b)

and $P(n,b)\ensuremath{\approx}{2}^{\ensuremath{-}{\ensuremath{\xi}}_{b}^{(a)}n}$ for

n>{n}_{t}(b)

, where ${\ensuremath{\xi}}_{b}^{(a)}\ensuremath{\approx}\frac{{\ensuremath{\pi}}^{2}}{12\mathrm{ln}(2)}\ifmmode\times\else\texttimes\fi{}{2}^{\ensuremath{-}2b}\ensuremath{\approx}1.19\ifmmode\times\else\texttimes\fi{}{2}^{\ensuremath{-}2b}$. Thus, our analytical results predict the ${\ensuremath{\varphi}}_{\mathrm{max}}^{2}$ scaling (

n<{n}_{t}

) and the ${2}^{\ensuremath{-}2b}$ scaling (

n>{n}_{t}

) of the data perfectly. In addition, in the large-

n

regime, the prefactor in ${\ensuremath{\xi}}_{b}^{(a)}$ is close to the results of our numerical simulations, and in the low-

n

regime, the numerical scaling factor in our analytical result is within a factor 2 of its numerical value. As an example we show that

b=8

is sufficient for factoring RSA-2048 with a 95

%

success rate.

N=557\phantom{\rule{0.16em}{0ex}}993

with up to

n=39

qubits, we confirm earlier, smaller-

n

results concerning the performance scaling of Shor's algorithm equipped with a truncated (banded) quantum Fourier transform. Running our virtual quantum computer in mode B (full quantum implementation of ME and PF), we find that a large number of gates may be discarded in a scalable way in both the ME and PF parts of Shor's algorithm in exchange for only a small reduction in performance. We explicitly state the associated scaling laws. Implying significant savings in quantum gates, we suggest that these results are of importance for future experimental and technical large-

n

implementations of quantum computers.