Mind the Gap

Julius Vidal · Kaloyan Aleksiev · Shashvat Shukla

“Do you guys just put the word Quantum in front of everything?”
Ant-Man, Ant-Man and the Wasp (2018)

Can the search for the right scientific questions be automated with AI?

A large part of scientific research is asking the right questions. In quantum algorithms research a good question is sometimes “What is the quantum equivalent of X?”, where X is some existing Classical Computer Science idea. From quantum Turing machines and quantum automata, to quantum machine learning and quantum search the Antman principle of sticking the word quantum before any Classical Computing idea has often yielded impressive results.

Of course there are limits, we may not need quantum markdown or a quantum bogosort. But when we encounter a Classical CS concept that does not yet have a quantum equivalent, especially in fields that are already substantially ‘quantumised’ such as Algorithms & Data-structures or Machine Learning, it's probably at least worth asking “why isn’t there a quantum version of this?” and “what might it look like if there was?”.

One of the bottlenecks in this hunt for quantum gaps is that to ask the question, someone has to have actually heard of the original CS concept and focus their attention on it. The sheer number of Classical Computer Science concepts available makes it easy for promising research directions to be missed.

And even once we identify a concept to investigate, the task of checking whether or not the quantum version already exists can prove time consuming since it involves searching for and reading relevant papers. One also needs to check whether the result is a quantum implementation of the algorithm, an application of the algorithm to a problem that arises in quantum, an application of quantum to the problem the algorithm solves, or just a random article that somehow contained the right keywords to show up in your search results by accident.

Therefore we asked the natural question: Can the task of finding good “quantumisations” be automated? In the advent of AI, this task seems addressable – LLMs possess vast knowledge in diverse scientific disciplines and agentic systems can be developed that search at scale and apply their inherent reasoning abilities to understand to what extent an idea has been integrated in the field of quantum.

One of the great benefits about automating a task is that it does not just make that task faster/cheaper to do, it also totally changes the scale at which you can do it. Rather than simply trying to look for the quantum equivalent of particular concepts on demand, we set out to look for the quantum version of every single concept in Classical Computer Science. Thus creating a comprehensive ‘gap analysis’ of quantum computing with respect to classical. This introduces a set of addressable research problems that can hopefully push the boundaries of knowledge for quantum research.

Approach

To do this the first thing we needed was a way to identify all the concepts to look for equivalents of. We initially considered simply taking every CS paper on arXiv and looking for a corresponding quantum paper, but this seemed too granular. Computer science is a storied and crowded field, and most new papers correspond to minor variations on existing ideas rather than unique concepts in their own right. Instead we looked for existing taxonomies of the field and eventually settled on WikiCSSH.

WikiCSSH had two useful properties for us:

  1. Each concept corresponds to a Wikipedia page, which would give our system the information needed to search for and evaluate potentially relevant papers.
  2. The tree-like taxonomy structure could be traversed with breadth first search. Which is useful for not wasting compute on dead ends (e.g. if we have already established there is no quantum equivalent of graphics software, there is no need to look for an equivalent of some sub-category such as 3D-animation software).

For the initial experiment we decided to focus on Algorithms and Data Structures.

Then it was a matter of actually looking for the quantum analogues. We needed to develop an understanding of what “quantumisation” means, so we came up with the following classification:

We then built the following agentic loop:

  1. Claude 3.7 Sonnet to read the summary of the wikipedia page and generate multiple search queries specifically aiming to investigate if this concept or related mathematical concepts have a quantum equivalent.
  2. Use the search queries to find papers. (We tested a few search mechanisms like Semantic Scholar [or custom RAG over a subset of papers] but we found simple search engine tool to be quite performant and sufficient)
  3. Use Claude 3.7 Sonnet to classify the papers into the classification and provide reasoning as to why.
  4. Use Claude 3.5 Haiku to write a more concise explanation of the decision, using the previous model’s reasoning chain.

Results and Discussion

Looking at the resulting data structure we identified the following “gaps”:

  1. What class of problems require a lot of quantum memory as a resource? That is, are there some memory-hard or memory-bound functions in quantum computing? Asked from another perspective, is there some way to do a proof-of-quantum-space?
  2. Is it possible to infer information about quantum computations from side-channel data such as memory access patterns? What kinds of protocols can be developed to achieve oblivious memory access on quantum computers, in analogy with classical ORAM?
  3. Is there a compressed/opportunistic data structure for classically representing quantum states?
  4. Are there any quantum algorithms that have a better best case time complexity than any possible classical algorithm? How should we formalise this?
  5. There are a number of concepts in data structures that have little connection to quantum computing, how should they be connected: E.g. retroactive, persistent, kinetic data structures.
  6. How will memory management apply in quantum computers with hierarchical memory?

The final results are available in our Github repo here.

We developed a simple visualisation tool that has two modes:

The graph visualisation is available here and the code is here.

This approach presents a compelling case for how AI can be used not just to answer scientific questions, but to ask them — a paradigm shift that holds the promise for automating scientific research or introducing recursive loops of self-improvement. This is the logical next step of scaling intellectual exploration in a way that simply isn’t feasible for human researchers alone towards a more general AI for Science.

The idea that AI can serve as a kind of epistemic scout — exploring through vast fields of knowledge (perhaps grounded in a strict taxonomy) to find places where a new question should exist — opens up a fascinating new research frontier.

The natural next step is to use reasoning models to propose solutions or research strategies for filling those gaps. That means offering plausible analogies, concrete blueprints for a quantum counterpart to a classical idea, and pointers to the mathematical tools that could bridge the two—pushing the boundaries of what any individual scientist can achieve.

Stay tuned for part 2.