### General Information

The WQACT 2018, will be held at CQT Level 3 Seminar Room, S15-03-15, Centre for Quantum Technologies, National University of Singapore from 26 Feb to 2 Mar 2018

This workshop will gather experts in randomized and quantum algorithms and complexity theory. The purpose of the workshop is to investigate interesting and important questions related to recent developments in randomized and quantum algorithms and complexity theory.

The broad schedule for talks is as follows:

### Program

 26 Feb, Mon 10:30hr Robin Kothari The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials Abstract We use the polynomial method to prove (nearly) optimal lower bounds on the quantum query complexity of several problems, resolving several open questions from prior work. The problems include k-distinctness, image size testing, k-junta testing, approximating statistical distance, approximating Shannon entropy, and surjectivity. Paper available at https://arxiv.org/abs/1710.09079. 11:15hr Alexander Belov Challenges for the quantum adversary bound Abstract The quantum adversary bound is a fascinating tool to study quantum query complexity theoretically. It provides a tight characterisation of the quantum query complexity, it behaves well with regard to various kinds of composition, it can be applied to problems beyond function evaluation. Still, when it comes to practice, there is much to be desired in terms of applicability of the adversary bound to specific problems. In this talk, I will survey some of the challenges I see in regard of the adversary bound, as well as some recent progress achieved in this direction. This talk is based on some of my on-going research. 12:00hr Lunch 14:00hr Peter Hoyer Some ideas used in quantum walks Abstract To be updated 14:45hr Serge Massar Total Functions in QMA and Testing Quantum States Abstract In analogy with the classical complexity class Total Functions from NP (TFNP), we introduce the complexity class of Total Functions in QMA (TFQMA). In this compleixty class one is given a quantum circuit Q that takes as input a classical string x and a quantum state psi, such that one can prove that for all x, Q(x,psi)=ACCEPT with probability > 2/3. The functional problem is then, given Q and x, find a psi such that Q(x,psi)=ACCEPT with high probability. This complexity of this class lies between the functional analogs of BQP and QMA. A slightly different definition leads us to define the complexity of a subspace or quantum state by the complexity of the quantum circuit that will accept with high probability on the state or subspace, and reject with high probability on orthogonal states. This provides a definition of complexity of states and subspaces that extends the usual definition based on the complexity of the circuit required to produce the state. We provide examples of problems that lie in these complexity classes. 15:30hr Coffee/Tea Break
 27 Feb, Tues 10:30hr Henry Yuen Approximate low-weight check codes and circuit lower bounds for noise ground states Abstract The No Low-Energy Trivial States (NLTS) conjecture of Freedman and Hastings, which asserts the existence of local Hamiltonians whose low energy states cannot generated by constant depth quantum circuits, identifies a fundamental obstacle to resolving the quantum PCP conjecture. Progress towards the NLTS conjecture was made by Eldar and Harrow, who proved a closely related theorem called No Low-Error Trivial States (NLETS). In this work we give a much simpler proof of the NLETS theorem, and use the same technique to establish superpolynomial circuit size lower bounds for noisy ground states of local Hamiltonians (assuming QMA != QCMA), resolving an open question of Eldar and Harrow. We discuss the new light our results cast on the relationship between NLTS and NLETS. Finally, our techniques imply the existence of approximate quantum low-weight check (qLWC) codes with linear distance and constant weight checks. These codes are similar to quantum LDPC codes except (1) each particle may participate in a large number of checks, and (2) errors only need to be corrected up to fidelity 1 − 1/poly(n). This stands in contrast to the best-known stabilizer LDPC codes due to Freedman, Meyer, and Luo which achieve a distance of O(sqrt(n log n)). Joint work with Chinmay Nirkhe and Umesh Vazirani. 11:15hr Dave Touchette Capacity Approaching Coding for Low Noise Interactive Quantum Communication Abstract We consider the problem of implementing two-party interactive quantum communication over noisy channels, a necessary endeavor if we wish to fully reap quantum advantages for communication. For an arbitrary protocol with n messages, designed for noiseless qudit channels (where d is arbitrary), our main result is a simulation method that fails with probability less than exp(-Theta(n epsilon)) and uses a qudit channel n(1 + Theta (sqrt(epsilon))) times, of which an epsilon fraction can be corrupted adversarially. The simulation is thus capacity achieving to leading order, and we conjecture that it is optimal up to a constant factor in the sqrt(epsilon) term. Furthermore, the simulation is in a model that does not require pre-shared resources such as randomness or entanglement between the communicating parties. Surprisingly, this outperforms the best known overhead of 1 + O(sqrt(epsilon log log 1/epsilon)) in the corresponding classical model, which is also conjectured to be optimal [Haeupler, FOCS'14]. Our work also improves over the best previously known quantum result where the overhead is a non-explicit large constant [Brassard et al., FOCS'14] for low epsilon. This is joint work with Debbie Leung, Ashwin Nayak, Ala Shayeghi, Penghui Yao and Nengkun Yu. 12:00hr Lunch 14:00hr Kai-Min Chung Computational Notions of Quantum Min-Entropy Abstract To be updated 14:45hr Jérémie Roland A lower bound technique for information complexity, with applications to the information complexity of quantum correlations Abstract Many lower bound techniques for communication complexity reduce to solving a linear program obtained from the following general recipe: - Show that a communication protocol for the problem leads to a zero-communication protocol (or local hidden variable model in the physics language) that constitutes a feasible point for some linear program. - Construct the dual of this linear program. - Any feasible point for this dual then provides a lower bound for the communication complexity. Obtaining such a feasible point reduces to proving limitations on zero-communication protocols (or proving Bell inequalities in the physics language). Information complexity is a variant of communication where, instead of counting the number of bits communicated by the players, one considers the information these messages reveal about the players' inputs. It has been shown that many of the linear programming based lower bounds for communication complexity also provide lower bounds for information complexity. This is shown by using compression techniques for the zero-communication protocols appearing in the linear program. However, this compression step induces some loss, which can make the bound trivial when the information complexity is very low. Here, we show that, perhaps surprisingly, one can directly obtain lower bounds for information complexity using the same general recipe as for the linear programming based lower bounds for communication complexity. The main difference is that the convex optimization program that is obtained is not linear anymore as the objective function is some entropic quantity. The lower bound then reduces to exhibiting violations for some non-linear Bell-type inequalities. As an application, we show lower bounds for the problem of simulating quantum correlations, a situation where the communication and information complexities are less than one bit, and therefore where the linear programming based techniques lead to trivial bounds for information complexity. Based on work in progress with Mathieu Cavenaile and Mathieu Brandeho 15:30hr Coffee/Tea Break
 28 Feb, Wed 10:30hr Harry Buhrman On nonlocal games with near-perfect quantum strategies Abstract To be updated 11:15hr Zhengfeng Ji Embezzlement-based Bell Inequality Abstract We introduce a three-player nonlocal game, with a finite number of classical questions and answers, such that the optimal success probability of 1 in the game can only be achieved in the limit of strategies using arbitrarily high-dimensional entangled states. The game is based on the coherent state exchange game of Leung et al. which is in turn based on quantum state embezzlement. In our game, the task of the quantum verifier is delegated to a third player by a classical referee. Our results provide a Bell inequality whose violation cannot be maximized with finite amount of entanglement, and complement those of Slofstra (arXiv:1703.08618) and Dykema et al. (arXiv:1709.05032), who obtained two-player games with similar (though quantitatively weaker) properties based on the representation theory of finitely presented groups and C*-algebras respectively. 12:00hr Lunch 14:00hr Shalev Ben-David Classical lower bounds from quantum upper bounds Abstract To be updated 14:45hr Dmitry Gavinsky Quantum versus classical simultaneity in communication complexity Abstract We will see a bipartite partial function, which has no efficient solution in the model of randomised simultaneous message passing (with shared randomness), but has an efficient protocol in the model of quantum simultaneous message passing (even without shared randomness). This can be interpreted as the strongest known, as of today, example of ""super-classical"" capabilities of the weakest studied model of quantum communication. 15:30hr Coffee/Tea Break 16:00hr Frédéric Magniez Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks Abstract The computation of the diameter is one of the most central problems in distributed computation. In the standard CONGEST model, in which two adjacent nodes can exchange O(log n) bits per round (here n denotes the number of nodes of the network), it is known that exact computation of the diameter requires Omega(n) rounds, even in networks with constant diameter. In this talk I will present my recent work with Frédéric Magniez on quantum distributed algorithms for this problem. The main result is a O(\sqrt{nD})-round quantum distributed algorithm for exact diameter computation, where D denotes the diameter. This shows a separation (up to quadratic for networks with small diameter) between the computational power of quantum and classical algorithms in the CONGEST model.
 1 Mar, Thurs 10:30hr Ashwin Nayak Online Learning of Quantum States Abstract Suppose we have many copies of an unknown n-qubit state rho. We measure some copies of rho using a known two-outcome measurement E_1, then other copies using a measurement E_2, and so on. At each stage t, we generate a current hypothesis sigma_t about the state rho, using the outcomes of the previous measurements. We show that it is possible to do this in a way that guarantees that Tr(E_i sigma_{i-1}) differs from Tr(E_i rho) by more than epsilon at most O(n/epsilon^2) times. Even in the non-realizable'' setting---where there could be arbitrary noise in the measurement outcomes---we show how to output hypothesis states that do significantly worse than the best possible states at most O(sqrt(Tn)) times on the first T measurements. These results generalize a 2007 theorem by Aaronson on the PAC-learnability of quantum states, to the online and regret-minimization settings. We give three different ways to prove our results---using convex optimization, quantum postselection, and sequential fat-shattering dimension---which have different advantages in terms of parameters and portability. Joint work with Scott Aaronson, Xinyi Chen, and Elad Hazan. 11:15hr Richard Cleve The computational complexity of simulating Lindblad evolution Abstract The Lindblad equation is a natural generalization of the Schrödinger equation to Markovian evolution. We show that expressing a trajectory under Lindblad evolution in terms of a trajectory of a larger system under Hamiltonian evolution entails a cost blow-up of T^2/epsilon, where [0,T] is the time interval and epsilon is the level of precision. Nevertheless, we show that Lindblad evolution for any specific time T and precision level epsilon can be simulated with complexity O(T polylog(T/epsilon)). This is joint work with Chunhao Wang. 12:00hr Free Afternoon
 2 Mar, Friday 10:30hr Stacey Jeffery Verifier-on-a-Leash: new schemes for verifiable delegated quantum computation, with quasilinear resources Abstract To be updated. 11:15hr Break 12:00hr Lunch 14:00hr Itai Arad Learning quantum Hamiltonians Abstract To be updated 14:45hr Iordanis Kerenedis Quantum methods for optimization and machine learning Abstract To be updated. 15:30hr Coffee/Tea Break

### Local Organising Committee

Divesh Aggarwal
Rahul Jain
Hartmut Klauck
Troy Lee
Miklos Santha

Contacts Details:
Evon Tan (Secretariat)
Centre for Quantum Technologies
National University of Singapore
Block S15, room #03-05
3 Science Drive 2
Singapore 117543

Phone : +65-6516-7019
Fax : +65-6516-6897
Email: cqtthme@nus.edu.sg