⚛️ quantum physics

The power of oracle access: Optimal sample and query complexity of the abelian state hidden subgroup problem

This paper establishes the optimal sample and query complexities for the abelian state hidden subgroup problem, demonstrating that coherent access to the state-preparation unitary enables a quadratic improvement in error dependence ( $\epsilon$ ) compared to the sample model, thereby settling the problem's complexity in both settings.

Original authors: Yuhan Liu, Jose Carrasco, Jens Eisert, Armando Bellante

Published 2026-09-29

📖 9 min read🧠 Deep dive

CC BY 4.0

Original authors: Yuhan Liu, Jose Carrasco, Jens Eisert, Armando Bellante

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the quest to build machines that can solve problems far beyond the reach of today's computers, scientists have long relied on a specific type of shortcut. These shortcuts, known as quantum algorithms, often work by exploiting the hidden symmetries of a system. Imagine a complex lock with many tumblers; a classical computer might have to try every possible combination of tumblers to find the one that opens it, a process that could take longer than the age of the universe. A quantum computer, however, can sometimes sense the shape of the lock from a distance, identifying the correct combination almost instantly. This ability to find hidden patterns is the engine behind some of the most famous quantum algorithms, including those that could one day break modern encryption codes.

For decades, researchers have focused on a specific type of symmetry problem called the hidden subgroup problem. In this scenario, a computer is given a function that behaves the same way for a hidden group of inputs, but differently for everything else. The goal is to find that hidden group. While this has been solved for simple, orderly groups, a more recent and challenging version has emerged: the state hidden subgroup problem. Here, instead of being given a mathematical function, the computer is given a mysterious quantum state—a delicate configuration of particles. The task is to figure out which operations leave this state unchanged. The difficulty of this task depends heavily on how the computer is allowed to interact with the state. If the computer can only receive static copies of the state, like looking at a photograph, the process is slow. But if the computer can access the machine that created the state, allowing it to run the creation process forward and backward, the rules of the game change entirely.

A new study by researchers at the Max Planck Institute for Quantum Optics and the Freie Universität Berlin has finally settled the question of how fast this problem can be solved under these different conditions. The team proved that the method of access is not just a minor technical detail; it fundamentally dictates the speed of the solution. They demonstrated that if a quantum computer can only look at copies of the unknown state, it must examine a number of copies that grows inversely with the size of the "gap" between the correct symmetry and the wrong ones. In simpler terms, if the signal is faint, the computer needs many, many copies to hear it clearly. However, if the computer has access to the preparation unitary—the actual circuit that builds the state—it can run the process in reverse. This ability to manipulate the state coherently allows the computer to use a technique called amplitude amplification, which acts like a powerful magnifying glass. With this tool, the number of required interactions drops dramatically, improving the speed by a factor equal to the square root of the previous requirement.

The researchers did not just find a faster way to solve the problem; they proved that this speedup is the absolute best possible. They constructed a rigorous mathematical argument showing that no algorithm, no matter how clever, can beat these limits. Even if the computer is allowed to perform the most complex measurements possible on the copies, or if it is given access to even more powerful versions of the preparation machine, the fundamental barrier remains. The study establishes that the quadratic improvement in speed is a genuine feature of having coherent control over the state's creation, not an artifact of a specific algorithm. This finding clarifies the exact source of quantum advantage in these learning tasks, isolating the power of being able to reverse a process versus simply observing its output.

The implications of this work extend beyond abstract theory into the heart of modern physics. The ability to efficiently identify hidden symmetries in quantum states is crucial for understanding complex materials and verifying quantum devices. For instance, the new algorithms can be used to locate where a large quantum system breaks apart into independent, unentangled parts, a task that is vital for understanding how quantum information spreads. They also offer faster ways to identify the stabilizer groups that protect quantum information from errors, which is a cornerstone of building reliable quantum computers. Furthermore, the methods can detect hidden translation symmetries in many-body systems, helping physicists map out the underlying order in complex quantum matter. In each of these applications, the study shows that if the preparation circuit is available, the time required to find the hidden structure shrinks significantly, making previously intractable problems solvable.

