Quantum computing offers a new path towards solving problems well beyond the scope of the most powerful classical computers. This is popularly referred to as "quantum advantage" or "quantum supremacy". We characterize conditions under which such advantages can be realized. In this talk we present a framework for obtaining quantum advantage in a systematic manner. Our first candidate problem to demonstrate our framework is search. By generalizing Grover’s well-known algorithm, we show that our algorithm searches a list of elements, composed of k "structured" segments, in 0(sqrt(k). logN) steps, compared to Grover's algorithm which takes 0(sqrt(N)) steps. The notion of focusing the scarce computational resources or Qubits on parts of the application where they add most value is the key idea. This notion is formalized by using the well-understood concept of spectral concentration from classical computing. A practical consequence of this analysis is that 'with error correction', a quantum volume of 220 is possible to achieve in 2023. Equivalently, the quantum volume that can potentially be reached in 2025 can now be reached two years earlier, in 2023. These results are based on evaluating random circuits in the Qiskit environment. We have also shown that for the optimization problem to prepare the ground state of a Heisenberg spin-1/2 model on a Kagome lattice, our methods combined with error mitigation resulted in solutions with 100% fidelity. We will then show in a general setting of learning Boolean functions in the PAC model that concentration always yields a quantum advantage when the error bounds are constant. We conclude the talk by showing that Shor’s celebrated algorithm can be derived as a special case of our framework and that its correctness can be shown to follow from the overarching theme that high spectral concentration yields quantum advantage. When relevant, our results will be presented in the framework of the query complexity model. 

Krishna V. Palem is the CEO and co-founder of Accelequant, a start-up company which aims to accelerate the commercial deployment of quantum computing. In the past, he has held academic appointments at several universities, most recently as the Ken and Audrey Kennedy professor at Rice University. He has led efforts internationally in the area of embedded systems and is well-known for having pioneered the area of inexact computing. His work and that of his students in the latter area has been recognized as groundbreaking and has received best-paper awards and his advisees Suren Talla and Lakshmi Chakrapani have been recognized respectively with a Janet Fabri Prize and a Sigma Xi best dissertation award. Inexact computing has been referred to as one of the ten technologies "likely to change the way we live" by MIT's Technology Review, and as one of the seven "emerging world changing technologies" by IEEE as part of its 125th anniversary celebrations. He was a Schonbrunn Fellow at the Hebrew University of Jerusalem and a Moore Scholar at Caltech. He is a fellow of the AAAS, ACM and IEEE, and a recipient of a Guggenheim Fellowship and the W. Wallace McDowell Award, IEEE Computer Society's highest technical award. Earlier, he was the founding CTO of a venture funded company Proceler Inc. and invented the technology behind architecture assembly which was recognized with an analysts’ choice award.