iiinova — where your digital self keeps evolving

Reposted by Franz J. Schreiber

Richard Kueng @richardkueng.bsky.social · 21/10/2025

(I/III) We're excited to announce a new tenure track opening! The position is called 'quantum informatics' and is affiliated with our QUICK group within the CS+AI division at @jku.at 🇦🇹. Application deadline is November 30th, 2025: www.jku.at/en/the-jku/w...

12817

Reposted by Franz J. Schreiber

Henry Yuen @henryyuen.bsky.social · 13/11/2025

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

arxiv.org

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...

1496

Reposted by Franz J. Schreiber

Franz J. Schreiber @fjschreiber.bsky.social · 14/11/2025

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.

121

Franz J. Schreiber @fjschreiber.bsky.social · 14/11/2025

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)

181

Reposted by Franz J. Schreiber

Jens Eisert @jenseisert.bsky.social · 08/06/2025

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

2143

Reposted by Franz J. Schreiber

Jens Eisert @jenseisert.bsky.social · 08/04/2025

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.

1274

Reposted by Franz J. Schreiber

Marco Cerezo @mvscerezo.bsky.social · 27/03/2025

🎉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...

nature.com

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...

22810

Reposted by Franz J. Schreiber

Craig Gidney @craiggidney.bsky.social · 19/12/2024

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.

arxiv.org

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...

2508

Reposted by Franz J. Schreiber

Steve Flammia @sflammia.bsky.social · 19/12/2024

Here is the referee report for that paper. :) Same would apply here.

1466

Reposted by Franz J. Schreiber

Elies Gil-Fuster @eliesgf.bsky.social · 20/12/2024

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!

0142

Reposted by Franz J. Schreiber

Timothy Gowers @wtgowers.bsky.social · 20/12/2024

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."

8868

Reposted by Franz J. Schreiber

Graeme Smith @graemesmith.bsky.social · 04/12/2024

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

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...

2352

Reposted by Franz J. Schreiber

Clément Canonne @ccanonne.github.io · 04/12/2024

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!

1131

Reposted by Franz J. Schreiber

anthony-leverrier.bsky.social @anthony-leverrier.bsky.social · 02/12/2024

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."

292

Reposted by Franz J. Schreiber

Clément Canonne @ccanonne.github.io · 26/11/2024

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

715520

Reposted by Franz J. Schreiber

Clément Canonne @ccanonne.github.io · 23/11/2024

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...

docs.google.com

Theoretical CS Job Market 2024

210538

Reposted by Franz J. Schreiber

Alex Townsend-Teague @townsend-teague.bsky.social · 24/11/2024

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.

151