Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1809.09535 · Physical Review A

Time-optimal implementations of quantum algorithms

Alejandro Cros Carrillo de Albornoz, John R. Taylor, Vlad Cărare

Published Sep 20, 2019• 5 citations
arXivHTMLPDF

Abstract

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\ifmmode\pm\else\textpm\fi{}0.04\phantom{\rule{4.pt}{0ex}}\text{s}$ to perform our simulated computation, whereas the expected optimal time under the same energy conditions is $0.955\ifmmode\pm\else\textpm\fi{}0.004\phantom{\rule{0.28em}{0ex}}\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.

DOI
10.1103/physreva.100.032329

Related papers

Experimental Quantum Computation with Nuclear Spins in Liquid Solution

Lieven M. K. Vandersypen

We have taken significant steps towards the realization of a practical quantum computer: using nuclear spins and magnetic resonance techniques at room temperature, we provided proof of principle of quantum computing in a series of experiments which culminated in the implementation of the simplest instance of Shor's quantum algorithm for prime factorization (15=3x5), using a seven-spin molecule. This algorithm achieves an exponential advantage over the best known classical factoring algorithms and its implementation represents a milestone in the experimental exploration of quantum computation. These remarkable successes have been made possible by the synthesis of suitable molecules and the development of many novel techniques for initialization, coherent control and readout of the state of multiple coupled nuclear spins. Furthermore, we devised and implemented a model to simulate both unitary and decoherence processes in these systems, in order to study and quantify the impact of various technological as well as fundamental sources of errors. In summary, this work has given us a much needed practical appreciation of what it takes to build a quantum computer. While liquid NMR quantum computing has well-understood scaling limitations, many of the techniques that originated from this research may find use in other, perhaps more scalable quantum computer implementations.

arXiv:quant-ph/0205193•May 31, 2002•13 citations

Implementation of Shor’s Quantum Factoring Algorithm Using ProjectQ Framework

Adjie Wahyu Wicaksono, Arya Wicaksana

Prime number factorization is a problem in computer science where the solution to that problem takes super-polynomial time classically. Shor’s quantum factoring algorithm is able to solve the problem in polynomial time by harnessing the power of quantum computing. The implementation of the quantum algorithm itself is not detailed by Shor in his paper. In this paper, an approach and experiment to implement Shor’s quantum factoring algorithm are proposed. The implementation is done using Python and a quantum computer simulator from ProjectQ. The testing and evaluation are completed in two computers with different hardware specifications. User time of the implementation is measured in comparison with other quantum computer simulators: ProjectQ and Quantum Computing Playground. This comparison was done to show the performance of Shor’s algorithm when simulated using different hardware. There is a 33% improvement in the execution time (user time) between the two computers with the accuracy of prime factorization in this implementation is inversely proportional to the number of qubits used. Further improvements upon the program that has been developed for this paper is its accuracy in terms of finding the factors of a number and the number of qubits used, as previously mentioned.

International Journal of Engineering and Advanced Technology•Nov 22, 2019•5 citations

Experimental realization of a Shor-type quantum algorithm

Isaac L. Chuang

I will describe our recent implementation of a five-qubit NMR quantum computer capable of executing a quantum algorithm for order-finding. This is the first demonstration of a quantum algorithm with the structure of Shor's algorithm for efficient prime factorization, a key step in the experimental realization of quantum computers because its structure appears to be common to all quantum algorithms that achieve an exponential speed-up over their classical counterparts. The experiment was made possible by the synthesis of a 5-spin molecule with remarkable NMR properties, and by the introduction of new techniques for state initialization and quantum control.

Optical Fiber Communication Conference•Jan 1, 2001•1 citation

Quantum Computing Implemented via Optimal Control: Application to Spin and Pseudospin Systems

Thomas Schulte‐Herbrüggen, Andreas K. Spörl, Raimund Marx +6 more

