Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with hidden subgroup problem:
TR06-055 | 10th April 2006
Scott Aaronson, Greg Kuperberg

Quantum Versus Classical Proofs and Advice

This paper studies whether quantum proofs are more powerful than
classical proofs, or in complexity terms, whether QMA=QCMA. We prove
two results about this question. First, we give a "quantum oracle
separation" between QMA and QCMA. More concretely, we show that any
quantum algorithm needs order sqrt(2^n/(m+1)) queries to find ... more >>>

TR10-030 | 18th February 2010
Airat Khasianov

Stronger Lower Bounds on Quantum OBDD for the Hidden Subgroup Problem

Revisions: 2

We consider the \emph{Hidden Subgroup} in the context of quantum \emph{Ordered Binary Decision Diagrams}.
We show several lower bounds for this function.
In this paper we also consider a slightly more general definition of the
hidden subgroup problem (in contrast to that in \cite{khashsp1}). It turns out that ... more >>>

TR16-109 | 18th July 2016
Scott Aaronson

The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes

This mini-course will introduce participants to an exciting frontier for quantum computing theory: namely, questions involving the computational complexity of preparing a certain quantum state or applying a certain unitary transformation. Traditionally, such questions were considered in the context of the Nonabelian Hidden Subgroup Problem and quantum interactive proof systems, ... more >>>

TR18-193 | 14th November 2018
Nicollas Sdroievski, Murilo Silva, André Vignatti

The Hidden Subgroup Problem and MKTP

We show that the Hidden Subgroup Problem for black-box groups is in $\mathrm{BPP}^\mathrm{MKTP}$ (where $\mathrm{MKTP}$ is the Minimum $\mathrm{KT}$ Problem) using the techniques of Allender et al (2018). We also show that the problem is in $\mathrm{ZPP}^\mathrm{MKTP}$ provided that there is a \emph{pac overestimator} computable in $\mathrm{ZPP}^\mathrm{MKTP}$ for the logarithm ... more >>>

ISSN 1433-8092 | Imprint