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

arXiv:2502.09240 · ACM SIGACT News

SIGACT News Complexity Theory Column 123

Ben Lee Volk

Published Dec 27, 2024• 1 citation
arXivHTMLPDF

Abstract

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!

DOI
10.1145/3710795.3710801

Related papers

SIGACT News Complexity Theory Column 127 and 128

Ben Lee Volk

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!

ACM SIGACT News•Mar 31, 2026•0 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

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: an introduction to quantum information and quantum circuits 1

John Watrous

column Share on Guest column: an introduction to quantum information and quantum circuits 1 Author: John Watrous Institute for Quantum Computing and School of Computer Science, University of Waterloo Institute for Quantum Computing and School of Computer Science, University of WaterlooView Profile Authors Info & Claims ACM SIGACT NewsVolume 42Issue 2June 2011 pp 52–67https://doi.org/10.1145/1998037.1998053Online:10 June 2011Publication History 6citation143DownloadsMetricsTotal Citations6Total Downloads143Last 12 Months10Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

ACM SIGACT News•Jun 10, 2011•14 citations

SIGACT news logic column 13

Riccardo Pucella

For this issue, Nick Papanikolaou brings us an introduction to the subject of quantum logic and a survey of the relevant literature, including a discussion of logics for specification and analysis of quantum information systems.

ACM SIGACT News•Sep 1, 2005•2 citations

Guest Column: A Primer on the Statistics of Longest Increasing Subsequences and Quantum States (Shortened Version)

Ryan O’Donnell, John Wright

column Share on Guest Column: A Primer on the Statistics of Longest Increasing Subsequences and Quantum States (Shortened Version) Authors: Ryan O'Donnell Carnegie Mellon University, Pittsburgh, PA Carnegie Mellon University, Pittsburgh, PAView Profile , John Wright Massachusetts Institute of Technology, Cambridge, MA Massachusetts Institute of Technology, Cambridge, MAView Profile Authors Info & Claims ACM SIGACT NewsVolume 48Issue 3September 2017 pp 37–59https://doi.org/10.1145/3138860.3138869Published:07 September 2017Publication History 2citation85DownloadsMetricsTotal Citations2Total Downloads85Last 12 Months9Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

ACM SIGACT News•Sep 7, 2017•6 citations
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!
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!
column Share on Guest column: an introduction to quantum information and quantum circuits 1 Author: John Watrous Institute for Quantum Computing and School of Computer Science, University of Waterloo Institute for Quantum Computing and School of Computer Science, University of WaterlooView Profile Authors Info & Claims ACM SIGACT NewsVolume 42Issue 2June 2011 pp 52–67https://doi.org/10.1145/1998037.1998053Online:10 June 2011Publication History 6citation143DownloadsMetricsTotal Citations6Total Downloads143Last 12 Months10Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access
column Share on Guest Column: A Primer on the Statistics of Longest Increasing Subsequences and Quantum States (Shortened Version) Authors: Ryan O'Donnell Carnegie Mellon University, Pittsburgh, PA Carnegie Mellon University, Pittsburgh, PAView Profile , John Wright Massachusetts Institute of Technology, Cambridge, MA Massachusetts Institute of Technology, Cambridge, MAView Profile Authors Info & Claims ACM SIGACT NewsVolume 48Issue 3September 2017 pp 37–59https://doi.org/10.1145/3138860.3138869Published:07 September 2017Publication History 2citation85DownloadsMetricsTotal Citations2Total Downloads85Last 12 Months9Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access