The path to this discovery involved a careful balancing act between two competing models of access. In the first model, the "sample" model, the algorithm is treated as a passive observer, handed a pile of identical quantum states. The researchers showed that in this scenario, the number of states needed to find the hidden symmetry is strictly determined by the inverse of the promise gap. If the gap is small, meaning the difference between the correct symmetry and the incorrect ones is subtle, the algorithm needs a large number of samples to distinguish them. The team proved that even with the most advanced collective measurements, where all copies are measured together in a single, complex operation, this limit cannot be broken. The information simply is not there in the copies to be extracted any faster.

In contrast, the second model, the "query" model, grants the algorithm active control. Here, the computer can call upon a unitary operator that prepares the state and its inverse, which undoes the preparation. This access allows the algorithm to interfere with the state, effectively amplifying the correct answer while canceling out the wrong ones. The researchers developed a new algorithm that uses this capability to find the hidden symmetry with a number of queries that scales with the inverse square root of the gap. This represents a massive reduction in the resources needed. To ensure this was not just a lucky break, they constructed a family of difficult problems based on a classic challenge known as Simon's problem. By padding this problem and introducing a fractional version of the oracle, they showed that the lower bound for the query model matches their upper bound exactly. This tight match proves that the algorithm is optimal and that the speedup is intrinsic to the ability to run the preparation process backward.

One of the most significant contributions of the work is the resolution of a long-standing uncertainty about the size of the hidden subgroup. Previous algorithms often assumed a worst-case scenario where the hidden group was very small, leading to resource estimates that depended on the total size of the entire group. The new study introduces an adaptive strategy that allows the algorithm to stop as soon as it has found enough information, regardless of the group's size. This means the complexity now depends on the size of the quotient, or the ratio between the total group and the hidden subgroup. If the hidden subgroup is large, the problem becomes much easier, and the algorithm reflects this by requiring fewer resources. This adaptive stopping rule works without the algorithm needing to know the size of the hidden group in advance, making the solution both efficient and practical.

The study also addresses the role of advanced quantum features like controlled queries and conjugate access. In some theoretical models, having access to the complex conjugate of an operator or the ability to control the oracle with a quantum bit could potentially offer further advantages. The researchers tested these possibilities and found that for the worst-case scenarios they constructed, these extra powers provided no additional benefit. The quadratic speedup achieved by simply having access to the inverse of the preparation unitary was the maximum possible gain. This result is crucial because it suggests that for a broad class of symmetry-learning problems, the ability to reverse the state preparation is the key ingredient, and adding more complex control mechanisms does not yield further asymptotic improvements.

The practical applications of these findings are already being felt in the design of quantum algorithms for specific physical tasks. For example, in the task of locating unentanglement, where the goal is to find the boundaries between independent parts of a quantum system, the new query-based approach offers a quadratic improvement in the dependence on the gap parameter. This means that for systems where the separation between parts is subtle, the coherent access method can find the solution much faster than any method relying on static copies. Similarly, in learning stabilizer groups, which are essential for quantum error correction, the new bounds provide a clearer picture of the resources required. The study clarifies that while the number of copies needed scales with the inverse of the gap, the number of queries scales with the inverse square root, offering a clear path for optimizing quantum verification protocols.

Ultimately, this work provides a definitive map of the terrain for the abelian state hidden subgroup problem. It draws a sharp line between what is possible with passive observation and what is possible with active control. The researchers have shown that the power of quantum algorithms in this domain is not a vague potential but a precisely quantifiable advantage that arises from the ability to coherently manipulate the state preparation. By proving that their algorithms are optimal and that no better method exists, they have closed the book on the complexity of this fundamental problem. The results offer a solid foundation for future research, guiding the development of quantum algorithms that can tackle the most challenging symmetry problems in physics and computer science with the maximum possible efficiency.

