Franz J. Schreiber
@fjschreiber.bsky.social
PhD student @ Eisert Group, FU Berlin. Quantum Information Theory
Pinned
The fastest quantum algorithms for 3-SAT achieve only quadratic, Grover-type speedups over the best classical algorithms. Optimality of this is unknown. I think we should look at algorithms that do more than put Grover on top of a classical base. (See link for paper below)
Reposted by Franz J. Schreiber
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 Franz J. Schreiber
Grover's quadratic speedup is provably optimal in the black-box setting. We expect general SAT to be essentially unstructured and as hard as the black-box setting (strong exponential time hypothesis). It's believable that Grover is optimal there. But this is not clear for 3-SAT.
November 14, 2025 at 6:50 AM
Grover's quadratic speedup is provably optimal in the black-box setting. We expect general SAT to be essentially unstructured and as hard as the black-box setting (strong exponential time hypothesis). It's believable that Grover is optimal there. But this is not clear for 3-SAT.
The fastest quantum algorithms for 3-SAT achieve only quadratic, Grover-type speedups over the best classical algorithms. Optimality of this is unknown. I think we should look at algorithms that do more than put Grover on top of a classical base. (See link for paper below)
November 14, 2025 at 6:50 AM
The fastest quantum algorithms for 3-SAT achieve only quadratic, Grover-type speedups over the best classical algorithms. Optimality of this is unknown. I think we should look at algorithms that do more than put Grover on top of a classical base. (See link for paper below)
Reposted by Franz J. Schreiber
Quantum state tomography for states that vary with parameters such as time or control settings attains new capabilities in characterization of evolving quantum states.
go.aps.org/3SAelEa
go.aps.org/3SAelEa
June 8, 2025 at 5:41 AM
Quantum state tomography for states that vary with parameters such as time or control settings attains new capabilities in characterization of evolving quantum states.
go.aps.org/3SAelEa
go.aps.org/3SAelEa
Reposted by Franz J. Schreiber
Artificially intelligent Maxwell's demon for optimal control of open quantum systems
iopscience.iop.org/article/10.1...
A reinforcement learning agent in #machinelearning is interpreted literally as a thermodynamic agent reminiscent of a #Maxwell's demon for the control of open quantum systems.
iopscience.iop.org/article/10.1...
A reinforcement learning agent in #machinelearning is interpreted literally as a thermodynamic agent reminiscent of a #Maxwell's demon for the control of open quantum systems.
April 8, 2025 at 4:16 AM
Artificially intelligent Maxwell's demon for optimal control of open quantum systems
iopscience.iop.org/article/10.1...
A reinforcement learning agent in #machinelearning is interpreted literally as a thermodynamic agent reminiscent of a #Maxwell's demon for the control of open quantum systems.
iopscience.iop.org/article/10.1...
A reinforcement learning agent in #machinelearning is interpreted literally as a thermodynamic agent reminiscent of a #Maxwell's demon for the control of open quantum systems.
Reposted by Franz J. Schreiber
🎉I am very happy to see our Barren Plateau Review published in Nature Review Physics. This article condenses 6 years of our LANL work, but also so many amazing papers by the community!!
Check it here 👇
www.nature.com/articles/s42...
Check it here 👇
www.nature.com/articles/s42...
Barren plateaus in variational quantum computing - Nature Reviews Physics
Barren plateaus are widely considered as one of the main limitations for variational quantum algorithms. This Review summarizes the latest understandings of barren plateaus, indicating its causes, arc...
www.nature.com
March 27, 2025 at 5:50 PM
🎉I am very happy to see our Barren Plateau Review published in Nature Review Physics. This article condenses 6 years of our LANL work, but also so many amazing papers by the community!!
Check it here 👇
www.nature.com/articles/s42...
Check it here 👇
www.nature.com/articles/s42...
Reposted by Franz J. Schreiber
The "hide the exponential" game Scott Aaronson has complained about for decades is alive and well: arxiv.org/abs/2412.13164
Yes, Shor's algorithm with 3 registers only needs very basic operations.
No, you can't pack a 2^2000 level quantum state into 1 oscillator and then operate accurately on it.
Yes, Shor's algorithm with 3 registers only needs very basic operations.
No, you can't pack a 2^2000 level quantum state into 1 oscillator and then operate accurately on it.
Factoring an integer with three oscillators and a qubit
A common starting point of traditional quantum algorithm design is the notion of a universal quantum computer with a scalable number of qubits. This convenient abstraction mirrors classical computatio...
arxiv.org
December 19, 2024 at 2:07 AM
The "hide the exponential" game Scott Aaronson has complained about for decades is alive and well: arxiv.org/abs/2412.13164
Yes, Shor's algorithm with 3 registers only needs very basic operations.
No, you can't pack a 2^2000 level quantum state into 1 oscillator and then operate accurately on it.
Yes, Shor's algorithm with 3 registers only needs very basic operations.
No, you can't pack a 2^2000 level quantum state into 1 oscillator and then operate accurately on it.
Reposted by Franz J. Schreiber
Here is the referee report for that paper. :) Same would apply here.
December 19, 2024 at 2:37 PM
Here is the referee report for that paper. :) Same would apply here.
Reposted by Franz J. Schreiber
New work out today 📝
Very insightful collaboration with colleagues from Fraunhofer HHI and the great @jenseisert.bsky.social. We offer a preview of explainable AI #xAI for #Quantum learning models #QML ⚛️🧠. Check it out and let us know your thoughts!
Very insightful collaboration with colleagues from Fraunhofer HHI and the great @jenseisert.bsky.social. We offer a preview of explainable AI #xAI for #Quantum learning models #QML ⚛️🧠. Check it out and let us know your thoughts!
December 20, 2024 at 10:40 PM
New work out today 📝
Very insightful collaboration with colleagues from Fraunhofer HHI and the great @jenseisert.bsky.social. We offer a preview of explainable AI #xAI for #Quantum learning models #QML ⚛️🧠. Check it out and let us know your thoughts!
Very insightful collaboration with colleagues from Fraunhofer HHI and the great @jenseisert.bsky.social. We offer a preview of explainable AI #xAI for #Quantum learning models #QML ⚛️🧠. Check it out and let us know your thoughts!
Reposted by Franz J. Schreiber
It seems that OpenAI's latest model, o3, can solve 25% of problems on a database called FrontierMath, created by EpochAI, where previous LLMs could only solve 2%. On Twitter I am quoted as saying, "Getting even one question right would be well beyond what we can do now, let alone saturating them."
December 20, 2024 at 11:15 PM
It seems that OpenAI's latest model, o3, can solve 25% of problems on a database called FrontierMath, created by EpochAI, where previous LLMs could only solve 2%. On Twitter I am quoted as saying, "Getting even one question right would be well beyond what we can do now, let alone saturating them."
Reposted by Franz J. Schreiber
Very happy with this joint paper with Paula Belzig, Li Gao, and Peixue Wu! The main goal is to understand how much distinguishability can be preserved under the action of a noisy channel. We study this with (relative) expansion coefficients.
scirate.com/arxiv/2411.1...
scirate.com/arxiv/2411.1...
Reverse-type Data Processing Inequality
The quantum data processing inequality states that two quantum states become harder to distinguish when a noisy channel is applied. On the other hand, a reverse quantum data processing inequality char...
scirate.com
December 4, 2024 at 3:07 PM
Very happy with this joint paper with Paula Belzig, Li Gao, and Peixue Wu! The main goal is to understand how much distinguishability can be preserved under the action of a noisy channel. We study this with (relative) expansion coefficients.
scirate.com/arxiv/2411.1...
scirate.com/arxiv/2411.1...
Reposted by Franz J. Schreiber
Troy's morning lecture was truly great, as a friendly introduction to quantum computing for algorithms designers.
Abstracting the quantum aspects as "new rules of the game, and blackbox primitives you can use" is really speaking to a classical (T)CS audience!
Abstracting the quantum aspects as "new rules of the game, and blackbox primitives you can use" is really speaking to a classical (T)CS audience!
Day 2: Troy Lee (UTS) on Quantum Algorithms!
Lecture in the morning, tutorial this afternoon.
Lecture in the morning, tutorial this afternoon.
December 4, 2024 at 2:37 AM
Troy's morning lecture was truly great, as a friendly introduction to quantum computing for algorithms designers.
Abstracting the quantum aspects as "new rules of the game, and blackbox primitives you can use" is really speaking to a classical (T)CS audience!
Abstracting the quantum aspects as "new rules of the game, and blackbox primitives you can use" is really speaking to a classical (T)CS audience!
Reposted by Franz J. Schreiber
The plot thickens:
"While all the proofs in the paper are correct to the best of our knowledge, we have been recently informed about a classical attack on our polynomial system."
"While all the proofs in the paper are correct to the best of our knowledge, we have been recently informed about a classical attack on our polynomial system."
When it rains new quantum algorithms with a potential advantage, it pours:
arxiv.org/abs/2411.14697
arxiv.org/abs/2411.14697
Quantum Advantage via Solving Multivariate Quadratics
In this work, we propose a new way to (non-interactively, verifiably) demonstrate Quantum Advantage by solving the average-case $\mathsf{NP}$ search problem of finding a solution to a system of (under...
arxiv.org
December 2, 2024 at 2:00 PM
The plot thickens:
"While all the proofs in the paper are correct to the best of our knowledge, we have been recently informed about a classical attack on our polynomial system."
"While all the proofs in the paper are correct to the best of our knowledge, we have been recently informed about a classical attack on our polynomial system."
Reposted by Franz J. Schreiber
The PCP theorem, a jewel of theoretical computer science, establishes that any NP statement can be assessed by a randomized verifier who only checks a vanishing fraction of the proof (indeed, a constant # of characters!)
This has had incredible impact, most notably on how ML reviews are conducted
This has had incredible impact, most notably on how ML reviews are conducted
November 26, 2024 at 5:33 AM
The PCP theorem, a jewel of theoretical computer science, establishes that any NP statement can be assessed by a randomized verifier who only checks a vanishing fraction of the proof (indeed, a constant # of characters!)
This has had incredible impact, most notably on how ML reviews are conducted
This has had incredible impact, most notably on how ML reviews are conducted
Reposted by Franz J. Schreiber
It's tough to gain visibility as a young researcher, and it's job market season! Are you a theoretical computer science PhD/postdoc on the job market?
I don't have a crazy juge audience but I'll try to help a bit: fill this form, and I'll tweet your pitch and info!
docs.google.com/forms/d/e/1F...
I don't have a crazy juge audience but I'll try to help a bit: fill this form, and I'll tweet your pitch and info!
docs.google.com/forms/d/e/1F...
Theoretical CS Job Market 2024
docs.google.com
November 23, 2024 at 11:56 PM
It's tough to gain visibility as a young researcher, and it's job market season! Are you a theoretical computer science PhD/postdoc on the job market?
I don't have a crazy juge audience but I'll try to help a bit: fill this form, and I'll tweet your pitch and info!
docs.google.com/forms/d/e/1F...
I don't have a crazy juge audience but I'll try to help a bit: fill this form, and I'll tweet your pitch and info!
docs.google.com/forms/d/e/1F...
Reposted by Franz J. Schreiber
In the spirit of trying to use this thing properly, rather than just lurking like I did on TwiXer, a community I'd like to be more plugged into is people using memory systems for research (Anki, Mochi, etc, but for more than language learning or memorising capital cities). So I've made a list.
November 24, 2024 at 8:12 AM
In the spirit of trying to use this thing properly, rather than just lurking like I did on TwiXer, a community I'd like to be more plugged into is people using memory systems for research (Anki, Mochi, etc, but for more than language learning or memorising capital cities). So I've made a list.