This chapter discusses algorithmic and experimental aspects of quantum control of spin and pseudospin systems in view of realizing quantum algorithms or quantum simulations at minimal cost, in particular in a minimum amount of time. Geometric and optimal quantum control are most powerful tools for optimizing experimental implementations of quantum computing, whenever the quantum degrees of freedom can be described in closed Lie-algebraic form. It is highly desirable to strive for time-optimal implementations of quantum algorithms or their modules in order to avoid unnecessary decoherence. Apart from low temperatures, hyperpolarization techniques, or in situ reactions with para-hydrogen, even thermal ensemble states may be used for nuclear magnetic resonance (NMR) implementations of quantum algorithms, which are in principle scalable. NMR quantum processors are examples of expectation-value quantum computers (EVQC), where the outcome of a given quantum algorithm can be extracted from the resulting NMR spectra.

Wiley eBooks•Apr 18, 2016•1 citation

Quantum Computations: Fundamentals And Algorithms

Steven Anatolievich Duplij, И.И. Шаповал

Basic concepts of quantum theory of information, principles of quantum calculations and the possibility of creation on this basis unique on calculation power and functioning principle device, named quantum computer, are briefly reviewed. The main blocks of quantum logic, schemes of implementation of quantum calculations, as well as some known today effective quantum algorithms, called to realize advantages of quantum calculations upon classical, are concerned. Among them special place is taken by Shor's algorithm of number factorization, Grover's algorithm of unsorted database search and, finally, the most promising in application methods of quantum phenomena simulation, particularly quantum chaos. The most perspective methods of experimental realization of quantum computer, namely nuclear-magnetic resonance and trapped ions realizations, are discussed. Phenomena of decoherence, its influence on quantum computer stability and methods of quantum error correction are described.

arXiv:0712.1098•Dec 7, 2007•3 citations

Energy efficiency of quantum computers

Miquel Carrasco-Codina, Pau Escofet, Paul Hilaire +13 more

How much energy does a quantum computer consume? Are they more efficient than their classical counterparts? In this work, we make a step towards answering these questions. We define the energy efficiency of a quantum computer as the ratio of the number of algorithms it can perform during a given time over the energy consumed by the hardware during this time. We analyze the most representative physical platforms currently envisioned to be used as building blocks of quantum computers: superconducting qubits, silicon spin qubits, trapped ions, neutral atoms and photonic qubits. Including insights from experts in all these technologies and taking into account algorithm compilation constraints, we discuss the advantages and inconveniences of each platform from an energy standpoint. Beyond providing concrete values of the energy consumption of current quantum computers, we lay the foundation of a framework to benchmark the energy efficiency of any future quantum computing architecture.