Problem Statement

The paper addresses the State Hidden Subgroup Problem (StateHSP) for finite abelian groups. This is a quantum generalization of the standard Hidden Subgroup Problem (HSP), which underpins algorithms like Shor's factoring and Simon's problem.

In the standard HSP, an algorithm queries an oracle $f: G \to X$ that hides a subgroup $H$ by being constant on cosets of $H$ and distinct on others. In StateHSP, the "hiding function" is replaced by an unknown quantum state $|\phi\rangle$ and a unitary representation $R$ of the group $G$ . The goal is to identify the hidden subgroup $H \le G$ such that:

Symmetry: $R(h)|\phi\rangle = |\phi\rangle$ for all $h \in H$ .
Gap: $|\langle\phi|R(g)|\phi\rangle| \le 1 - \epsilon$ for all $g \in G \setminus H$ , where $\epsilon \in (0, 1]$ is a known promise gap.

The paper investigates the complexity of solving this problem under two distinct input access models:

Sample Model: The algorithm has access to $t$ independent copies of the state $|\phi\rangle$ .
Query Model: The algorithm has coherent access to a state-preparation unitary $U_\phi$ (where $U_\phi|0\rangle = |\phi\rangle$ ) and its inverse $U_\phi^\dagger$ .

Existing literature established an upper bound of $O(\log(|G|)/\epsilon)$ copies for the sample model but left open the optimal dependence on $\epsilon$ and whether the size of the hidden subgroup $|H|$ influences complexity. Furthermore, the query complexity for StateHSP had not been studied.

Methodology

The authors employ a combination of quantum algorithmic techniques, information-theoretic lower bounds, and adversary arguments.

1. Algorithmic Framework (Upper Bounds):
The core strategy involves weak Fourier sampling to generate elements of the dual subgroup $H^\perp$ . The algorithm iteratively collects "span-increasing" generators (elements in $H^\perp$ not currently in the span of previously found generators) until $H^\perp$ is fully spanned, at which point $H$ is recovered via classical post-processing (using $(H^\perp)^\perp = H$ ).

Adaptive Stopping Strategy: To avoid the $O(\log |G|)$ overhead when $|H|$ is unknown, the authors introduce an adaptive budgeting mechanism. The algorithm starts with a small iteration budget and increases it whenever a new span-increasing generator is found. This ensures the complexity scales with $\log(|G/H|)$ rather than $\log(|G|)$ .
Sample Model Implementation: The algorithm uses weak Fourier sampling on copies of $|\phi\rangle$ . A key lemma (Lemma 3.7) establishes that if the current span $K^\perp$ is a proper subgroup of $H^\perp$ , the probability of sampling an element in $H^\perp \setminus K^\perp$ is at least $\epsilon/2$ . By repeating the sampling $O(1/\epsilon)$ times, a new generator is found with high probability.
Query Model Implementation: The authors leverage the ability to run $U_\phi$ and $U_\phi^\dagger$ coherently. They construct a subspace identifier (a unitary $U_\perp$ ) that flags Fourier samples lying outside the current span $K^\perp$ . This flagging allows the use of fixed-point amplitude amplification (inspired by Gilyén et al. and Yoder et al.) to boost the probability of finding a new generator from $\epsilon/2$ to near 1 using only $O(1/\sqrt{\epsilon})$ queries.

2. Lower Bound Techniques:

Query Lower Bound: The authors use the adversary method (specifically the relative $\gamma_2$ norm formulation by Belovs). They construct a family of "Fractional Padded Simon's" states. By padding Simon's problem to vary $|H|$ and introducing a fractional oracle that rescales the oracle difference by $\sqrt{\epsilon}$ , they prove that distinguishing instances requires $\Omega(\log(|G/H|)/\sqrt{\epsilon})$ queries. This bound holds even with access to conjugate queries ( $U_\phi^*, U_\phi^T$ ) and controlled queries.
Sample Lower Bound: The authors use information-theoretic tools, specifically Fano's inequality and the Holevo bound. They construct a hard family of instances where the hidden subgroup is chosen from a large set of candidates. They show that each copy of the state provides at most $O(\epsilon)$ bits of information about the hidden subgroup. Consequently, identifying the subgroup with constant probability requires $\Omega(\log(|G/H|)/\epsilon)$ copies, even with arbitrary collective measurements.

