A team of researchers from Georgia Tech, Lawrence Berkeley National Laboratory, the Netherlands eScience Center, and the Georgia Tech Research Institute published a paper in Communications Physics today demonstrating that the fundamental readout bottleneck blocking quantum linear system solvers from delivering their promised speedups has a working solution — at least for the class of quantum states those solvers actually produce. The method, called the Hadamard Random Forest (HRF), reduces the number of distinct measurement circuits required to fully reconstruct a quantum state from an exponentially growing count to a count that grows only linearly with qubit number — from 3^N to N+1 — and does so without sacrificing reconstruction accuracy, as validated on IBM’s Heron r2 superconducting processor. The catch, and the insight, is that the method only works for quantum states whose amplitudes are entirely real-valued. That structural restriction turns out to cover the very family of algorithms — quantum linear system solvers — that researchers have targeted as the most commercially promising near-term quantum applications.
The significance of this is not incremental. Since Harrow, Hassidim, and Lloyd introduced the first quantum algorithm for solving linear equations in 2009, the field has recognized that the theoretical speedup the algorithm promises — exponential improvement over classical methods for certain well-conditioned sparse matrices — depends entirely on being able to read out the solution efficiently. A theoretical speedup that cannot be extracted from the hardware is not a speedup. The readout cost problem has shadowed quantum linear system algorithms for 15 years, and HRF is the first method validated on real hardware that directly removes it for the real-valued case that those algorithms most commonly produce.
Why Does Reading Out a Quantum Computer Cost Exponentially More as Qubits Grow?
When a quantum algorithm finishes, extracting its answer requires characterizing the quantum state it produced — a process called quantum state tomography. For a general N-qubit quantum state, that characterization requires measurements in every combination of the three standard Pauli bases — X, Y, and Z — across all qubits, producing 3^N distinct measurement configurations. For a 10-qubit system, that is already 59,049 settings. For 20 qubits, it exceeds 3.4 billion. Even the most aggressive prior approaches — compressed sensing, classical shadow protocols, permutationally invariant tomography — reduce that scaling under specific structural assumptions, but none eliminates the exponential dependency for general states.
This is not a peripheral concern. Quantum linear system algorithms produce their answers encoded in quantum states. Extracting those answers requires reconstructing the state vector, and that reconstruction cost can erase the very speedup the algorithm was designed to deliver. A warning that has circulated among quantum computing theorists since the HHL algorithm was introduced — that the readout overhead would swallow the runtime advantage — has remained unresolved for any general class of practically relevant quantum states.
The Georgia Tech paper directly addresses this warning. By restricting to real-valued states — a subclass that covers the variational quantum linear system solvers the field has most actively targeted — HRF reduces the number of distinct measurement circuits from exponential to linear without sacrificing reconstruction accuracy.
Which Quantum States Are Real-Valued, and Why That Matters
A general N-qubit quantum state assigns a complex number — an amplitude with both magnitude and phase — to each of the 2^N computational basis states. Reconstructing those complex amplitudes is why full tomography needs to sweep through all three Pauli bases: the Z-basis recovers magnitudes, while the X and Y bases together resolve the complex phases.
Real-valued quantum states are a structural special case: every amplitude is a real number, meaning the only phase information is a sign — either +1 or −1. States produced by Grover’s search algorithm, the Bernstein-Vazirani algorithm, and the family of variational quantum linear system solvers are all real-valued in this sense. This is not a narrow restriction; it is precisely the class of algorithms where practical quantum advantage has been most concretely argued. The HRF method exploits this: it replaces the need to sweep three Pauli bases with a targeted procedure that recovers magnitudes in the Z-basis and probes signs using single Hadamard gates on individual qubits. That is N+1 circuits in total — one for magnitudes, one per qubit for signs — regardless of system size.
How Hadamard Random Forest Works
The amplitude recovery step uses a single circuit: it measures the system in the standard computational basis, and the resulting probability distribution directly encodes |ψ_j|² for each basis state j. From those probabilities, the amplitudes’ magnitudes are extracted.
Recovering the signs is the technical challenge HRF solves. For each qubit k, applying a Hadamard gate to qubit k before measurement creates a rotated basis that mixes pairs of computational basis states — specifically, the states at hypercube vertices that differ only in bit k. The resulting probability distribution encodes the relative sign between those pairs, as detailed in the HRF paper’s sign-recovery derivation. Each such circuit requires only a single-qubit gate, making the procedure hardware-friendly on near-term processors.
The sign information these circuits produce, however, is relative: it tells you the sign relationship between neighboring states in the N-dimensional hypercube graph Q_N, but propagating that information to assign absolute signs to all 2^N states requires traversing the hypercube from a fixed reference. This traversal — spanning the hypercube with consistent sign paths — is sensitive to sampling noise: a single miscalculated relative sign can corrupt the signs of all states reachable through that path.
HRF handles this with a random-forest majority vote. Rather than using a single spanning tree to propagate signs, the method generates N_tree random spanning trees of the hypercube using breadth-first search, computes independent sign assignments for each tree, and takes the majority vote for each basis state. Because the hypercube graph is bipartite — vertices divide into two groups based on Hamming weight parity — the sign voting is efficiently parallelizable across classical processor clusters. With 11 trees, the method achieves sign error rates below 3% on 10-qubit states sampled under realistic hardware noise.
After sign recovery, maximum likelihood estimation (MLE) enforces physical consistency on the reconstructed state vector — ensuring it is normalized and matches measurement statistics. This post-processing step carries the unavoidable exponential cost: Ω(2^N) operations, because the state vector itself has 2^N entries. The authors note that this cost is parallelizable and, for 10-qubit systems, completes in under a minute of classical computation. Their estimate for a 14-qubit equivalent — based on prior benchmarks for full quantum state tomography post-processing — projects HRF completing in roughly 10 minutes against a baseline of several hours.
IBM Hardware Validation
The team tested HRF on IBM’s Heron r2 superconducting processor (ibm_fez), the platform IBM designated as its most advanced publicly accessible device at time of the experiments.
The comparison against full quantum state tomography (FQST) was direct. For 5-qubit systems, FQST requires 3^5 = 243 measurement settings and ran for approximately 10 minutes of processor time on the same hardware. HRF required 6 settings — N+1 = 6 for a 5-qubit system — and completed its measurement phase in 18 seconds. At 10 qubits, the exponential scaling makes full tomography impractical on the same hardware within a reasonable time budget; HRF completed sampling in under a minute.
Reconstruction fidelity held up well under these compressed conditions. Across five random real-valued states at 10 qubits, HRF achieved an average fidelity of 89%, outperforming 5-qubit full tomography’s 84% while using fewer total measurement shots. Crucially, the reconstructed states could be used to compute nonlinear properties accurately: quantum entanglement (measured via logarithmic negativity), quantum “magic” (measured via stabilizer Rényi entropy), and state overlap — a quantity that appears naturally in numerical integration problems with applications to computational fluid dynamics and electromagnetic scattering simulations.
The method also outperformed the standard SWAP test for state overlap estimation. The SWAP test is a standard quantum protocol for computing overlap between two states; HRF delivers higher accuracy on the same task with smaller circuits and fewer ancilla qubits under realistic hardware noise. That means HRF is not merely a tomography improvement: it is a competitive replacement for a common quantum subroutine.
What Remains Exponential
The paper is careful about one boundary that HRF does not cross: post-processing cost. Writing down a 2^N-entry state vector requires 2^N storage, and verifying that reconstruction against 2^N measurement outcomes requires 2^N operations. No algorithm can escape this for full reconstruction, and HRF does not claim to. The exponential cost is in the classical computation that follows the quantum measurement, not in the quantum circuits that perform it.
For applications where the goal is to extract a single property of the solution state — an expectation value, an overlap, an entanglement measure — the post-processing burden may be reducible further, and the authors note this as a direction for follow-on work. For full state vector reconstruction, the irreducible classical cost remains exponential, though the parallelizability of the bipartite hypercube structure makes it tractable at the qubit counts relevant to near-term hardware.
Quantum Linear Solver Advantage: What Changes Now
Quantum linear system solvers are near the top of every list of applications where quantum computers are expected to demonstrate genuine computational advantage in the near-to-medium term. The relevant domains are large: computational fluid mechanics, finite-element structural analysis, machine learning model training at scale, and quantum chemistry all involve solving large, sparse systems of linear equations. The theoretical speedup for these problems under favorable conditions is exponential — the kind of advantage that, if realized end-to-end, would matter for industrial-scale computation.
The readout problem has been the recognized gap between that theoretical speedup and any practical demonstration. HRF fills that gap for the real-valued case that variational quantum linear system solvers natively produce. The Georgia Tech team demonstrated this directly: they implemented HRF on a variational quantum linear system solver, demonstrating end-to-end applicability from algorithm execution to state reconstruction to property extraction. The code and data are publicly available under an MIT license at the open-source HRF repository.
Field Context: Assumption-Aware Tomography Takes Over
HRF enters a field that has been moving toward what researchers call assumption-aware tomography — methods that trade universality for practicality by targeting specific structural classes of quantum states. Quandela demonstrated single-basis quantum tomography on a photonic platform on June 26, as described in Quandela’s photonic tomography paper, and a separate research team published a stabilizer state tomography framework with polynomial-time complexity under bounded-magic assumptions.
Each of these methods carves a different niche: photonic hardware and single-basis access, stabilizer states with low quantum magic, real-valued amplitude states. HRF is distinctive in what it does and does not assume. It does not assume sparsity. It does not assume low rank. It does not assume limited entanglement or a specific hardware architecture. It assumes only that the amplitudes are real-valued — and for the algorithms where that assumption holds, it delivers a clean exponential-to-linear reduction that can be demonstrated on superconducting hardware available today.
Whether that is enough to unlock the end-to-end quantum advantage that linear system algorithms have long promised remains an open question that depends on hardware error rates, state preparation fidelity, and problem instance structure outside the scope of any single tomography paper. But HRF removes the clearest obstacle that has stood between the theoretical promise and any practical demonstration. For researchers working on quantum linear system applications, that changes the calculus in a way that has not been possible before.
Frequently Asked QuestionsWhat is quantum state tomography and why has it been so expensive?
Quantum state tomography is the process of fully characterizing a quantum state by measuring it in multiple different bases. The problem is that a complete characterization of an N-qubit system requires measurements in every combination of the three standard Pauli bases across all qubits — producing 3^N distinct configurations. For a 10-qubit system, that is nearly 60,000 settings; for 20 qubits, it exceeds 3.4 billion. This exponential scaling has made full tomography impractical for any system large enough to be interesting for computational advantage.
Which quantum algorithms produce the real-valued states that HRF can read out?
HRF applies to any quantum algorithm whose output state has exclusively real-valued amplitudes — meaning the only phase information is a positive or negative sign on each amplitude. Grover’s search algorithm, the Bernstein-Vazirani algorithm, and the family of variational quantum linear system solvers all fall into this category. This is not a narrow restriction: variational quantum linear system solvers are among the most actively pursued near-term quantum applications, covering problems in computational fluid mechanics, finite-element analysis, and machine learning.
What is the readout problem that has blocked quantum linear system advantage?
Quantum linear system algorithms encode their output in a quantum state rather than a classical bit string. To use that output — to verify the solution, compute properties of it, or feed it into further computation — the quantum state must be read out. Traditional tomography makes this read-out exponentially expensive, potentially erasing any speedup the algorithm provides. This “readout problem” has been recognized since the first quantum linear system algorithms were published in 2009 and has remained unresolved for any practically relevant class of quantum states on real hardware until now.
Can researchers use HRF on current IBM quantum hardware today?
Yes. The Georgia Tech team validated HRF specifically on IBM’s Heron r2 processor (ibm_fez) using IBM Quantum services. The complete code and experimental data are available under an MIT open-source license at github.com/comp-physics/Quantum-HRF-Tomography. Any research group with access to IBM Quantum services can apply HRF immediately to algorithms that produce real-valued quantum states.