Audrey Dot, Joseph Fourier University
Barbara Terhal, RWTH Aachen University
Caslav Brukner, Institute for Quantum Computing (IQC)
Guoxing Miao, Institute for Quantum Computing (IQC)
Vadym Kliuchnikov, Institute for Quantum Computing (IQC)
TBD
Melanie Jensenworth, University of Washington
A welded tree is a graph consisting of two binary trees "welded"
together with a random cycle between the leaves. In 2003, Childs et
al. showed that a quantum walk has an exponential speedup over
classical algorithms when traversing the graph from one root vertex to
the other. I give evidence that related graphs also have an
exponential gap between classical algorithms and the quantum walk.
David Gosset, Institute for Quantum Computing (IQC)
Jonathan Friedman, Amherst College
Pragya Shukla, Indian Institute of Technology Kharagpur
We provide the first two-party protocol allowing Alice and Bob to evaluate privately even against active adversaries a completely positive, trace-preserving map F, given as a quantum circuit, upon their joint quantum input state. Our protocol leaks no more to any active adversary than an ideal functionality for F provided Alice and Bob have the cryptographic resources for active secure two-party classical computation.