Key Contributions and Results

1. Tight Complexity Characterization:
The paper settles the complexity of the abelian StateHSP in both models, providing matching upper and lower bounds up to constant factors:

Access Model	Complexity	Dependence on Parameters
Sample Model (Copies)	$\Theta\left(\frac{\log(\|G/H\|)}{\epsilon}\right)$	Linear in $1/\epsilon$ ; depends on quotient size $\|G/H\|$ .
Query Model (Unitaries)	$\Theta\left(\frac{\log(\|G/H\|)}{\sqrt{\epsilon}}\right)$	Quadratic improvement in $1/\sqrt{\epsilon}$ ; depends on quotient size $\|G/H\|$ .

2. Resolution of Open Questions:

Optimality of $1/\epsilon$ : The paper proves that the $1/\epsilon$ scaling in the sample model is information-theoretically necessary and cannot be improved without coherent access.
Role of Subgroup Size: The complexity depends on $\log(|G/H|)$ , not $\log(|G|)$ . Larger hidden subgroups (smaller quotients) are strictly easier to learn. The adaptive stopping strategy achieves this without prior knowledge of $|H|$ .
Source of Quadratic Speedup: The quadratic improvement in $\epsilon$ (from $1/\epsilon$ to $1/\sqrt{\epsilon}$ ) is shown to arise solely from coherent access to the preparation circuit (enabling amplitude amplification). The lower bound holds even with powerful oracle extensions (conjugate and controlled queries), indicating that amplitude amplification is the maximal advantage available in this setting.

3. Applications:
The authors demonstrate how these improved bounds translate to specific symmetry-learning problems previously formulated as StateHSP instances:

Locating Unentanglement: Identifying tensor-product cuts in multipartite states. The query model improves the scaling with the fidelity gap from $1/\tilde{\epsilon}^2$ to $1/\tilde{\epsilon}$ .
Learning Stabilizer Groups: Recovering the stabilizer group of a quantum state. The query model improves the dependence on the gap parameter $\epsilon$ .
Identifying Translation Symmetries: Finding hidden translational symmetries in many-body states. The complexity scales with the number of invariant translations rather than the system size.

Significance and Claims

The paper claims to provide a complete and tight characterization of the abelian StateHSP. Its significance lies in:

Clarifying the Power of Oracle Access: It isolates the exact computational advantage provided by coherent access to state-preparation unitaries versus mere copies. The results show that while coherent access offers a quadratic speedup in the gap parameter, it does not alter the fundamental logarithmic dependence on the group structure.
Bridging HSP and Learning: By generalizing HSP to StateHSP and providing optimal algorithms, the work connects the algebraic structure of Shor's algorithm with modern quantum learning tasks (stabilizer learning, entanglement detection).
Methodological Rigor: The authors provide time-efficient algorithms that are not only query-optimal but also carefully bound the classical and quantum gate overheads, ensuring the results are practically relevant for time-efficient implementations.

The authors modestly note that while their results optimize the StateHSP reduction for specific applications, the hard instances used for the lower bounds are constructed specifically for the reduction and may not directly reflect the structure of the specific physical problems (like stabilizer learning). Therefore, establishing matching lower bounds for those specific physical problems remains an open direction. Additionally, the necessity of the inverse unitary $U_\phi^\dagger$ for the quadratic speedup is suggested but not rigorously proven for the general case without inverses.

Problem Statement

Methodology

Key Contributions and Results

Significance and Claims

More like this