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:1505.06552 · Quantum Information Processing

Concrete resource analysis of the quantum linear-system algorithm used to compute the electromagnetic scattering cross section of a 2D target

Artur Scherer, Benoît Valiron, Siun-Chuon Mau, D. Scott Alexander, Eric van den Berg, Thomas E. Chapuran

Published Jan 25, 2017• 72 citations
arXivHTMLPDF

Abstract

We provide a detailed estimate for the logical resource requirements of the quantum linear-system algorithm (Harrow et al. in Phys Rev Lett 103:150502, 2009) including the recently described elaborations and application to computing the electromagnetic scattering cross section of a metallic target (Clader et al. in Phys Rev Lett 110:250504, 2013). Our resource estimates are based on the standard quantum-circuit model of quantum computation; they comprise circuit width (related to parallelism), circuit depth (total number of steps), the number of qubits and ancilla qubits employed, and the overall number of elementary quantum gate operations as well as more specific gate counts for each elementary fault-tolerant gate from the standard set $$\{ X, Y, Z, H, S, T, \text{ CNOT } \}$$ . In order to perform these estimates, we used an approach that combines manual analysis with automated estimates generated via the Quipper quantum programming language and compiler. Our estimates pertain to the explicit example problem size $$N=332{,}020{,}680$$ beyond which, according to a crude big-O complexity comparison, the quantum linear-system algorithm is expected to run faster than the best known classical linear-system solving algorithm. For this problem size, a desired calculation accuracy $$\varepsilon =0.01$$ requires an approximate circuit width 340 and circuit depth of order $$10^{25}$$ if oracle costs are excluded, and a circuit width and circuit depth of order $$10^8$$ and $$10^{29}$$ , respectively, if the resource requirements of oracles are included, indicating that the commonly ignored oracle resources are considerable. In addition to providing detailed logical resource estimates, it is also the purpose of this paper to demonstrate explicitly (using a fine-grained approach rather than relying on coarse big-O asymptotic approximations) how these impressively large numbers arise with an actual circuit implementation of a quantum algorithm. While our estimates may prove to be conservative as more efficient advanced quantum-computation techniques are developed, they nevertheless provide a valid baseline for research targeting a reduction of the algorithmic-level resource requirements, implying that a reduction by many orders of magnitude is necessary for the algorithm to become practical.

DOI
10.1007/s11128-016-1495-5

Related papers

Applying Grover's algorithm to AES: quantum resource estimates

Markus Grassl, Brandon Langenberg, Martin Roetteler +1 more

We present quantum circuits to implement an exhaustive key search for the Advanced Encryption Standard (AES) and analyze the quantum resources required to carry out such an attack. We consider the overall circuit size, the number of qubits, and the circuit depth as measures for the cost of the presented quantum algorithms. Throughout, we focus on Clifford$+T$ gates as the underlying fault-tolerant logical quantum gate set. In particular, for all three variants of AES (key size 128, 192, and 256 bit) that are standardized in FIPS-PUB 197, we establish precise bounds for the number of qubits and the number of elementary logical quantum gates that are needed to implement Grover's quantum algorithm to extract the key from a small number of AES plaintext-ciphertext pairs.

arXiv:1512.04965•Dec 15, 2015•12 citations

Preconditioned Quantum Linear System Algorithm

B. D. Clader, B. C. Jacobs, C. Sprouse

We describe a quantum algorithm that generalizes the quantum linear system algorithm [Harrow et al., Phys. Rev. Lett. 103, 150502 (2009)] to arbitrary problem specifications. We develop a state preparation routine that can initialize generic states, show how simple ancilla measurements can be used to calculate many quantities of interest, and integrate a quantum-compatible preconditioner that greatly expands the number of problems that can achieve exponential speedup over classical linear systems solvers. To demonstrate the algorithm's applicability, we show how it can be used to compute the electromagnetic scattering cross section of an arbitrary target exponentially faster than the best classical algorithm.

arXiv:1301.2340•Physical Review Letters•Jun 18, 2013•288 citations

Quantum Resource Estimation for Quantum Chemistry Algorithms

Dmitry A. Fedorov, Matthew Otten, Byeol Kang +4 more

