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

ACM SIGACT News

SIGACT News Complexity Theory Column 127 and 128

Ben Lee Volk

Published Mar 31, 2026• 0 citations
Publisher

Abstract

Dear Readers, After a short hiatus, the complexity theory column is back with a double feature! In this issue, we present a column by Mitali Bafna on Size-Efficient PCPs from High-Dimensional Expanders, and a column by Fernando Granha Jeronimo, Itai Leigh and Pei Wu on the landscape of complexity classes surrounding QMA(2). Both columns are excellent, and I am sure you will find them both enjoyable and enlightening. Many thanks to the authors for their hard work! What's coming up next in the pipeline? If all goes according to plan, we will feature guest columns by Geoffroy Couteau; Jesse Goodman (on seedless extractors); Davi Castro-Silva, Arkopal Dutt, and Tom Gur (on connections between additive combinatorics and quantum complexity theory); Debarati Das; and Jeroen Zuiddam (on matrix multiplication, moment polytopes and asymptotic spectra). Stay tuned for upcoming issues of SIGACT News!

DOI
10.1145/3802807.3802812

Related papers

SIGACT News Complexity Theory Column 123

Ben Lee Volk

Introduction to Complexity Theory Column 123We close off 2024 with a fantastic guest column by Stacey Jeffery, on the surprising intricacies regarding composition of quantum algorithms.Stacey also did great work in providing illuminating intuitive explanations and figures, so trust me -you don't want to miss it!What's in store for 2025?We expect to publish guest columns by Igor Carboni Oliveira (on Meta-Mathematics of Computational Complexity Theory), Noam Mazor (topic TBA), Elena Grigorescu (on Locally Decodable Codes for Insertions and Deletions) and Mitali Bafna (on Highdimensional expanders and their applications to PCPs and codes), so stay tuned!

arXiv:2502.09240•ACM SIGACT News•Dec 27, 2024•1 citation

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

SIGACT News Complexity Theory Column 110

Lane A. Hemaspaandra

My deepest thanks to Beatrice and Carlo for their fascinating article, Quantum Finite Automata: From Theory to Practice. Regarding the extent to which their article brings to life both parts of its subtitle... wow! And I think Section 4 is an absolute first for this column; please don't miss it!

ACM SIGACT News•Oct 17, 2021•0 citations

Guest Column: The 7 faces of quantum NP

Sevag Gharibian

When it comes to NP, its natural definition, its wide applicability across scientific disciplines, and its timeless relevance, the writing is on the wall: There can be only one. Quantum NP, on the other hand, is clearly the apple that fell far from the tree of NP. Two decades since the first definitions of quantum NP started rolling in, quantum complexity theorists face a stark reality: There's QMA, QCMA, QMA1, QMA(2), StoqMA, and NQP. In this article aimed at a general theoretical computer science audience, I survey these various definitions of quantum NP, their strengths and weaknesses, and why most of them, for better or worse, actually appear to fit naturally into the complexity zoo.

arXiv:2310.18010•ACM SIGACT News•Dec 29, 2023•20 citations

Quantum Computing Algorithms and Computational Complexity

Pelayo, Fernando L., Mezzini, Mauro

This reprint is mainly concerned with quantum algorithms, their mathematics from behind and the complexity issues arising from them. It comprises seven papers: Two of them are focused on improving the performance by means of quantum algorithms over the best instances of classical ones: A Fast Quantum Image Component Labeling Algorithm [1] by Yan Li, Dapeng Hao, Yang Xu and Kinkeung Lai. Quantum Algorithms for Some Strings Problems Based on Quantum String Comparator [2] by Kamil Khadiev, Artem Ilikaev and Jevgenijs Vihrovs. Another four papers deal with enhanced quantum algorithms: Progress towards Analytically Optimal Angles in Quantum Approximate Optimisation: [3] by Daniil Rabinovich, Richik Sengupta, Ernesto Campos, Vishwanathan Akshay and Jacob Biamonte. Quantum Weighted Fractional Fourier Transform [4] by Tieyu Zhao, Tianyu Yang and Yingying Chi. On the Amplitude Amplification of Quantum States Corresponding to the Solutions of the Partition Problem [5] by Mauro Mezzini, Jose J. Paulet, Fernando Cuartero, Hernan I. Cruz and Fernando L. Pelayo. On the Complexity of Finding the Maximum Entropy Compatible Quantum State [6] by Serena Di Giorgio and Paulo Mateus. Last, but not least, one paper researched a classical operational research problem by means of quantum annealing: GPS: A New TSP Formulation for Its Generalizations Type QUBO [7] by Saul Gonzalez-Bermejo, Guillermo Alonso-Linaje and Parfait Atchade-Adelomou. As Guest Editors, we would like to thank the authors and reviewers who made this possible by promoting, spreading research on and supporting quantum computing.

