Building a quantum computer is hard. Finding problems where it can actually outperform classical computers may be even harder.

That’s one of the problems we’re working on at Magic State Labs. We accelerate quantum algorithm discovery: generating ideas, stress-testing them, and helping researchers explore mathematical territory faster than traditional workflows allow.

In our latest paper, Discovering New Problems for Decoded Quantum Interferometry, we identify two new optimization problems that show promise as candidates for quantum advantage.¹ Establishing such an advantage is particularly difficult in optimization, where classical algorithms are formidable competitors. As a result, the portfolio of concrete optimization problems for which we have strong, provable evidence of quantum advantage remains small. Our goal is to expand that portfolio.

Our starting point is decoded quantum interferometry (DQI), a framework that turns error-correction techniques into tools for quantum optimization.² We developed mathematical filters to make the search for new applications agent-friendly: does the required decoder exist, are its guarantees strong enough, and does the same structure give classical algorithms a shortcut? With researchers guiding the process, agents explored candidates and helped develop the most promising ideas.¹

Two problems emerged:

• Alternant max-agreement. The task is to find an encoded message that satisfies as many conflicting constraints as possible. Because the problem is built from codes used in cryptography, it provides a natural setting for exploring cryptographic protocols and quantum services that can exploit private information.

• Multiplicative polynomial intersection. This is a knapsack-like problem in which products take the place of sums: the goal is to combine mathematical building blocks so that their products come close to multiple targets. The underlying ideas may also inform approaches to resource allocation and planning, where the central challenge is choosing combinations that satisfy competing objectives.

For both problems, we prove decoding guarantees and compare DQI against a specified classical strategy. Under the comparison models studied in the paper, DQI’s predicted average solution quality also exceeds what the classical solvers we tested achieved on larger instances under fixed computational budgets.

Together, these results make both problems compelling candidates for quantum advantage: their mathematical structure supports a rigorous quantum–classical separation under the models we analyze, while the numerical evidence points in the same direction.¹

DQI is only a starting point. Ultimately, we want to discover new quantum primitives—the building blocks from which algorithms are made—and uncover a much broader zoo of quantum algorithms beyond the frameworks we already know.

We believe the future of research will increasingly be machine-driven: systems that propose ideas, test them, search for counterexamples, and change direction when the evidence demands it.

We are not just looking for the next quantum algorithm. We are building a lab that can keep discovering them.

References

1. Rhik Mazumder and Pradeep Niroula. Discovering New Problems for Decoded Quantum Interferometry. Magic State Labs, 2026.

2. Stephen P. Jordan et al. Optimization by Decoded Quantum Interferometry, 2025.