quant-pharXiv:2605.15090•May 15, 2026•5 citations
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=15N=15N=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\ifmmode±\else\textpm\fi0.04s1.59\ifmmode\pm\else\textpm\fi{}0.04\phantom{\rule{4.pt}{0ex}}\text{s}1.59\ifmmode±\else\textpm\fi0.04s to perform our simulated computation, whereas the expected optimal time under the same energy conditions is 0.955\ifmmode±\else\textpm\fi0.004ms0.955\ifmmode\pm\else\textpm\fi{}0.004\phantom{\rule{0.28em}{0ex}}\mathrm{ms}0.955\ifmmode±\else\textpm\fi0.004ms. 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.
We have taken significant steps towards the realization of a practical quantum computer: using nuclear spins and magnetic resonance techniques at room temperature, we provided proof of principle of quantum computing in a series of experiments which culminated in the implementation of the simplest instance of Shor's quantum algorithm for prime factorization (15=3x5), using a seven-spin molecule. This algorithm achieves an exponential advantage over the best known classical factoring algorithms and its implementation represents a milestone in the experimental exploration of quantum computation. These remarkable successes have been made possible by the synthesis of suitable molecules and the development of many novel techniques for initialization, coherent control and readout of the state of multiple coupled nuclear spins. Furthermore, we devised and implemented a model to simulate both unitary and decoherence processes in these systems, in order to study and quantify the impact of various technological as well as fundamental sources of errors. In summary, this work has given us a much needed practical appreciation of what it takes to build a quantum computer. While liquid NMR quantum computing has well-understood scaling limitations, many of the techniques that originated from this research may find use in other, perhaps more scalable quantum computer implementations.
Prime number factorization is a problem in computer science where the solution to that problem takes super-polynomial time classically. Shor’s quantum factoring algorithm is able to solve the problem in polynomial time by harnessing the power of quantum computing. The implementation of the quantum algorithm itself is not detailed by Shor in his paper. In this paper, an approach and experiment to implement Shor’s quantum factoring algorithm are proposed. The implementation is done using Python and a quantum computer simulator from ProjectQ. The testing and evaluation are completed in two computers with different hardware specifications. User time of the implementation is measured in comparison with other quantum computer simulators: ProjectQ and Quantum Computing Playground. This comparison was done to show the performance of Shor’s algorithm when simulated using different hardware. There is a 33% improvement in the execution time (user time) between the two computers with the accuracy of prime factorization in this implementation is inversely proportional to the number of qubits used. Further improvements upon the program that has been developed for this paper is its accuracy in terms of finding the factors of a number and the number of qubits used, as previously mentioned.
I will describe our recent implementation of a five-qubit NMR quantum computer capable of executing a quantum algorithm for order-finding. This is the first demonstration of a quantum algorithm with the structure of Shor's algorithm for efficient prime factorization, a key step in the experimental realization of quantum computers because its structure appears to be common to all quantum algorithms that achieve an exponential speed-up over their classical counterparts. The experiment was made possible by the synthesis of a 5-spin molecule with remarkable NMR properties, and by the introduction of new techniques for state initialization and quantum control.
This chapter discusses algorithmic and experimental aspects of quantum control of spin and pseudospin systems in view of realizing quantum algorithms or quantum simulations at minimal cost, in particular in a minimum amount of time. Geometric and optimal quantum control are most powerful tools for optimizing experimental implementations of quantum computing, whenever the quantum degrees of freedom can be described in closed Lie-algebraic form. It is highly desirable to strive for time-optimal implementations of quantum algorithms or their modules in order to avoid unnecessary decoherence. Apart from low temperatures, hyperpolarization techniques, or in situ reactions with para-hydrogen, even thermal ensemble states may be used for nuclear magnetic resonance (NMR) implementations of quantum algorithms, which are in principle scalable. NMR quantum processors are examples of expectation-value quantum computers (EVQC), where the outcome of a given quantum algorithm can be extracted from the resulting NMR spectra.
Basic concepts of quantum theory of information, principles of quantum calculations and the possibility of creation on this basis unique on calculation power and functioning principle device, named quantum computer, are briefly reviewed. The main blocks of quantum logic, schemes of implementation of quantum calculations, as well as some known today effective quantum algorithms, called to realize advantages of quantum calculations upon classical, are concerned. Among them special place is taken by Shor's algorithm of number factorization, Grover's algorithm of unsorted database search and, finally, the most promising in application methods of quantum phenomena simulation, particularly quantum chaos. The most perspective methods of experimental realization of quantum computer, namely nuclear-magnetic resonance and trapped ions realizations, are discussed. Phenomena of decoherence, its influence on quantum computer stability and methods of quantum error correction are described.
How much energy does a quantum computer consume? Are they more efficient than their classical counterparts? In this work, we make a step towards answering these questions. We define the energy efficiency of a quantum computer as the ratio of the number of algorithms it can perform during a given time over the energy consumed by the hardware during this time. We analyze the most representative physical platforms currently envisioned to be used as building blocks of quantum computers: superconducting qubits, silicon spin qubits, trapped ions, neutral atoms and photonic qubits. Including insights from experts in all these technologies and taking into account algorithm compilation constraints, we discuss the advantages and inconveniences of each platform from an energy standpoint. Beyond providing concrete values of the energy consumption of current quantum computers, we lay the foundation of a framework to benchmark the energy efficiency of any future quantum computing architecture.