|
COMPUTER SCIENCE SEMINAR Date and time: 14:00, Friday, 10 March, 2023 Venue: Lecture Hall 6, CMI Realizing quantum advantage across multiple applications Krishna V. Palem Rice University. 10-03-23 Abstract 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 advantage 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 O(sqrt(k) log N) steps, compared to Grover's algorithm which takes O(sqrt(N) steps. The notion of focusing the scarce computational resources or Qbits 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. 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 a 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. For ease of exposition, our results will be presented in the query complexity model used routinely to characterize the efficiency of quantum algorithms. This work was done jointly with Kaden Hazard (Rice University), Duc Hung Pham (Rice University), M. V. Panduranga Rao (IIT Hyderabad) and Surya Sai Teja (IIT Hyderabad).
|
