research
∙
05/08/2023
Tight Bounds for Quantum Phase Estimation and Related Problems
Phase estimation, due to Kitaev [arXiv'95], is one of the most fundament...
share
research
∙
03/01/2022
Influence in Completely Bounded Block-multilinear Forms and Classical Simulation of Quantum Algorithms
The Aaronson-Ambainis conjecture (Theory of Computing '14) says that eve...
research
∙
12/29/2021
Exact quantum query complexity of computing Hamming weight modulo powers of two and three
We study the problem of computing the Hamming weight of an n-bit string ...
research
∙
10/25/2021
Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints
Lasso and Ridge are important minimization problems in machine learning ...
research
∙
07/25/2021
Tight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error
We investigate the randomized and quantum communication complexities of ...
research
∙
05/04/2021
A Guide for New Program Committee Members at Theoretical Computer Science Conferences
In theoretical computer science, conferences play an important role in t...
research
∙
12/09/2020
Symmetry and Quantum Query-to-Communication Simulation
Buhrman, Cleve and Wigderson (STOC'98) showed that for every Boolean fun...
research
∙
11/25/2020
Quantum algorithms for matrix scaling and matrix balancing
Matrix scaling and matrix balancing are two basic linear-algebraic probl...
research
∙
09/17/2020
Improved Quantum Boosting
Boosting is a general method to convert a weak learner (which generates ...
research
∙
11/17/2019
Quantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solving
Graph sparsification underlies a large number of algorithms, ranging fro...
research
∙
07/19/2019
Quantum Computing: Lecture Notes
This is a set of lecture notes suitable for a Master's course on quantum...
research
∙
11/25/2018
Exponential Separation between Quantum Communication and Logarithm of Approximate Rank
Chattopadhyay, Mande and Sherif (ECCC 2018) recently exhibited a total B...
research
∙
09/30/2018
Two new results about quantum exact learning
We present two new results about exact learning by quantum computers. Fi...
research
∙
09/26/2018
Improved bounds on Fourier entropy and Min-entropy
Given a Boolean function f:{-1,1}^n→{-1,1}, the Fourier distribution ass...
research
∙
09/03/2018
Convex optimization using quantum oracles
We study to what extent quantum algorithms can speed up solving convex o...
research
∙
12/14/2017