research
∙
11/22/2022
Optimizing the depth of variational quantum algorithms is strongly QCMA-hard to approximate
Variational Quantum Algorithms (VQAs), such as the Quantum Approximate O...
share
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
∙
06/10/2022
Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement
Savitch's theorem states that NPSPACE computations can be simulated in P...
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
∙
11/03/2021
On polynomially many queries to NP or QMA oracles
We study the complexity of problems solvable in deterministic polynomial...
research
∙
12/23/2020
The Complexity of Translationally Invariant Problems beyond Ground State Energies
It is known that three fundamental questions regarding local Hamiltonian...
research
∙
09/19/2019
Almost optimal classical approximation algorithms for a quantum generalization of Max-Cut
Approximation algorithms for constraint satisfaction problems (CSPs) are...
research
∙
09/12/2019
Oracle complexity classes and local measurements on physical Hamiltonians
The canonical problem for the class Quantum Merlin-Arthur (QMA) is that ...
research
∙
05/28/2018
Quantum generalizations of the polynomial hierarchy with applications to QMA(2)
The polynomial-time hierarchy (PH) has proven to be a powerful tool for ...
research
∙
12/27/2017