BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/247
DTSTAMP:20230914T125916Z
SUMMARY:Quantum Query Complexity of State Conversion
DESCRIPTION:Speaker: \n\nAbstract: \nState conversion generalizes query com
plexity to the problem of converting between two input-dependent quantum s
tates by making queries to the input. We characterize the complexity of th
is problem by introducing a natural information-theoretic norm that extend
s the Schur product operator norm. The complexity of converting between tw
o systems of states is given by the distance between them\, as measured by
this norm. In the special case of function evaluation\, the norm is close
ly related to the general adversary bound\, a semi-definite program that l
ower-bounds the number of input queries needed by a quantum algorithm to e
valuate a function. We thus obtain that the general adversary bound charac
terizes the quantum query complexity of any function whatsoever. This gene
ralizes and simplifies the proof of the same result in the case of boolean
input and output. Also in the case of function evaluation\, we show that
our norm satisfies a remarkable composition property\, implying that the q
uantum query complexity of the composition of two functions is at most the
product of the query complexities of the functions\, up to a constant. In
this talk we will focus more on designing new quantum query algorithms us
ing classical tools.\n
URL:https://www.tcs.tifr.res.in/web/events/247
DTSTART;TZID=Asia/Kolkata:20120125T160000
DTEND;TZID=Asia/Kolkata:20120125T170000
LOCATION:AG-80
END:VEVENT
END:VCALENDAR