Quantum Algorithms for Composed Functions With Shared InputsExport this event to calendar

Monday, December 10, 2018 — 2:30 PM EST

Justin Thaler, Georgetown University

The quantum query complexity of a function f measures how many bits of the input a quantum computer must look at in order to compute f. 

Quantum query complexity is known to behave multiplicatively under block composition: for any two functions f, g with quantum query complexities Q(f) and Q(g), the block composition F obtained by applying f to the results of g on disjoint sets of variables satisfies Q(F)=Theta(Q(f) * Q(g)). Meanwhile, "shared-input" compositions, where the copies of the inner functions g may share n inputs in an arbitrary fashion, are not well understood. 

I will describe a general setting in which the overlapping structure of the inputs to copies of g can be exploited algorithmically. Specifically, for any function f, I will give an algorithm for evaluating any shared-input composition of f and g=AND using ~O((Q(f) * n)^{1/2}) quantum queries. As long as Q(f)<<n, this improves on the bound of O(Q(f) * n^{1/2}) that follows by treating each conjunction independently, and is tight for worst-case choices of f. 

I will describe consequences in (classical) circuit complexity and learning theory, and highlight several tantalizing open questions. 

Joint work with Mark Bun and Robin Kothari.

Location 
QNC - Quantum Nano Centre
0101
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
26
27
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
  1. 2020 (10)
    1. August (1)
    2. June (1)
    3. May (1)
    4. March (1)
    5. February (5)
    6. January (2)
  2. 2019 (139)
    1. December (7)
    2. November (10)
    3. October (7)
    4. September (5)
    5. August (10)
    6. July (16)
    7. June (13)
    8. May (15)
    9. April (15)
    10. March (11)
    11. February (20)
    12. January (12)
  3. 2018 (144)
  4. 2017 (131)
  5. 2016 (88)
  6. 2015 (82)
  7. 2014 (94)
  8. 2013 (91)
  9. 2012 (122)
  10. 2011 (117)
  11. 2010 (41)
  12. 2009 (4)
  13. 2008 (1)
  14. 2005 (1)
  15. 2004 (3)