Predicting the quantum resources for potential applications such as quantum chemistry plays a key role in the future development of quantum computers, and a systematic approach based on a reliable metric is needed for efficient resource estimation. In this work, we developed a Python software package QRE (Quantum Resource Estimator) for estimating quantum resources required to compute the properties of molecules. We define the key requirements for the quantum phase estimation (QPE) algorithm for molecules with different basis sets. We estimated the number of ancilla qubits, circuit depth, and time to solution. The input for QRE is the information about a molecule such as atom types, molecular geometries, charges, basis set, and level of theory. Also, we consider an error analysis scheme for QPE algorithm to calculate the number of ancilla qubits. As a part of the estimation, we calculate the number of rotation and CNOT gates for one Trotter step. Based on these results, the QRE program calculates costs for full QPE algorithms for the given gate time, fidelities of CNOT gates, and target success probability. It is expected that our work will contribute to a better understanding of the limitations of current and future quantum computers for quantum chemistry applications.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 1, 2022•2 citations

Quipper: Concrete Resource Estimation in Quantum Algorithms

Jonathan M. Smith, Neil J. Ross, Peter Selinger +1 more

Despite the rich literature on quantum algorithms, there is a surprisingly small amount of coverage of their concrete logical design and implementation. Most resource estimation is done at the level of complexity analysis, but actual concrete numbers (of quantum gates, qubits, etc.) can differ by orders of magnitude. The line of work we present here is a formal framework to write, and reason about, quantum algorithms. Specifically, we designed a language, Quipper, with scalability in mind, and we are able to report actual resource counts for seven non-trivial algorithms found in the quantum computer science literature.

arXiv:1412.0625•Dec 1, 2014•10 citations

Logical Resource Estimation for Quantum State Preparation with Compilation

Diyi Liu, Hanyu Wang, Shuchen Zhu +6 more

Quantum state preparation is a fundamental primitive in quantum algorithms for encoding classical data into quantum amplitudes. We compare the cost of preparing general $n$-qubit states with real amplitudes using two common paradigms: rotation-based methods, based on controlled rotations, and sampling-based methods, based on a structured representation of the target state. Although these approaches are often theoretically compared using CNOT count and $T$-count, their relative performance in total gate count remains less well understood practically. We compare representative rotation-based and sampling-based methods using $T$-count and total gate count, and analyze how compilation overhead affects their relative performance. We also develop a software package for compiling state preparation circuits, designed as a practical subroutine for more general quantum computations. Numerical experiments on resource states and quantum states related to quantum chemistry, condensed matter physics, and simulation via Magnus expansion over a range of target accuracies $ε$ support the analysis. Our results show that sampling-based methods achieve asymptotically lower $T$-count and retain an overall advantage after accounting for total gate count and compilation overhead.

quant-pharXiv:2605.18877•May 19, 2026•0 citations

Program compilation for large-scale quantum computers

Giulia Meuli

Practical realizations of quantum computers are poised to deliver outstanding computational capabilities far beyond the reach of any classical supercomputer. While classical systems are reliably implemented using CMOS technology, the fabrication of quantum hardware has not yet reached a commercially viable level of maturity. Nowadays, many different technologies are being developed as competing candidates to build the first error-corrected quantum computer. Among the software resources required to operate such a system, quantum compilers translate a high-level description of a quantum algorithm into low-level, technology-dependent quantum instructions. Many quantum algorithms, including Shor's and Grover's algorithms, require to compute some classical logic functions on the quantum computer. The first part of this thesis deals with the problem of compiling quantum circuits that perform such classical Boolean functions, called oracles, into a fault-tolerant set of instructions. Oracle circuits often demand many resources in terms of the number of qubits and gates. The focus is on compiling quantum circuits starting from multi-level logic networks representing large Boolean functions while minimizing the resource footprint of the obtained quantum circuits. At the same time, the trade-off between memory resources and the number of operations typical of such a compilation process is explored. As part of the effort in reducing the resources required to perform a given quantum program, I also present some quantum circuit optimization techniques. The researched algorithms leverage data structures and techniques borrowed and adapted from classical logic synthesis, e.g., SAT solvers, LUT mapping, and multi-level logic networks. I implemented all the compilation algorithms presented in this thesis as part of open-source projects. In particular, I develop and maintain caterpillar---a C++ header-only library dedicated to the quantum compilation of oracles and quantum memory management. The second part of this thesis describes how to equip quantum programming language compilers with automatic accuracy management. Despite the availability of many of such languages, resource estimation of quantum algorithms does not yet support taking approximation errors into account. This general methodology is applicable to any programming language and I demonstrate its integration into the Q# compiler. The technique consists of providing language support to ease the accuracy-aware programming task. The user can define accuracy parameters that will be automatically optimized according to a constraint and a cost function directly generated from the source code. In the presented practical evaluations, the constraint function is the overall allowed accuracy, while the cost function is application-dependent and related to the number of gates. During the optimization process, such functions are evaluated hundreds of times. For this reason, we extract them as (near-)symbolic expressions, whose evaluation time does not depend on the quantum algorithm size. The algorithms and the methodologies presented in this thesis are part of a widespread effort of the research community to build a complete and efficient software stack to program and control the first practical universal quantum computer.

