9 Evaluate performance of quantum algorithms
This chapter covers
- Comparing quantum algorithms with classical algorithms for the same problem
- Factors that impact performance of quantum algorithms
- Using Azure Quantum Resource Estimator to estimate performance of quantum programs on future quantum computers
In chapter 8, we came up with two quantum algorithms for solving the N queens puzzle — variants of Grover’s search that relied on different problem encoding and oracle implementation. How can we compare these two algorithms to decide which of them is better? And how can we figure out whether either of these algorithms can beat the classical solution to the N queens puzzle for large boards?
These questions arise whenever somebody comes up with a quantum algorithm to solve a problem. Comparing quantum solutions with each other and with classical ones is a critical part of quantum algorithm development. After all, we’re building quantum computers to achieve practical quantum advantage — to solve useful problems that classical computers cannot handle. Understanding what kinds of problems these can be and what the quantum solutions to them look like gives us important information for making decisions about the architecture of the future quantum computers as we build them.