Can we have classically verifiable quantum advantage with a quantum cost that is cheaper than, say, factoring?
What are the mathematical features of quantum computations might achieve such an advantage?

By Professor Michael Bremner
Director, Centre for Quantum Software and Information
University of Technology, Sydney
Quantum Algorithms and Complexity Team
Centre for Quantum Computation and Communication Technology

Addressing the problem

This is the problem that we attempt to address in a newly published paper with Dr Bin Cheng (NUS) and Professor Zhengfeng Ji (Tsinghua). Together, we introduce the “IQP stabilizer scheme” as a framework for establishing verifiable tests of quantum computing resources based on a cryptographic assumption, we call the “Hidden Structured Code” problem, which builds on work that Dr Dan Shepherd and I did back in 2008.

This work was driven by Bin during his PhD with Zhengfeng and I (back when both Zhengfeng and Bin were at UTS), and it’s great to see that it has now been published in PRX Quantum, together with an accompanying paper by Professor David Gross and Dr Dominik Hangleiter that investigates the security of this problem. (Interestingly, this isn’t the first time David Gross and I have had back-to-back papers like this and I’m really happy that PRX Quantum decided to publish these papers in this way.)

Introducing IQP

Back in 2008, Dr Dan Shepherd and I created a cryptographic game to attempt to argue that IQP circuits could not be simulated by classical computers efficiently. This was an early example of a verifiable quantum advantage, whose advantage depended on the security of the of this cryptographic game.

This was the paper where we first introduced IQP, which we later argued in papers with Professors Richard Jozsa and Ashley Montanaro would be hard to simulate classically leveraging complexity theoretic assumptions. While these arguments were in many ways stronger, and very useful for helping prove results on quantum advantage and beyond classical computing, they usually only apply to problems that aren’t classically efficiently verifiable.

In the original IQP game Alice would test that Bob has a quantum computer by sending him a description of an IQP circuit, with a planted secret, that she would like him to run and gather measurement samples from. If Bob correctly ran the circuit, then Alice would be able to “verify” Bob’s quantumness by analysing the measurement outcomes to check that they were consistent with the planted secret. Dan and I even put up a website with a challenge problem and a $25NZD bounty!

Figure 1: From the original IQP challenge website, quantumchallenges.wordpress.com

What we liked about this game was that it appeared to be relatively cheap from a quantum computing resources perspective, and it potentially even had some robustness to error as the verification procedure involved detecting a bias, or correlations, in the data that was quite large and so this test may be adaptable to near-term devices.

Vulnerabilities and addressing them

However, biggest problem with our scheme was that we used non-standard cryptographic assumptions. In 2019, Greg Kahanamoku-Meyer, then a student at Berkeley, emailed Dan and I with a list of samples asking us to check them, and the samples passed the test! Did Greg secretly build a quantum computer? No, it turned out that the ad-hoc cryptographic protocol that we created had a flaw, and Greg discovered a way of not only attacking the website’s challenge, but attacking many such protocols. I recently met up with Greg at QIP’25 and finally pay up on the bounty.

In our new paper we discover that Greg’s attack, while interesting, was not complete. It turned out that sometimes it would fail and in our analysis of those failures, we found that we could create a more general IQP game, that enabled a richer set of challenge problems to be generated that evaded the Kahanamoku-Meyer attack. In our new paper we call this generalisation the “IQP stabilizer scheme” as it links elements of the so-called stabiliser formalism, coding theory, and characterisations of IQP correlation functions. Its security depends on a mathematical challenge we call the “Hidden Structured Code” problem. Like in the original paper we also published a challenge problem.

We posted these results to the arXiv in 2023, and a few months later Professor David Gross and Dr Dominic Hangleiter reached out and showed that they could not only beat our challenge problem, but that they had invented a range of new types of attack on these schemes that worked for different choices that could be made. Over the next few months and a lot of back-and-forth with David and Dominic we (mostly Bin!) gradually came to appreciate that there were ways of evading most of these attacks by altering the parameter choices in our original problem.

As a consequence we updated our manuscript and the published version contains this new analysis. Despite the security of our scheme holding (for now!) David and Dominic’s attacks allowed us to better understand the problem, and such work is critical for evaluating the security of such schemes.

There is still a lot to do

Moving forward, there’s still a lot to do on this problem.
The basic question remains, how “secure” is the “Hidden Structured Code” problem. One approach would be to work on enhancing the theoretical arguments for the classical difficulty of this problem. Typically, in cryptography a worst-to-average case reduction would need to be established, can one be found for this problem? Another more practical approach is to continue the back-and-forth of attacking and defending the protocol, which will hopefully reveal more about their structure. Another key question to be examined is the links between this style of problem and what they mean for practically relevant applications both for near- and long-term quantum processors. Both from the perspective of how they can be physically implemented, but also the underlying mathematical structures that can lead to quantum advantage.

Professor Michael Bremner is the Director, Centre for Quantum Software and Information, University of Technology Sydney
and Program Manager of the Quantum Algorithms and Complexity Team for the ARC Centre for Quantum Computation and Communication Technology.