Characterizing Quantum Advantage through Quantum Fourier Analysis

Quantum computers promise to solve a range of problems faster than classical computers, with potential applications in areas such as communication, materials science, optimization, and the simulation of physical systems. A central scientific challenge, however, is to understand where this quantum advantage comes from and how it can be rigorously identified, quantified, and harnessed. To address this challenge, the project will develop a mathematical approach to study the structural boundary that separates quantum processes that can be efficiently simulated by classical computers from those that genuinely produce quantum computational power. By clarifying this boundary, the project seeks to deepen a fundamental understanding of quantum computing and will support the development of reliable methods for evaluating and certifying emerging quantum technologies. The work will serve the national interest by strengthening United States leadership in quantum information science, a field of strategic importance for scientific discovery and economic competitiveness. The project will also support the training of graduate students and early-career researchers at the interface of mathematics, computer science, and physics, contributing to the scientific workforce needed for the future of quantum technologies. The technical goal of the project is to build a mathematical framework based on Fourier analysis for studying the quantum advantage in computation and information processing. A central aim will be to design clear tests and mathematical results that distinguish quantum operations that classical computers can reproduce from those that cannot, providing a principled way to describe the resources behind quantum speedups. The project will also study how quantum systems can transmit information more efficiently and more securely than classical systems, as well as identify the quantum features responsible for these improvements. Expected contributions will include new ways to describe and measure the quantum advantage, new procedures for testing quantum operations, and new connections between mathematics, physics, and quantum information. Together, these results aim to strengthen the mathematical foundations of quantum computing and quantum information that will help guide the design, verification, and testing of future quantum devices. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria. NSF Award ID: 2606749 | Program: 01002627DB NSF RESEARCH & RELATED ACTIVIT | Principal Investigator: Kaifeng Bu | Institution: OHIO STATE UNIVERSITY, THE, COLUMBUS, OH | Award Amount: $232,033 View on NSF Award Search: https://www.nsf.gov/awardsearch/show-award/?AWD_ID=2606749 View on Research.gov: https://www.research.gov/awardapi-service/v1/awards/2606749.html