•Jan 1, 2020•1 citation
We provide a detailed estimate for the logical resource requirements of the quantum linear-system algorithm (Harrow et al. in Phys Rev Lett 103:150502, 2009) including the recently described elaborations and application to computing the electromagnetic scattering cross section of a metallic target (Clader et al. in Phys Rev Lett 110:250504, 2013). Our resource estimates are based on the standard quantum-circuit model of quantum computation; they comprise circuit width (related to parallelism), circuit depth (total number of steps), the number of qubits and ancilla qubits employed, and the overall number of elementary quantum gate operations as well as more specific gate counts for each elementary fault-tolerant gate from the standard set {X,Y,Z,H,S,T, CNOT }\{ X, Y, Z, H, S, T, \text{ CNOT } \}{X,Y,Z,H,S,T, CNOT } . In order to perform these estimates, we used an approach that combines manual analysis with automated estimates generated via the Quipper quantum programming language and compiler. Our estimates pertain to the explicit example problem size N=332,020,680N=332{,}020{,}680N=332,020,680 beyond which, according to a crude big-O complexity comparison, the quantum linear-system algorithm is expected to run faster than the best known classical linear-system solving algorithm. For this problem size, a desired calculation accuracy ε=0.01\varepsilon =0.01ε=0.01 requires an approximate circuit width 340 and circuit depth of order 102510^{25}1025 if oracle costs are excluded, and a circuit width and circuit depth of order 10810^8108 and 102910^{29}1029 , respectively, if the resource requirements of oracles are included, indicating that the commonly ignored oracle resources are considerable. In addition to providing detailed logical resource estimates, it is also the purpose of this paper to demonstrate explicitly (using a fine-grained approach rather than relying on coarse big-O asymptotic approximations) how these impressively large numbers arise with an actual circuit implementation of a quantum algorithm. While our estimates may prove to be conservative as more efficient advanced quantum-computation techniques are developed, they nevertheless provide a valid baseline for research targeting a reduction of the algorithmic-level resource requirements, implying that a reduction by many orders of magnitude is necessary for the algorithm to become practical.
We present quantum circuits to implement an exhaustive key search for the Advanced Encryption Standard (AES) and analyze the quantum resources required to carry out such an attack. We consider the overall circuit size, the number of qubits, and the circuit depth as measures for the cost of the presented quantum algorithms. Throughout, we focus on Clifford+T+T+T gates as the underlying fault-tolerant logical quantum gate set. In particular, for all three variants of AES (key size 128, 192, and 256 bit) that are standardized in FIPS-PUB 197, we establish precise bounds for the number of qubits and the number of elementary logical quantum gates that are needed to implement Grover's quantum algorithm to extract the key from a small number of AES plaintext-ciphertext pairs.
We describe a quantum algorithm that generalizes the quantum linear system algorithm [Harrow et al., Phys. Rev. Lett. 103, 150502 (2009)] to arbitrary problem specifications. We develop a state preparation routine that can initialize generic states, show how simple ancilla measurements can be used to calculate many quantities of interest, and integrate a quantum-compatible preconditioner that greatly expands the number of problems that can achieve exponential speedup over classical linear systems solvers. To demonstrate the algorithm's applicability, we show how it can be used to compute the electromagnetic scattering cross section of an arbitrary target exponentially faster than the best classical algorithm.
Predicting the quantum resources for potential applications such as quantum chemistry plays a key role in the future development of quantum computers, and a systematic approach based on a reliable metric is needed for efficient resource estimation. In this work, we developed a Python software package QRE (Quantum Resource Estimator) for estimating quantum resources required to compute the properties of molecules. We define the key requirements for the quantum phase estimation (QPE) algorithm for molecules with different basis sets. We estimated the number of ancilla qubits, circuit depth, and time to solution. The input for QRE is the information about a molecule such as atom types, molecular geometries, charges, basis set, and level of theory. Also, we consider an error analysis scheme for QPE algorithm to calculate the number of ancilla qubits. As a part of the estimation, we calculate the number of rotation and CNOT gates for one Trotter step. Based on these results, the QRE program calculates costs for full QPE algorithms for the given gate time, fidelities of CNOT gates, and target success probability. It is expected that our work will contribute to a better understanding of the limitations of current and future quantum computers for quantum chemistry applications.
Despite the rich literature on quantum algorithms, there is a surprisingly small amount of coverage of their concrete logical design and implementation. Most resource estimation is done at the level of complexity analysis, but actual concrete numbers (of quantum gates, qubits, etc.) can differ by orders of magnitude. The line of work we present here is a formal framework to write, and reason about, quantum algorithms. Specifically, we designed a language, Quipper, with scalability in mind, and we are able to report actual resource counts for seven non-trivial algorithms found in the quantum computer science literature.
Quantum state preparation is a fundamental primitive in quantum algorithms for encoding classical data into quantum amplitudes. We compare the cost of preparing general nnn-qubit states with real amplitudes using two common paradigms: rotation-based methods, based on controlled rotations, and sampling-based methods, based on a structured representation of the target state. Although these approaches are often theoretically compared using CNOT count and TTT-count, their relative performance in total gate count remains less well understood practically. We compare representative rotation-based and sampling-based methods using TTT-count and total gate count, and analyze how compilation overhead affects their relative performance. We also develop a software package for compiling state preparation circuits, designed as a practical subroutine for more general quantum computations. Numerical experiments on resource states and quantum states related to quantum chemistry, condensed matter physics, and simulation via Magnus expansion over a range of target accuracies εεε support the analysis. Our results show that sampling-based methods achieve asymptotically lower TTT-count and retain an overall advantage after accounting for total gate count and compilation overhead.
Practical realizations of quantum computers are poised to deliver outstanding computational capabilities far beyond the reach of any classical supercomputer. While classical systems are reliably implemented using CMOS technology, the fabrication of quantum hardware has not yet reached a commercially viable level of maturity. Nowadays, many different technologies are being developed as competing candidates to build the first error-corrected quantum computer. Among the software resources required to operate such a system, quantum compilers translate a high-level description of a quantum algorithm into low-level, technology-dependent quantum instructions. Many quantum algorithms, including Shor's and Grover's algorithms, require to compute some classical logic functions on the quantum computer. The first part of this thesis deals with the problem of compiling quantum circuits that perform such classical Boolean functions, called oracles, into a fault-tolerant set of instructions. Oracle circuits often demand many resources in terms of the number of qubits and gates. The focus is on compiling quantum circuits starting from multi-level logic networks representing large Boolean functions while minimizing the resource footprint of the obtained quantum circuits. At the same time, the trade-off between memory resources and the number of operations typical of such a compilation process is explored. As part of the effort in reducing the resources required to perform a given quantum program, I also present some quantum circuit optimization techniques. The researched algorithms leverage data structures and techniques borrowed and adapted from classical logic synthesis, e.g., SAT solvers, LUT mapping, and multi-level logic networks. I implemented all the compilation algorithms presented in this thesis as part of open-source projects. In particular, I develop and maintain caterpillar---a C++ header-only library dedicated to the quantum compilation of oracles and quantum memory management. The second part of this thesis describes how to equip quantum programming language compilers with automatic accuracy management. Despite the availability of many of such languages, resource estimation of quantum algorithms does not yet support taking approximation errors into account. This general methodology is applicable to any programming language and I demonstrate its integration into the Q# compiler. The technique consists of providing language support to ease the accuracy-aware programming task. The user can define accuracy parameters that will be automatically optimized according to a constraint and a cost function directly generated from the source code. In the presented practical evaluations, the constraint function is the overall allowed accuracy, while the cost function is application-dependent and related to the number of gates. During the optimization process, such functions are evaluated hundreds of times. For this reason, we extract them as (near-)symbolic expressions, whose evaluation time does not depend on the quantum algorithm size. The algorithms and the methodologies presented in this thesis are part of a widespread effort of the research community to build a complete and efficient software stack to program and control the first practical universal quantum computer.