9 Evaluate performance of quantum algorithms

This chapter explains how to evaluate the performance of quantum algorithms rigorously and fairly, with the goal of identifying where practical quantum advantage might exist. It frames “quality” as a balance of accuracy, time to solution, and monetary cost, and stresses that comparisons must be made against the best available classical baselines that exploit problem structure. Using the N queens puzzle as the running example, it shows why asymptotic complexity alone is insufficient: practical performance depends on constants, crossover points, and implementation details such as oracle construction and encoding choices.

The text cautions against using simulator runtimes as a proxy for hardware performance, since simulators differ and are themselves classical programs. It instead grounds estimation in the assumptions of future fault-tolerant machines, outlining key architectural factors that shape runtime and qubit needs: slower physical operations than classical logic, noise necessitating error correction, limited connectivity that introduces routing overhead and auxiliary qubits, restricted native gate sets requiring decompositions, and costly magic state distillation for non-native gates. These realities create significant overheads and reveal meaningful trade-offs between runtime and the number of physical qubits.

To quantify these effects, the chapter introduces the Azure Quantum Resource Estimator, which takes a program, an error budget, and a hardware model to produce logical and physical resource counts, runtime estimates, and space-time trade-offs. Applying it to Grover-based N queens solvers (N=10, about 109 iterations), the encoding that maps each queen to a column index outperforms the per-cell bit encoding, with indicative estimates around 3 minutes using roughly 340k physical qubits versus about 37 minutes and 670k qubits. Despite this, classical approaches still dominate: even a simple brute-force Python solution finds all 10-queen placements in under 0.1 second, more advanced local search scales to enormous N rapidly, and constructive methods can generate solutions immediately. The chapter concludes that credible quantum performance evaluation demands careful baselines, realistic hardware assumptions, and full accounting of implementation overheads—especially for search problems where Grover-style speedups often fail to translate into practical advantage.

The key metrics that describe the quality of a problem solution are the accuracy of the result and the time and cost required to get it. We can often trade off these metrics by using different algorithms or implementations.

To understand performance of a quantum algorithm, you need to take into account not only its asymptotic complexity, but its practical behavior. The performance estimates are affected by the overheads introduced by the algorithm implementation and then by its execution on a fault-tolerant quantum computer. You also need to choose the best known classical algorithm as the baseline for comparison.

The classical solutions to the N queens puzzle range from brute-force solutions similar to those we considered as the equivalent to Grover’s search, to methods that exploit all the available information about the problem to construct the solution mathematically.

When comparing the performance of algorithms, it’s important to consider not only their asymptotic behavior but also the details. Algorithms can have the same asymptotic behavior but vastly different growth rates once you take into account all the factors. The solution with worse asymptotic behavior can be better in practice if the problem sizes are smaller than the crossover point — the problem size for which two algorithms have similar performance.

Physical qubits are noisy, they support a limited set of gates, and these gates are slow. We have to use error correction to enable reliable computation on noisy qubits. We also have to use a special process to implement arbitrary logical gates on logical qubits. These factors affect both the runtime of algorithms on the quantum computers and the numbers of qubits required to run them.

An example of resource estimates produced by Azure Quantum Resource Estimator.

The high-level inputs and processing logic of Azure Quantum Resource Estimator. The first step reduces the quantum program to a set of logical resource estimates. Then, AQRE looks for the parameters of the different architectural components of the quantum computer that allow to execute the program within the given error budget.

• The quality of a problem solution is a combination of the accuracy of the answer it gives and the time and the expense needed to produce that answer. When comparing quantum and classical solutions, it is important to use these practical metrics rather than more abstract properties such as the asymptotic behavior of the algorithms.
• When we look for practical quantum advantage for a classical problem, we have to compare the quantum solution with the best known classical solution of all. Such a solution will typically be designed specifically for this problem and take advantage of all information about the problem structure.
• If a problem has an efficient classical solution, quantum computing is unlikely to offer an improvement over it. The search for practical quantum advantage focuses on problems that don’t have a known efficient classical solution.
• Quantum algorithms aim to run on future fault-tolerant quantum computers, so any estimates of the algorithms’ performance have to take into account the overhead introduced by the architecture of these computers.
• Error correction is a technique that enables reliable computation using noisy qubits. It encodes logical qubits and gates — the ones used in quantum programs — as multiple physical qubits and gates on an actual quantum device.
• Magic gates are gates that are not supported by the quantum computer directly but have to be generated using a separate process. These gates allow us to approximate any gate the program needs with required accuracy.
• Error correction and magic state distillation are several of the key factors that impact the resource requirements of quantum algorithms. The other factors include execution time of quantum gates and measurements and the limitations on the qubit connectivity.
• You have to take into account a lot of information about the logical architecture of quantum computers to make realistic estimates of your algorithm’s performance. Specialized software tools such as Azure Quantum Resource Estimator allow you to make these estimates automatically based on your quantum program.

FAQ