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