Robustness of Quantum Algorithms
Abstract
The goal of this project is to test the robustness of quantum algorithms under various types of perturbations. There are two benefits to this line of investigation. The first is that it provides a tool for probing the boundary between success and failure in quantum algorithms. Quantum speed-ups seem fragile; many quantum algorithms need carefully crafted promises and extraordinarily low error rates to guarantee success. To test this fragility, and to figure out at what point quantum algorithms truly break down, we propose to examine the behavior of quantum algorithms as we loosen the restrictions on promises and introduce errors. This research will address questions like: as promises are relaxed, will there be a slow degradation of the performance, or will there be sharp cliff, where the algorithm works as usual and then fails dramatically? Will new techniques increase the robustness of the algorithm, so that a similar performance can be achieved even in the presence of weakened promises or increased errors? The answers might differ depending on the type of perturbation, and this in turn will provide insight into when quantum algorithms should succeed, and when they will likely fail or provide a more limited advantage. Ultimately, the answers to these questions will help us to better understand the structure and nature of quantum computing and quantum speed-ups. The second motivation for this line of inquiry is more practical. In the NISQ (Noisy Intermediate-Scale Quantum) era, quantum devices will not be able to execute perfect gates, and the problems they attempt to solve will likely be real-world problems that do not perfectly fit the promises and assumptions of theoretical results. By showing that quantum speed-ups are robust to perturbations, it will increase confidence that NISQ devices can succeed despite these challenges. On the other hand, if quantum speed-ups appear to be sensitive to the perturbations and relaxations in this proposal, it might signal that caution is needed regarding the potential of such NISQ devices. This research will analyze the robustness of three algorithms. In two cases, the promise on the underlying problem is perturbed or altered. For the third case, the underlying problem is unchanged, but tunable errors are introduced. In each case, the goal will be to examine to what extent the algorithm is still successful under the perturbation, in what ways the algorithm can be adjusted to better cope with the perturbation, or whether the perturbation affects a fundamental property of the quantum speed-up, resulting in a failure of the algorithm.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Aug 31, 2020
- Source ID
- W911NF2010327
Entities
People
- Shelby Kimmel
Organizations
- Army Contracting Command
- Middlebury College
- United States Army