MDPI eBooks•Oct 10, 2023•1 citation

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
Dear Readers, After a short hiatus, the complexity theory column is back with a double feature! In this issue, we present a column by Mitali Bafna on Size-Efficient PCPs from High-Dimensional Expanders, and a column by Fernando Granha Jeronimo, Itai Leigh and Pei Wu on the landscape of complexity classes surrounding QMA(2). Both columns are excellent, and I am sure you will find them both enjoyable and enlightening. Many thanks to the authors for their hard work! What's coming up next in the pipeline? If all goes according to plan, we will feature guest columns by Geoffroy Couteau; Jesse Goodman (on seedless extractors); Davi Castro-Silva, Arkopal Dutt, and Tom Gur (on connections between additive combinatorics and quantum complexity theory); Debarati Das; and Jeroen Zuiddam (on matrix multiplication, moment polytopes and asymptotic spectra). Stay tuned for upcoming issues of SIGACT News!
Introduction to Complexity Theory Column 123We close off 2024 with a fantastic guest column by Stacey Jeffery, on the surprising intricacies regarding composition of quantum algorithms.Stacey also did great work in providing illuminating intuitive explanations and figures, so trust me -you don't want to miss it!What's in store for 2025?We expect to publish guest columns by Igor Carboni Oliveira (on Meta-Mathematics of Computational Complexity Theory), Noam Mazor (topic TBA), Elena Grigorescu (on Locally Decodable Codes for Insertions and Deletions) and Mitali Bafna (on Highdimensional expanders and their applications to PCPs and codes), so stay tuned!
When it comes to NP, its natural definition, its wide applicability across scientific disciplines, and its timeless relevance, the writing is on the wall: There can be only one. Quantum NP, on the other hand, is clearly the apple that fell far from the tree of NP. Two decades since the first definitions of quantum NP started rolling in, quantum complexity theorists face a stark reality: There's QMA, QCMA, QMA1, QMA(2), StoqMA, and NQP. In this article aimed at a general theoretical computer science audience, I survey these various definitions of quantum NP, their strengths and weaknesses, and why most of them, for better or worse, actually appear to fit naturally into the complexity zoo.
This reprint is mainly concerned with quantum algorithms, their mathematics from behind and the complexity issues arising from them. It comprises seven papers: Two of them are focused on improving the performance by means of quantum algorithms over the best instances of classical ones: A Fast Quantum Image Component Labeling Algorithm [1] by Yan Li, Dapeng Hao, Yang Xu and Kinkeung Lai. Quantum Algorithms for Some Strings Problems Based on Quantum String Comparator [2] by Kamil Khadiev, Artem Ilikaev and Jevgenijs Vihrovs. Another four papers deal with enhanced quantum algorithms: Progress towards Analytically Optimal Angles in Quantum Approximate Optimisation: [3] by Daniil Rabinovich, Richik Sengupta, Ernesto Campos, Vishwanathan Akshay and Jacob Biamonte. Quantum Weighted Fractional Fourier Transform [4] by Tieyu Zhao, Tianyu Yang and Yingying Chi. On the Amplitude Amplification of Quantum States Corresponding to the Solutions of the Partition Problem [5] by Mauro Mezzini, Jose J. Paulet, Fernando Cuartero, Hernan I. Cruz and Fernando L. Pelayo. On the Complexity of Finding the Maximum Entropy Compatible Quantum State [6] by Serena Di Giorgio and Paulo Mateus. Last, but not least, one paper researched a classical operational research problem by means of quantum annealing: GPS: A New TSP Formulation for Its Generalizations Type QUBO [7] by Saul Gonzalez-Bermejo, Guillermo Alonso-Linaje and Parfait Atchade-Adelomou. As Guest Editors, we would like to thank the authors and reviewers who made this possible by promoting, spreading research on and supporting quantum computing.