Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Introduction to Complexity Theory Column 54

Lane A. Hemaspaandra

Published Apr 1, 2008• 0 citations
OpenAlex

Abstract

about small depth quantum circuits and Salil Vadhan writing on the complexity of zero knowledge. And warmest thanks to Jiong Guo and Rolf Niedermeier for this issue’s article on data reduction

Related papers

Special Issue “Quantum computation complexity theory and quantum network theory” (Preface)

Junde Wu

International Journal of Theoretical Physics•Jun 2, 2021•0 citations

SIGACT News Complexity Theory Column 107

Lane A. Hemaspaandra

Warmest thanks to Mark Bun and Justin Thaler for their terri c article, \Approximate Degree in Classical and Quantum Computing." And, amazingly, they made the time to craft it during a time of worldwide pandemic|wow!

ACM SIGACT News•Dec 14, 2020•0 citations

Complexity Lower Bounds for Quantum Circuits

Mika Hirvensalo

Springer eBooks•Jan 1, 2004•0 citations

The role of help in Classical and Quantum Zero-Knowledge

André Chailloux, Iordanis Kerenidis

We study the role of help in Non-Interactive Zero-Knowledge protocols and its relation to the standard interactive model. In the classical case, we show that help and interaction are equivalent, answering an open question of Ben-Or and Gutfreund. This implies a new complete problem for the class SZK, the Image Intersection Density. For this problem, we also prove a polarization lemma which is stronger than the previously known one. In the quantum setting, we define the notion of quantum help and show in a more direct way that help and interaction are again equivalent. Moreover, we define quantum Non-Interactive Zero-Knowledge with classical help and prove that it is equal to the class of languages that have classical honest-Verifier Zero Knowledge protocols secure against quantum Verifiers. Last, we provide new complete problems for all these quantum classes. Similar results were independently discovered by Dragos Florin Ciocan and Salil Vadhan.

arXiv:0711.4251•Nov 27, 2007•2 citations

SIGACT News Complexity Theory Column 119

Ben Lee Volk

After a short break, the complexity theory column is back! In this issue, Sevag Gharibian introduces us to the multifaceted nature of Quantum NP and its relation to Snow White (yes, it all makes sense if you read the column). Thanks a lot to Sevag for his dedication and thoroughness and the effort he put into his fantastic contribution.

ACM SIGACT News•Dec 29, 2023•0 citations

Complexity Lower Bounds for Quantum Circuits

Mika Hirvensalo

Springer eBooks•Jan 1, 2001•0 citations
We study the role of help in Non-Interactive Zero-Knowledge protocols and its relation to the standard interactive model. In the classical case, we show that help and interaction are equivalent, answering an open question of Ben-Or and Gutfreund. This implies a new complete problem for the class SZK, the Image Intersection Density. For this problem, we also prove a polarization lemma which is stronger than the previously known one. In the quantum setting, we define the notion of quantum help and show in a more direct way that help and interaction are again equivalent. Moreover, we define quantum Non-Interactive Zero-Knowledge with classical help and prove that it is equal to the class of languages that have classical honest-Verifier Zero Knowledge protocols secure against quantum Verifiers. Last, we provide new complete problems for all these quantum classes. Similar results were independently discovered by Dragos Florin Ciocan and Salil Vadhan.