9 Evaluate performance of quantum algorithms
This chapter covers
- Comparing quantum algorithms with classical ones
- 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 rely on different problem encoding and oracle implementation. How can we compare the performance of 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. Being able to compare 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 help us solve 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.