John Bostanci
@johnbostanci.bsky.social
Reposted by John Bostanci
FOCS 2026 will be held in New York City Nov 8 - 11! CFP is up (link below). Submit your best work in theoretical computer science by April 1, 5pm ET.
March 2, 2026 at 1:41 AM
FOCS 2026 will be held in New York City Nov 8 - 11! CFP is up (link below). Submit your best work in theoretical computer science by April 1, 5pm ET.
Reposted by John Bostanci
In the last post of a 3-part series, Dominik Hangleiter highlights the importance of efficient verification of quantum advantage, and assesses the prospects for achieving it soon.
quantumfrontiers.com/2026/02/28/w...
quantumfrontiers.com/2026/02/28/w...
What is next in quantum advantage?
We are now at an exciting point in our process of developing quantum computers and understanding their computational power: It has been demonstrated that quantum computers can outperform classical …
quantumfrontiers.com
February 28, 2026 at 8:31 PM
In the last post of a 3-part series, Dominik Hangleiter highlights the importance of efficient verification of quantum advantage, and assesses the prospects for achieving it soon.
quantumfrontiers.com/2026/02/28/w...
quantumfrontiers.com/2026/02/28/w...
Reposted by John Bostanci
Congratulations to our colleague John Wright, who has received a 2026 Sloan Fellowship!
chemistry.berkeley.edu/news/seven-u...
chemistry.berkeley.edu/news/seven-u...
February 21, 2026 at 2:37 AM
Congratulations to our colleague John Wright, who has received a 2026 Sloan Fellowship!
chemistry.berkeley.edu/news/seven-u...
chemistry.berkeley.edu/news/seven-u...
Reposted by John Bostanci
How can we make sense of computational problems that we don’t even have the language to describe? I spoke to @henryyuen.bsky.social about what’s missing from the standard approach to quantum complexity theory — read more in @quantamagazine.bsky.social!
A New Complexity Theory for the Quantum Age | Quanta Magazine
Henry Yuen is developing a new mathematical language to describe problems whose inputs and outputs aren’t ordinary numbers.
www.quantamagazine.org
February 17, 2026 at 4:32 PM
How can we make sense of computational problems that we don’t even have the language to describe? I spoke to @henryyuen.bsky.social about what’s missing from the standard approach to quantum complexity theory — read more in @quantamagazine.bsky.social!
Reposted by John Bostanci
The list of accepted papers at #STOC2026 is out:
acm-stoc.org/stoc2026/acc...
Congratulations to all authors!
acm-stoc.org/stoc2026/acc...
Congratulations to all authors!
STOC 2026 - 58th ACM Symposium on Theory of Computing
acm-stoc.org
February 13, 2026 at 1:27 AM
The list of accepted papers at #STOC2026 is out:
acm-stoc.org/stoc2026/acc...
Congratulations to all authors!
acm-stoc.org/stoc2026/acc...
Congratulations to all authors!
Hi, I have a new paper out with Andrew Huang and Vinod Vaikuntanathan! We give another classical oracle separation between QMA and QCMA, and a classical oracle separation between BQP/qpoly and BQP/poly. Based on the Yamakawa-Zhandry code intersection problem.
arxiv.org/abs/2602.09385
arxiv.org/abs/2602.09385
Separating Quantum and Classical Advice with Good Codes
We show an unconditional classical oracle separation between the class of languages that can be verified using a quantum proof ($\mathsf{QMA}$) and the class of languages that can be verified with a c...
arxiv.org
February 11, 2026 at 6:35 PM
Hi, I have a new paper out with Andrew Huang and Vinod Vaikuntanathan! We give another classical oracle separation between QMA and QCMA, and a classical oracle separation between BQP/qpoly and BQP/poly. Based on the Yamakawa-Zhandry code intersection problem.
arxiv.org/abs/2602.09385
arxiv.org/abs/2602.09385
Reposted by John Bostanci
Dominik Hangleiter weighs in with an informative post about a much debated question: Has quantum advantage been achieved? This is the first post in a three-part series.
quantumfrontiers.com/2026/01/06/h...
quantumfrontiers.com/2026/01/06/h...
Has quantum advantage been achieved?
Recently, I gave a couple of perspective talks on quantum advantage, one at the annual retreat of the CIQC and one at a recent KITP programme. I started off by polling the audience on who believed …
quantumfrontiers.com
January 6, 2026 at 9:15 PM
Dominik Hangleiter weighs in with an informative post about a much debated question: Has quantum advantage been achieved? This is the first post in a three-part series.
quantumfrontiers.com/2026/01/06/h...
quantumfrontiers.com/2026/01/06/h...
Reposted by John Bostanci
My student @johnbostanci.bsky.social, Chinmay Nirkhe, Jonas Haferkamp, and Mark Zhandry have put out a tour-de-force paper that shows, relative to a classical oracle, QMA is stronger than QCMA -- i.e., quantum proofs >> classical proofs. Congratulations to the authors! arxiv.org/abs/2511.09551
Separating QMA from QCMA with a classical oracle
We construct a classical oracle proving that, in a relativized setting, the set of languages decidable by an efficient quantum verifier with a quantum witness (QMA) is strictly bigger than those decid...
arxiv.org
November 13, 2025 at 2:59 AM
My student @johnbostanci.bsky.social, Chinmay Nirkhe, Jonas Haferkamp, and Mark Zhandry have put out a tour-de-force paper that shows, relative to a classical oracle, QMA is stronger than QCMA -- i.e., quantum proofs >> classical proofs. Congratulations to the authors! arxiv.org/abs/2511.09551
Reposted by John Bostanci
It's a thrill to announce names of the amazing set of theory people joining NYU CS+CSE this year: @aineshbakshi.bsky.social, Allen Liu, @fermima.bsky.social, Sanjeev Khanna, Tony Metger, and Juan Perdomo.
@nyucourant.bsky.social
@nyutandon.bsky.social
@nyucourant.bsky.social
@nyutandon.bsky.social
June 3, 2025 at 9:20 PM
It's a thrill to announce names of the amazing set of theory people joining NYU CS+CSE this year: @aineshbakshi.bsky.social, Allen Liu, @fermima.bsky.social, Sanjeev Khanna, Tony Metger, and Juan Perdomo.
@nyucourant.bsky.social
@nyutandon.bsky.social
@nyucourant.bsky.social
@nyutandon.bsky.social
Reposted by John Bostanci
I'm hiring a postdoc! If you'd like to work with me on quantum learning, error correction, quantum algorithms, and FTQC at Virginia Tech in the Washington, DC metro area, please apply here: careers.pageuppeople.com/968/cw/en-us...
Details | Postdoctoral Associate - Computer Science | Careers | Division of Human Resources | Virginia Tech
careers.pageuppeople.com
April 28, 2025 at 7:43 PM
I'm hiring a postdoc! If you'd like to work with me on quantum learning, error correction, quantum algorithms, and FTQC at Virginia Tech in the Washington, DC metro area, please apply here: careers.pageuppeople.com/968/cw/en-us...
Reposted by John Bostanci
For sigbovik, I factored all 8 bit ints (up to 255) with a quantum computer github.com/strilanc/fal...
I did it as legit as I possibly could. I ran a correct circuit with no optimization shenanigans. I did correct pre/postprocessing.
It took 121 quantum samples to finish the entire task.
But...
I did it as legit as I possibly could. I ran a correct circuit with no optimization shenanigans. I did correct pre/postprocessing.
It took 121 quantum samples to finish the entire task.
But...
April 1, 2025 at 10:26 PM
For sigbovik, I factored all 8 bit ints (up to 255) with a quantum computer github.com/strilanc/fal...
I did it as legit as I possibly could. I ran a correct circuit with no optimization shenanigans. I did correct pre/postprocessing.
It took 121 quantum samples to finish the entire task.
But...
I did it as legit as I possibly could. I ran a correct circuit with no optimization shenanigans. I did correct pre/postprocessing.
It took 121 quantum samples to finish the entire task.
But...
Reposted by John Bostanci
Congrats to Jeongwan Haah and Ewin Tang on being awarded the 2025 New Horizons in Physics and Maryam Mirzakhani New Frontiers Prizes respectively!
breakthroughprize.org/News/91
breakthroughprize.org/News/91
Breakthrough Prize – Breakthrough Prize Announces 2025 Laureates in Life Sciences, Fundamental Physics, and Mathematics
breakthroughprize.org
April 6, 2025 at 7:22 AM
Congrats to Jeongwan Haah and Ewin Tang on being awarded the 2025 New Horizons in Physics and Maryam Mirzakhani New Frontiers Prizes respectively!
breakthroughprize.org/News/91
breakthroughprize.org/News/91
Reposted by John Bostanci
Our third tutorial of QIP 2025 is “Quantum error correction: a guided tour" by Victor Albert (@vva.bsky.social) from NIST and QuICS, who will gently introduce and visit increasingly important corners of the mega-field of QEC (Sun Feb 23, 9am-12:30pm, Room 302ABC). Overview below:
February 12, 2025 at 5:11 PM
Our third tutorial of QIP 2025 is “Quantum error correction: a guided tour" by Victor Albert (@vva.bsky.social) from NIST and QuICS, who will gently introduce and visit increasingly important corners of the mega-field of QEC (Sun Feb 23, 9am-12:30pm, Room 302ABC). Overview below:
Reposted by John Bostanci
Our second tutorial of QIP 2025 is by Hsin-Yuan (Robert) Huang from #Google Quantum AI on Quantum Learning and Certification (Feb 22 Sat, 2-5:30pm, Room 302ABC). Overview below:
February 11, 2025 at 9:02 PM
Our second tutorial of QIP 2025 is by Hsin-Yuan (Robert) Huang from #Google Quantum AI on Quantum Learning and Certification (Feb 22 Sat, 2-5:30pm, Room 302ABC). Overview below:
Reposted by John Bostanci
QIP 2025 is fast approaching! And we have exciting tutorials lined up on Feb 22-23 (Sat-Sun) right before the conference! First in line, we have Cambyse Rouzé from #inria, whose tutorial will cover Quantum Gibbs Sampling (9am-12:30pm, Room 302ABC).
February 11, 2025 at 8:56 PM
QIP 2025 is fast approaching! And we have exciting tutorials lined up on Feb 22-23 (Sat-Sun) right before the conference! First in line, we have Cambyse Rouzé from #inria, whose tutorial will cover Quantum Gibbs Sampling (9am-12:30pm, Room 302ABC).
Reposted by John Bostanci
Our fourth and final tutorial of QIP 2025 is by Dakshita Khurana from UIUC about Quantum Cryptography and TCS (Sun Feb 23, 2-5:30pm, Room 302ABC). Overview below!
February 12, 2025 at 5:13 PM
Our fourth and final tutorial of QIP 2025 is by Dakshita Khurana from UIUC about Quantum Cryptography and TCS (Sun Feb 23, 2-5:30pm, Room 302ABC). Overview below!
Can't wait to see everyone in NYC for ITCS! :D
January 5, 2025 at 12:22 AM
Can't wait to see everyone in NYC for ITCS! :D
Reposted by John Bostanci
Good news for the new year: if you want a more streamlined proof of the landmark result MIP* = RE, then a new paper does that (and much more):
arxiv.org/abs/2501.00173
(207 pages, though)
arxiv.org/abs/2501.00173
(207 pages, though)
The Aldous--Lyons Conjecture II: Undecidability
This paper, and its companion [BCLV24], are devoted to a negative resolution of the Aldous--Lyons Conjecture [AL07, Ald07].
In this part we study tailored non-local games. This is a subclass of non-...
arxiv.org
January 3, 2025 at 7:35 AM
Good news for the new year: if you want a more streamlined proof of the landmark result MIP* = RE, then a new paper does that (and much more):
arxiv.org/abs/2501.00173
(207 pages, though)
arxiv.org/abs/2501.00173
(207 pages, though)
Finally finished my 9+1, super excited to run the NY marathon next year! 😃
Time to start training 😅
Time to start training 😅
December 15, 2024 at 10:08 PM
Finally finished my 9+1, super excited to run the NY marathon next year! 😃
Time to start training 😅
Time to start training 😅
Reposted by John Bostanci
Peer reviews of the quantum cryptography community have been making me very depressed and nihilistic recently.....
Wrote this just to vent....
gardenofforkingpath.blogspot.com/2024/12/some...
Wrote this just to vent....
gardenofforkingpath.blogspot.com/2024/12/some...
Some thoughts after QIP reviews....
Peer reviews of the quantum cryptography community at the moment: Reviewers from other areas: "Not my area, not interested so reject" Revi...
gardenofforkingpath.blogspot.com
December 9, 2024 at 2:20 AM
Peer reviews of the quantum cryptography community have been making me very depressed and nihilistic recently.....
Wrote this just to vent....
gardenofforkingpath.blogspot.com/2024/12/some...
Wrote this just to vent....
gardenofforkingpath.blogspot.com/2024/12/some...
Reposted by John Bostanci
Now in one place, my sixty favorite theorems covering the six decades of computational complexity.
blog.computationalco...
blog.computationalco...
Favorite Theorems: The Complete List
Now in one place all of my sixty favorite theorems from the six decades of computational complexity (1965-2024). 2015-2024 Graph Isomorphism...
blog.computationalcomplexity.org
December 4, 2024 at 2:07 PM
Now in one place, my sixty favorite theorems covering the six decades of computational complexity.
blog.computationalco...
blog.computationalco...
Reposted by John Bostanci
I just set the maximum possible bounty on a Quantum Computing Stack Exchange problem. I could answer myself, but I know many others could too, and this seemed like fun. quantumcomputing.stackexchange.com/questions/40...
What is the complexity of modulo order-finding problem on classical computer?
It doesn't seem to be NP-complete. But has it been proved to be NP-hard?
quantumcomputing.stackexchange.com
November 28, 2024 at 4:56 PM
I just set the maximum possible bounty on a Quantum Computing Stack Exchange problem. I could answer myself, but I know many others could too, and this seemed like fun. quantumcomputing.stackexchange.com/questions/40...
Reposted by John Bostanci
Meanwhile, it's been 5 months since told at #STOC24, and SIGACT still hasn't made an official announcement about the recipient of the 2024 ACM SIGACT Distinguished Service Award (Sanjeev Arora) and why (commendation).
You'd start to think that they don't really give a damn about service after all.
You'd start to think that they don't really give a damn about service after all.
November 26, 2024 at 9:07 PM
Meanwhile, it's been 5 months since told at #STOC24, and SIGACT still hasn't made an official announcement about the recipient of the 2024 ACM SIGACT Distinguished Service Award (Sanjeev Arora) and why (commendation).
You'd start to think that they don't really give a damn about service after all.
You'd start to think that they don't really give a damn about service after all.