log in  |  register  |  feedback?  |  help  |  web accessibility
Logo
Quantum Query Complexity of Symmetric Oracle Problems
Shih-Han Hung
Virtual - https://umd.zoom.us/j/93284680492?pwd=RHEvWGtoSk03T2FLblh0bkFldHNYQT09
Monday, October 19, 2020, 2:00-3:00 pm Calendar
  • You are subscribed to this talk through .
  • You are watching this talk through .
  • You are subscribed to this talk. (unsubscribe, watch)
  • You are watching this talk. (unwatch, subscribe)
  • You are not subscribed to this talk. (watch, subscribe)
Abstract

In this talk, I will present quantum query complexity of symmetric oracle problems. In particular, we will be exploring the query complexity of quantum learning problems in which the oracles form a group G of unitary matrices, and a description of the optimal success probability of a t-query quantum algorithm in terms of group characters. More generally, in the coset identification problem, for a subgroup H of group G, the task is to determine which coset the group element belongs to. The authors provide character-theoretic formulas for the optimal success probability achieved by a t-query algorithm for this problem. It generalizes a number of well-known quantum algorithms including the Bernstein-Vazirani problem, the van Dam problem and finite field polynomial interpolation.

This talk is organized by Yusuf Alnawakhtha