Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Quantum complexity classes:
TR09-104 | 26th October 2009
Scott Aaronson

BQP and the Polynomial Hierarchy

The relationship between BQP and PH has been an open problem since the earliest days of quantum computing. We present evidence that quantum computers can solve problems outside the entire polynomial hierarchy, by relating this question to topics in circuit complexity, pseudorandomness, and Fourier analysis.

First, we show that there ... more >>>

TR19-086 | 7th June 2019
Alex Bredariol Grilo, William Slofstra, Henry Yuen

Perfect zero knowledge for quantum multiprover interactive proofs

In this work we consider the interplay between multiprover interactive proofs, quantum
entanglement, and zero knowledge proofs — notions that are central pillars of complexity theory,
quantum information and cryptography. In particular, we study the relationship between the
complexity class MIP$^*$ , the set of languages decidable by multiprover interactive ... more >>>

TR24-050 | 5th March 2024
Omri Shmueli

Quantum Algorithms in a Superposition of Spacetimes

Revisions: 1

Quantum computers are expected to revolutionize our ability to process information. The advancement from classical to quantum computing is a product of our advancement from classical to quantum physics -- the more our understanding of the universe grows, so does our ability to use it for computation. A natural question ... more >>>

ISSN 1433-8092 | Imprint