Time-optimal implementations of quantum algorithms

In this paper, we present the general methodologies and framework to evaluate the time efficiency of an experimental realization of quantum algorithms. We do so by describing the factorization of $N=15$ in an NMR quantum computer (using Shor's algorithm) as an example. We began by simulating a quantum computer which performs the algorithm. Using this simulation, we devised a Monte Carlo algorithm to calculate the expected time in which a theoretical quantum computer could perform this calculation under the same energy conditions as current working quantum computers. We found that experimentally, a nuclear magnetic resonance quantum computer would take $1.59\pm 0.04\text{s}$ to perform our simulated computation, whereas the expected optimal time under the same energy conditions is $0.955\pm 0.004\mathrm{ms}$. Moreover, we found that the expected time is inversely proportional to the energy variance of our qubit states (as expected). Finally, we propose this theoretical method for analyzing the time efficiency of future quantum computing experiments.

Figure 1

A gate-by-gate breakdown of the 7-qubit Shor's algorithm circuit used for factorizing 15. All the symbols used in the diagram are presented in detail in Ref. [6]. The system was initialized to the state $|0000001\rangle$ as described in [8]. The first 3 qubits from the top comprise the $x$ register and the next 4 qubits are the $f$ register. Part (1) corresponds to putting the $x$ register in a superposition of all possible values of $x$ from 0 to $2^3-1$. Part (2) corresponds to the gate-by-gate breakdown of the 3 function gates described in Ref. [8]. These function gates control-multiply the $f$ register by $a^x$ mod 15. The resulting value of the $f$ register will be periodic. Part (3) represents the inverse Fourier transform which brings out the period of the function and we then read this out using the measurements on the far right of the diagram. The complete description of the process is available in Ref. [8].

Figure 2

Plot comparing the duration of Shor's algorithm for factorizing 15 using NMR techniques and time-optimal translations. The scale is logarithmic such that both data sets appear clearly on the plot. The $x$ axis represents each of the 25 steps of the quantum computation given in Fig. 1. The $y$ axis shows the cumulative time it takes to perform each step in our algorithm, calculated using the frequency values given by Vandersypen et al. [4]. Errors are not quoted but we assume the error is given by the precision of the values provided, although they are not clearly visible on the logarithmic scale. The 0 point on the $x$ axis is omitted as it corresponds to $log\left(0\right)=-\infty$ on the logarithmic scale. This plot was made using Python.