IBM Team Develops Stabilizer Testing Algorithm for Limited Quantum Memory Systems

Arunachalam and Schatzki at IBM show that the previously understood difference between testing and learning stabilizer states disappears as memory capacity diminishes. Their investigation of the fundamental limits of verifying and identifying quantum states with restricted coherent quantum memory reveals the sample complexity of testing these states with limited memory scales with the number of qubits not stored, specifically Θ(n-k), while learning complexity is Θ(n²/k). The findings highlight coherent quantum memory as a key resource for maintaining the separation between testing and learning, and demonstrate that even near-full memory capacity, such as retaining 99% of qubits, does not enable a constant-copy stabilizer tester.

Reduced quantum memory necessitates increased copies for stabiliser state verification

A team at Freie Universität Berlin, in collaboration with researchers at IBM, has overturned a long-held assumption regarding the complexity of testing and learning stabilizer states, a specific type of quantum state crucial for quantum error correction and fault-tolerant quantum computation. Stabilizer states are particularly important as they possess a mathematical structure that simplifies the implementation of error correction protocols. Previously, testing these states required six copies, irrespective of the number of qubits they comprised, while learning, the process of fully identifying the unknown quantum state, demanded a number of copies proportional to the number of qubits. However, this new research demonstrates that the sample complexity of testing has decreased to Θ(n-k), where ‘n’ represents the total number of qubits in the state and ‘k’ is the amount of coherent quantum memory retained between measurements. This represents a significant shift in understanding the resource requirements for quantum state verification.

This signifies a strong improvement over prior methods, and establishes that even retaining 99% of qubits does not allow for a constant-copy stabilizer tester. The implications of this finding are substantial; it suggests that maintaining a fixed number of copies for testing, as previously possible with unlimited memory, becomes increasingly difficult as memory resources become constrained. Stabilizer states, a key component in quantum error correction, require fewer copies for testing than previously believed when limited quantum memory is available. The sample complexity for testing is now expressed as Θ(n-k), where ‘n’ is the total number of qubits and ‘k’ represents the number of qubits retained in quantum memory, a change from prior assumptions of a fixed six copies regardless of state size. This scaling with (n-k) indicates that the number of copies needed for testing grows linearly with the number of qubits not stored in memory. Further analysis revealed that learning the same states, using a non-adaptive approach where measurement settings are determined before observing previous results, demands Θ(n²/k) copies, highlighting a direct relationship between memory capacity and learning efficiency. The inverse relationship with ‘k’ in the learning complexity suggests that increasing memory capacity significantly reduces the number of copies needed to learn the state. Retaining 99% of the qubits, represented as k=0.99n, does not allow for a constant-copy test, indicating a significant constraint on testing efficiency and reinforcing the importance of memory management in quantum algorithms.

Quantum memory limitations redefine the boundaries of state verification and quantum information

Investigations at IBM and Freie Universität Berlin revealed a key interaction between quantum memory and the difficulty of verifying quantum states. Their work addresses a fundamental problem in quantum information: how much information is needed to confirm the validity of a quantum state, and how does this change when storage space is limited. The researchers employed a sequential model, where the algorithm receives copies of an unknown n-qubit state one at a time, and can only maintain coherence of k qubits at any given moment. This constraint mirrors the limitations of current and near-future quantum hardware. The findings highlight a tension between testing and learning, previously thought to be distinct, now converging under restricted conditions. Testing aims to determine if a state belongs to a specific family (in this case, stabilizer states) without necessarily identifying the state itself, while learning seeks to fully reconstruct the unknown quantum state.

These findings do not negate the previously established distinction between testing and learning in ideal conditions with unlimited quantum memory. Seminal work by Gross, Nezami and Walter demonstrated that testing n-qubit stabilizer states could be achieved with six copies when unrestricted memory was available. Instead, the current research pinpoints precisely where that separation breaks down; limited storage fundamentally alters the computational landscape. This is important because practical quantum devices will inevitably face memory constraints due to physical limitations and decoherence, making these results directly relevant to building real-world quantum technologies. The ability to efficiently verify quantum states is paramount for ensuring the reliability of quantum computations and communication protocols.

Understanding how restricted memory impacts verification is therefore vital, even if perfect separation remains theoretically possible elsewhere. The researchers at Freie Universität demonstrated that limited quantum memory reduces the distinction between testing and learning quantum states. The findings establish a connection between storage capacity and the difficulty of verifying these states, a step towards building practical quantum technologies. The algorithm used in this study sequentially receives copies of the unknown state and strategically allocates its limited k qubits of coherent memory to perform measurements. The choice of which qubits to retain and measure is crucial for optimising the testing and learning processes under memory constraints.

Prior work showed testing n-qubit stabilizer states requires 6 copies with unrestricted memory, unlike learning which needs Θ(n) copies. This testing-vs-learning separation is lost when memory is limited, with testing stabilizer states in the k-qubit memory framework needing Θ(n-k) samples, while learning requires Θ(n²/k). The findings clarify how limited quantum memory impacts verifying quantum states, specifically stabilizer states used in quantum error correction. Reduced quantum memory diminishes the previously understood difference between the difficulty of testing, confirming a state’s validity, and learning, fully identifying it. This finding establishes a direct relationship between memory capacity and computational cost, revealing that coherent quantum memory is not simply a convenient resource but a fundamental constraint. The results suggest that as quantum technology advances, optimising memory usage will be as important as increasing qubit count for achieving efficient quantum information processing.

The researchers demonstrated that the efficiency of verifying quantum states is directly linked to the amount of available quantum memory. They found that testing stabilizer states with limited memory requires a number of samples proportional to n-k, where n is the number of qubits in the state and k represents the amount of coherent memory. This contrasts with unrestricted memory scenarios and diminishes the distinction between testing and learning quantum states. The study clarifies that coherent quantum memory is a fundamental resource impacting the complexity of verifying these states, suggesting optimisation of memory usage is crucial for future quantum technologies.