Stuart Hadfieldstuart-hadfield

Quantum optimization, both for classical and quantum functions, is one of the most well-studied applications of quantum computing, but recent trends have relied on hybrid methods that push much of the fine-tuning off onto costly classical algorithms. Feedback-based quantum algorithms, such as FALQON, avoid these fine-tuning problems but at the cost of additional circuit depth and a lack of convergence guarantees. In this work, we take the local greedy information collected by Lyapunov feedback control and develop an analytic framework to use it to perturbatively update previous control layers, similar to the global optimal control achievable using Pontryagin optimal control. This perturbative methodology, which we call Feedback Optimally Controlled Quantum States (FOCQS), can be used to improve the results of feedback-based algorithms, like FALQON. Furthermore, this perturbative method can be used to push smooth annealing-like control protocol closer to the control optimum, even providing and iterative approach, albeit with diminishing returns. In numerical testing, we show improvements in convergence and required depth due to these methods over existing quantum feedback control methods.

Quantum Fourier transformations are an essential component of many quantum algorithms, from prime factoring to quantum simulation. While the standard abelian QFT is well-studied, important variants corresponding to \emphnonabelian groups of interest have seen less development. In particular, fast nonabelian Fourier transformations are important components for both quantum simulations of field theories as well as approaches to the nonabelian hidden subgroup problem. In this work, we present fast quantum Fourier transformations for a number of nonabelian groups of interest for high energy physics, $\mathbb{BT}$, $\mathbb{BO}$, $\Delta(27)$, $\Delta(54)$, and $\Sigma(36\times3)$. For each group, we derive explicit quantum circuits and estimate resource scaling for fault-tolerant implementations. Our work shows that the development of a fast Fourier transformation can substantively reduce simulation costs by up to three orders of magnitude for the finite groups that we have investigated.

Quantum computing is one of the most enticing computational paradigms with the potential to revolutionize diverse areas of future-generation computational systems. While quantum computing hardware has advanced rapidly, from tiny laboratory experiments to quantum chips that can outperform even the largest supercomputers on specialized computational tasks, these noisy-intermediate scale quantum (NISQ) processors are still too small and non-robust to be directly useful for any real-world applications. In this paper, we describe NASA's work in assessing and advancing the potential of quantum computing. We discuss advances in algorithms, both near- and longer-term, and the results of our explorations on current hardware as well as with simulations, including illustrating the benefits of algorithm-hardware co-design in the NISQ era. This work also includes physics-inspired classical algorithms that can be used at application scale today. We discuss innovative tools supporting the assessment and advancement of quantum computing and describe improved methods for simulating quantum systems of various types on high-performance computing systems that incorporate realistic error models. We provide an overview of recent methods for benchmarking, evaluating, and characterizing quantum hardware for error mitigation, as well as insights into fundamental quantum physics that can be harnessed for computational purposes.

We present Noise-Directed Adaptive Remapping (NDAR), a heuristic algorithm for approximately solving binary optimization problems by leveraging certain types of noise. We consider access to a noisy quantum processor with dynamics that features a global attractor state. In a standard setting, such noise can be detrimental to the quantum optimization performance. Our algorithm bootstraps the noise attractor state by iteratively gauge-transforming the cost-function Hamiltonian in a way that transforms the noise attractor into higher-quality solutions. The transformation effectively changes the attractor into a higher-quality solution of the Hamiltonian based on the results of the previous step. The end result is that noise aids variational optimization, as opposed to hindering it. We present an improved Quantum Approximate Optimization Algorithm (QAOA) runs in experiments on Rigetti's quantum device. We report approximation ratios $0.9$-$0.96$ for random, fully connected graphs on $n=82$ qubits, using only depth $p=1$ QAOA with NDAR. This compares to $0.34$-$0.51$ for standard $p=1$ QAOA with the same number of function calls.

Parameterized quantum circuits are attractive candidates for potential quantum advantage in the near term and beyond. At the same time, as quantum computing hardware not only continues to improve but also begins to incorporate new features such as mid-circuit measurement and adaptive control, opportunities arise for innovative algorithmic paradigms. In this work we focus on measurement-based quantum computing protocols for approximate optimization, in particular related to quantum alternating operator ansätze (QAOA), a popular quantum circuit model approach to combinatorial optimization. For the construction and analysis of our measurement-based protocols we demonstrate that diagrammatic approaches, specifically ZX-calculus and its extensions, are effective for adapting such algorithms to the measurement-based setting. In particular we derive measurement patterns for applying QAOA to the broad and important class of QUBO problems. We further outline how for constrained optimization, hard problem constraints may be directly incorporated into our protocol to guarantee the feasibility of the solution found and avoid the need for dealing with penalties. Finally we discuss the resource requirements and tradeoffs of our approach to that of more traditional quantum circuits.

Recent advances in quantum computers are demonstrating the ability to solve problems at a scale beyond brute force classical simulation. As such, a widespread interest in quantum algorithms has developed in many areas, with optimization being one of the most pronounced domains. Across computer science and physics, there are a number of different approaches for major classes of optimization problems, such as combinatorial optimization, convex optimization, non-convex optimization, and stochastic extensions. This work draws on multiple approaches to study quantum optimization. Provably exact versus heuristic settings are first explained using computational complexity theory - highlighting where quantum advantage is possible in each context. Then, the core building blocks for quantum optimization algorithms are outlined to subsequently define prominent problem classes and identify key open questions that, if answered, will advance the field. The effects of scaling relevant problems on noisy quantum devices are also outlined in detail, alongside meaningful benchmarking problems. We underscore the importance of benchmarking by proposing clear metrics to conduct appropriate comparisons with classical optimization techniques. Lastly, we highlight two domains - finance and sustainability - as rich sources of optimization problems that could be used to benchmark, and eventually validate, the potential real-world impact of quantum optimization.