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 110

Lane A. Hemaspaandra

Published Oct 17, 2021• 0 citations
Publisher

Abstract

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!
DOI
10.1145/3494656.3494665

Related papers

The Complexity of Probabilistic versus Quantum Finite Automata

Gatis Midrijānis

arXiv:quant-ph/0309080•Lecture notes in computer science•Jan 1, 2002•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

Comparing Classical And Quantum Finite Automata

Kaitlin Gili, Rudy Raymond, Rodney Van Meter +1 more

Bulletin of the American Physical Society•Mar 5, 2019•0 citations

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

On the State Complexity of Semi-quantum Finite Automata

Shenggen Zheng, Jozef Gruska, Daowen Qiu

Lecture notes in computer science•Jan 1, 2014•10 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!