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:
WQACT 2018 Program


26 Feb, Mon
10:30hr Robin Kothari
The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials
Arrow 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

11:15hr Alexander Belov
Challenges for the quantum adversary bound
Arrow 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
Arrow Abstract

To be updated

14:45hr Serge Massar
Total Functions in QMA and Testing Quantum States
Arrow 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
Arrow 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
Arrow 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
Arrow 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
Arrow 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
Arrow Abstract

To be updated

11:15hr Zhengfeng Ji
Embezzlement-based Bell Inequality
Arrow 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
Arrow Abstract

To be updated

14:45hr Dmitry Gavinsky
Quantum versus classical simultaneity in communication complexity
Arrow 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
Arrow 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
Arrow 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
Arrow 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
Arrow Abstract

To be updated.

11:15hr Break
12:00hr Lunch
14:00hr Itai Arad
Learning quantum Hamiltonians
Arrow Abstract

To be updated

14:45hr Iordanis Kerenedis
Quantum methods for optimization and machine learning
Arrow 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

    Copyright© 2018 Centre for Quantum Technologies, NUS   Centre for quantum technologies National University of Singapore