research
∙
08/09/2023
Space-bounded quantum state testing via space-efficient quantum singular value transformation
Driven by exploring the power of quantum computation with a limited numb...
share
research
∙
07/18/2023
No distributed quantum advantage for approximate graph coloring
We give an almost complete characterization of the hardness of c-colorin...
research
∙
07/13/2023
Faster Rectangular Matrix Multiplication by Combination Loss Analysis
Duan, Wu and Zhou (FOCS 2023) recently obtained the improved upper bound...
research
∙
04/11/2023
Robust Dequantization of the Quantum Singular value Transformation and Quantum Machine Learning Algorithms
Several quantum algorithms for linear algebra problems, and in particula...
research
∙
03/03/2023
Quantum Merlin-Arthur proof systems for synthesizing quantum states
Complexity theory typically focuses on the difficulty of solving computa...
research
∙
12/06/2022
Non-trivial lower bound for 3-coloring the ring in the quantum LOCAL model
We consider the LOCAL model of distributed computing, where in a single ...
research
∙
10/04/2022
Distributed Quantum Interactive Proofs
The study of distributed interactive proofs was initiated by Kol, Oshman...
research
∙
10/04/2022
Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications
The generation and verification of quantum states are fundamental tasks ...
research
∙
07/21/2022
Improved Hardness Results for the Guided Local Hamiltonian Problem
Estimating the ground state energy of a local Hamiltonian is a central p...
research
∙
05/10/2022
An optimal oracle separation of classical and quantum hybrid schemes
Recently, Chia, Chung and Lai (STOC 2020) and Coudron and Menda (STOC 20...
research
∙
04/06/2022
Quantum Approximate Counting for Markov Chains and Application to Collision Counting
In this paper we show how to generalize the quantum approximate counting...
research
∙
01/09/2022
Quantum Distributed Algorithms for Detection of Cliques
The possibilities offered by quantum computing have drawn attention in t...
research
∙
11/17/2021
Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
The Quantum Singular Value Transformation (QSVT) is a recent technique t...
research
∙
10/02/2021
Lower Bounds for Induced Cycle Detection in Distributed Computing
The distributed subgraph detection asks, for a fixed graph H, whether th...
research
∙
05/12/2021
Test of Quantumness with Small-Depth Quantum Circuits
Recently Brakerski, Christiano, Mahadev, Vazirani and Vidick (FOCS 2018)...
research
∙
05/06/2021
Quantum Logarithmic Space and Post-selection
Post-selection, the power of discarding all runs of a computation in whi...
research
∙
05/03/2021
Quantum Advantage with Shallow Circuits under Arbitrary Corruption
Recent works by Bravyi, Gosset and König (Science 2018), Bene Watts et a...
research
∙
01/19/2021
Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs
In this paper we give fast distributed graph algorithms for detecting an...
research
∙
11/14/2020
Tight Distributed Listing of Cliques
Much progress has recently been made in understanding the complexity lan...
research
∙
10/23/2020
Quantum Meets Fine-grained Complexity: Sublinear Time Quantum Algorithms for String Problems
Longest common substring (LCS), longest palindrome substring (LPS), and ...
research
∙
07/10/2020
On Distributed Listing of Cliques
We show an Õ(n^p/(p+2))-round algorithm in the model for listing of K_p ...
research
∙
06/26/2020
Quantum Communication Complexity of Distribution Testing
The classical communication complexity of testing closeness of discrete ...
research
∙
03/06/2020
Barriers for rectangular matrix multiplication
We study the algorithmic problem of multiplying large matrices that are ...
research
∙
02/24/2020
Distributed Quantum Proofs for Replicated Data
The paper tackles the issue of checking that all copies of a large data ...
research
∙
10/13/2019
Quantum-Inspired Classical Algorithms for Singular Value Transformation
A recent breakthrough by Tang (STOC 2019) showed how to "dequantize" the...
research
∙
08/30/2019
Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model
This paper considers the triangle finding problem in the CONGEST model o...
research
∙
06/06/2019
Quantum Distributed Algorithm for the All-Pairs Shortest Path Problem in the CONGEST-CLIQUE Model
The All-Pairs Shortest Path problem (APSP) is one of the most central pr...
research
∙
10/30/2018
Average-Case Quantum Advantage with Shallow Circuits
Recently Bravyi, Gosset and König (Science 2018) proved an unconditional...
research
∙
10/25/2018
Quantum Advantage for the LOCAL Model in Distributed Computing
There are two central models considered in (fault-free synchronous) dist...
research
∙
05/09/2018
Interactive Proofs with Polynomial-Time Quantum Prover for Computing the Order of Solvable Groups
In this paper we consider what can be computed by a user interacting wit...
research
∙
04/09/2018
Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks
The computation of the diameter is one of the most central problems in d...
research
∙
08/18/2017