TreeVQA: A Tree-Structured Execution Framework for Shot Reduction in Variational Quantum Algorithms

A variational quantum algorithm finds a molecule's or a problem's ground state by running a quantum circuit millions of times, and a real application needs thousands of such runs — one per configuration to map an energy landscape — driving the total number of quantum executions into the billions; this paper (University of Michigan — Yuewen Hou, Dhanvi Bharadwaj, Gokul Subramanian Ravi) presents TreeVQA, which notices that these related problems have overlapping solutions, so it runs them all together as one shared execution at first and lets them branch apart only as their quantum states diverge — cutting the number of measurement shots by 25.9 times on average and over 100 times for large problems.

The argument in one glance

Problem

Variational quantum algorithms burn through an astronomical number of shots

A variational quantum algorithm (VQA) is one of the most promising ways to get useful work out of today's noisy, pre-fault-tolerant quantum computers. It solves a problem — for example, finding the lowest-energy (ground) state of a molecule — by running a parameterized quantum circuit, measuring it, and having a classical optimizer nudge the circuit's parameters over many iterations until the answer converges. The catch is the sheer number of times the quantum hardware must run. Three factors multiply together. First, a VQA is iterative: exploring a complex problem's landscape can take thousands of optimizer iterations, made worse by device noise. Second, each iteration is not one circuit but many: a chemistry problem's Hamiltonian (the mathematical object encoding the problem) can have thousands of Pauli terms, each needing its own circuits. Third, and most overlooked, a real application is not one problem but thousands of related VQA tasks — for instance, the energy of a molecule at thousands of different geometries, whose collective ground states map out the application's full energy landscape. Multiply these together and a single application demands billions of circuit executions, each requiring many measurement "shots" for statistical precision. That cost, in time and quantum resources, is a show-stopper for practical use, and prior work — classical initialization that trims iterations, or error mitigation that adds shots — has not tamed it.
What people did

Solve each of the thousands of tasks independently, from scratch

The conventional way to run such an application is to treat each VQA task as its own separate job. You take the first molecular geometry, run its VQA to convergence — all its iterations, all its circuits, all its shots — then move to the next geometry and do the whole thing again, and so on for every one of the thousands of tasks. Each task starts fresh and pays its full cost, and prior efforts to reduce shots focus on making an individual task cheaper (better initialization, cleverer measurement) rather than questioning that the tasks are run in isolation at all.
Why it fell short

Running related tasks in isolation repeats the same expensive work thousands of times

Solving each task independently ignores a huge amount of redundancy. The tasks in an application are not arbitrary — they are closely related variations of the same underlying problem, such as the same molecule at slightly different geometries, so their solutions are highly similar. The quantum states that represent their ground states overlap substantially: two nearby geometries converge to nearly the same state through nearly the same optimization trajectory. Running them separately means re-walking almost the same path from scratch thousands of times, paying the full, enormous shot cost for each even though most of that work is nearly identical across tasks. The tasks are distinct enough that you do ultimately need to evaluate each one individually to build the high-precision landscape the application demands — you cannot simply collapse them into one answer — but the bulk of the journey toward those distinct answers is shared. Conventional execution captures none of that sharing. What was missing was a way to do the common part of the work once and only diverge into per-task effort where the tasks actually differ.
This paper's idea

Run the tasks jointly, and branch apart only as their quantum states diverge

TreeVQA exploits the similarity across tasks with a tree-structured execution. Instead of running each task separately, it begins by executing all of the application's VQA tasks together as a single shared quantum execution — one representative optimization standing in for all the tasks at once, forming the root of a tree. As the optimization proceeds and the tasks' quantum states begin to diverge toward their individual solutions, TreeVQA splits the shared execution into branches: dissimilar tasks branch off earlier, while highly similar tasks stay together longer, sharing their execution until close to convergence. This branching continues recursively until, at the leaves, every task is executing independently and converging to its own precise solution. The payoff is the shared work at every internal level of the tree before the leaves — with the greatest savings near the root, where a single execution does the early optimization for all tasks at once, and progressively less sharing as branches split. Because the early, similar part of every task's optimization is done once rather than thousands of times, the total number of shots collapses. TreeVQA is implemented as a wrapper that integrates with typical VQA applications, so it slots around existing algorithms rather than replacing them. On scientific and combinatorial benchmarks it reduces shot counts by 25.9 times on average, and by over 100 times for large-scale problems, at the same target accuracy — and the benefit grows as problems get bigger and demand more precision.

Why this problem is worth solving

Shot cost is the single biggest practical barrier between variational quantum algorithms and real use, so reducing it is what decides whether they are usable at all.

On a quantum computer, you cannot simply read out an answer; you must run a circuit and measure it, and because measurement is probabilistic, you need many repetitions — shots — to estimate a value to the precision you need, with cost scaling steeply as you demand more accuracy. For a variational algorithm this multiplies against everything else: every optimizer iteration needs the expectation value estimated, that estimate needs many circuits for a many-term Hamiltonian, each circuit needs many shots, and a real application stacks thousands of such tasks on top. The result is that the total shot count, not the qubit count or the circuit depth, is often what makes a VQA application infeasible — running it would take an impractical amount of scarce, expensive quantum-computer time. This is why so much research targets shots specifically, and why some techniques that improve accuracy, like error mitigation, are a mixed blessing: they can multiply the shot budget further. Any method that genuinely cuts the number of executions, without sacrificing the accuracy of the final result, directly moves VQAs toward practicality on the hardware that exists today. And because the shot burden grows with problem size and required precision — exactly the directions useful applications push in — a technique whose savings also grow in those directions is attacking the problem where it hurts most.

The deeper insight is that an application’s many tasks are not independent jobs but a family with a shared history, and computation should follow that shared structure.

The conventional view treats each VQA task as a standalone problem to be solved from scratch, which is natural if you look at one task at a time. TreeVQA’s reframing is to look at the whole application and notice that its tasks form a related family: they are the same problem under small variations, and their solutions live close together. When solutions are close, the paths to them are largely shared, so solving each independently redoes nearly the same work over and over. The right structure for computing a family of related solutions is therefore not a flat list of independent runs but a tree, where a common trunk of shared work splits into branches only as the tasks genuinely diverge, and finally into individual leaves. This is the same logic behind computing anything over a set of similar instances efficiently — do the common part once, specialize late — and it maps naturally onto the iterative nature of VQAs, because divergence happens gradually as the optimization proceeds, giving a clear signal of when to branch. The subtlety the design must respect is that the tasks really are distinct and each needs its own precise final answer, so the tree cannot collapse them permanently; it must let them separate in time to converge individually. Getting that timing right — branching dissimilar tasks early and similar ones late, guided by how their quantum executions diverge — is what turns the observation about overlap into a concrete, large, and scalable reduction in cost.

What people did before, and where it broke

Independent per-task execution. Run each VQA task in the application separately, to full convergence. Where it broke. Related tasks share most of their optimization trajectory, so running them in isolation repeats nearly identical, expensive work thousands of times.
Classical initialization. Warm-start each task to cut its iteration count. Where it broke. The benefit is limited and problem-dependent, and it still treats each task as a separate run rather than exploiting cross-task overlap.
Error mitigation (ZNE, PEC, measurement mitigation). Improve result accuracy on noisy hardware. Where it broke. These techniques enormously increase the shot count rather than reduce it, worsening the very cost that blocks practicality.
Per-task shot-reduction methods. Reduce shots within a single task through better measurement or grouping. Where it broke. They optimize one task at a time and miss the far larger opportunity of sharing execution across the thousands of related tasks in an application.
The gap. No approach did the common part of a related family of VQA tasks once and diverged into per-task work only where the tasks actually differ, so the cross-task redundancy of real applications went unexploited.

How TreeVQA works

From thousands of independent runs to one shared execution that branches

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Run a variational quantum algorithm to find a problem’s ground state. TreeVQA operates on VQAs, the near-term quantum approach of optimizing a parameterized circuit toward a problem’s lowest-energy state. Iteratively tuning a quantum circuit’s parameters with a classical optimizer to solve a problem on noisy near-term hardware is the same variational-quantum-algorithm foundation the work on a classical bootstrap for variational quantum algorithms (CAFQA) covered elsewhere on this site builds on, working within the VQA loop to make it more efficient. TreeVQA targets the same loop but attacks the cost across many related tasks rather than within one.

Do the common work once across a family of related instances. TreeVQA’s core move is to share the overlapping computation among many similar tasks instead of redoing it for each. Reusing the large common portion of computation across closely-related problem instances, rather than recomputing it from scratch for every one, is the same shared-computation idea the work on graph analytics over evolving, related data (CommonGraph) covered elsewhere on this site is built on, computing what is common once and only the differences per instance. TreeVQA applies this to a family of VQA tasks whose solutions overlap, sharing their quantum executions until they diverge.

Organize the computation as a tree that specializes late. TreeVQA structures the shared-then-diverging execution as a tree, branching from a common root toward per-task leaves. Structuring a computation as a tree so that a shared path splits into specialized branches only where needed is the same tree-structured-execution idea the work on synthesizing efficient tree traversals (tree-traversal synthesis) covered elsewhere on this site embodies, letting a hierarchical structure capture what is shared versus what is specific. TreeVQA’s tree branches exactly when the tasks’ quantum states diverge, so sharing is maximized near the root and specialization deferred to the leaves.

Following an application through TreeVQA

From eight related tasks to eight converged solutions, sharing along the way

A trace, drawn from the paper's example, of how TreeVQA executes an application of eight related VQA tasks as a branching tree.

Step 1 of 5

Start all tasks at a single shared root

The application's eight VQA tasks (Hamiltonians H1 through H8) begin as one shared quantum execution, represented by a single optimization at the tree root. For the first block of iterations, this one execution advances all eight tasks together.

The heaviest early optimization is paid once, not eight times.

Why it works

Related tasks share most of their optimization path. Their ground states overlap because they are variations of one problem → but running them separately re-walks that path each time → so executing the shared part once removes the bulk of the redundancy.
A tree matches shared-then-divergent structure. A flat list of independent runs captures no sharing → but a tree with a common root and per-task leaves → so common work is done once and specialization deferred to where tasks differ.
Branching on divergence times the split correctly. Splitting too early or too late wastes the opportunity → but branching exactly when the tasks’ quantum states diverge → so dissimilar tasks separate early and similar ones share as long as possible.
Late leaves preserve per-task accuracy. The tasks are distinct and each needs its own answer → but letting branches reach independent leaves before convergence → so every task still converges to its own precise solution at the target accuracy.
A wrapper design keeps it drop-in. Rewriting VQA algorithms would limit adoption → but implementing the tree as a wrapper around existing VQAs → so TreeVQA integrates with typical applications rather than replacing them.

What it costs (trade-offs and scope)

The savings depend on tasks actually being similar. TreeVQA’s benefit comes from overlap among an application’s tasks; an application whose tasks are unrelated, with little shared solution structure, would branch early and gain little.
Deciding when to branch is itself a judgment. The framework must measure how the tasks’ executions diverge and choose split points; branching too eagerly forfeits sharing, too late risks mixing tasks that need separate treatment, so this control matters.
Shared execution needs a representative to stand in for a group. Running many tasks jointly requires a representative optimization for each internal node, and how faithfully that representative captures the group affects both savings and accuracy.
It reduces shots, not qubits or depth. TreeVQA attacks the shot-count bottleneck of VQA applications; it does not by itself reduce the number of qubits, circuit depth, or the noise of the underlying hardware.
Results are on specific benchmarks and accuracy targets. The 25.9-times average and over-100-times large-problem reductions are at a fixed target accuracy on the paper’s scientific and combinatorial benchmarks; other applications, sizes, or accuracy demands may differ, though the paper reports benefits grow with size and precision.

The comparison

Executing an application of many related VQA tasks

Property	Independent per-task runs	Per-task shot reduction	TreeVQA
Cross-task sharing
Handles related-task redundancy
Per-task accuracy
Scales with problem size
Reported shot reduction

Ways to run an application made of many related VQA tasks. Conventional execution runs each task independently to convergence, repeating nearly identical work thousands of times; per-task shot-reduction methods trim one task's cost but miss the cross-task overlap. TreeVQA runs all tasks jointly at a shared root and branches only as their quantum states diverge, doing the common work once and specializing late at independent leaves — cutting shot counts by 25.9 times on average and over 100 times for large problems at the same target accuracy, with benefits growing as problems get bigger. Exact figures should be read from the paper.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

This explainer is based on the paper’s full text (the authors’ arXiv copy, 2512.12068, of the ASPLOS 2026 paper; code at github.com/isaachyw/TreeVQA). The described system is the paper’s: variational quantum algorithms (VQAs) demand enormous numbers of measurement shots because they are iterative (thousands of iterations), each iteration runs many circuits (Hamiltonians with thousands of Pauli terms), and real applications comprise thousands of related tasks whose ground states map an energy landscape, driving total executions into the billions. TreeVQA’s observation is that these tasks are highly similar — their ground-state quantum states overlap — so it executes them jointly as a shared quantum execution (the tree root) and progressively branches into distinct paths only as the tasks’ executions diverge, with dissimilar tasks branching earlier and similar ones staying grouped until near convergence, reaching independent leaves where each task converges to its own solution. It is implemented as a VQA wrapper that integrates with typical applications. The reported results — shot count reductions of 25.9 times on average and over 100 times for large-scale problems at the same target accuracy on scientific and combinatorial benchmarks, with benefits growing with problem size and precision — are from the paper’s evaluation. Background on VQAs, shots, iterations, Hamiltonians and Pauli terms, ground-state energy, and near-term (pre-fault-tolerant) quantum computing is standard context. The step-by-step walkthrough follows the paper’s eight-task example but is an illustration, not a verbatim trace. Exact branching criteria, the representative-execution mechanism, and full results should be read from the paper.

Background

Why near-term quantum computing keeps hunting for redundancy to exploit

It helps to see TreeVQA within the broader effort to make near-term, noisy quantum computers do useful work despite their severe limits. Today’s quantum hardware has few qubits, high error rates, and no full error correction, and quantum-computer time is scarce and expensive, so essentially every advance in this era is about squeezing more useful computation out of very constrained, costly resources. Variational algorithms are the flagship near-term approach precisely because they tolerate noise, but they pay for that with punishing execution costs, and a large body of systems work has grown up around making them cheaper — better initialization, smarter measurement grouping, noise-aware compilation, and cost-reducing scheduling. A recurring theme is to find and exploit structure that a naive execution wastes: symmetry, similarity, or shared substructure that lets the same result be reached with fewer runs. TreeVQA is a clean instance, spotting that the many tasks of a real application are a related family with overlapping solutions and organizing their execution to share the common work. This drive to make near-term quantum algorithms practical by wringing efficiency out of their expensive execution is the same terrain the work on efficient quantum circuit search for near-term devices (Elivagar) covered elsewhere on this site occupies, doing more within a tight quantum-resource budget. TreeVQA’s distinctive contribution is to lift the optimization from a single task to the whole application, turning cross-task similarity into order-of-magnitude shot savings.

If you remember only three things

1. A variational quantum algorithm solves a problem — such as finding a molecule's ground-state energy — by iteratively tuning a parameterized quantum circuit with a classical optimizer, and it is one of the best ways to get useful work from today's noisy, pre-fault-tolerant quantum hardware. But its execution cost is punishing, because three factors multiply: it takes thousands of optimizer iterations, each iteration runs many circuits (a Hamiltonian can have thousands of Pauli terms), and a real application comprises thousands of related tasks (for example, one molecule at thousands of geometries) whose collective ground states map its energy landscape. Together these drive the total number of circuit executions, each needing many measurement shots, into the billions — a show-stopper for practical use — and prior work either only trims a single task's cost or, in the case of error mitigation, adds shots.
2. TreeVQA's key observation is that the tasks within an application are highly similar: being small variations of one problem, their ground-state quantum states overlap substantially, so their optimization paths are largely shared, yet conventional execution solves each independently and re-walks nearly the same path thousands of times. TreeVQA instead structures execution as a tree. It begins by running all the tasks jointly as a single shared quantum execution at the root, doing the common early optimization once for everyone. As the tasks' quantum states diverge toward their individual solutions, it branches — dissimilar tasks splitting off earlier, similar tasks staying grouped until close to convergence — recursing until, at the leaves, each task executes independently and converges to its own precise answer. Sharing is greatest near the root and specialization is deferred to the leaves, and it is implemented as a wrapper around existing VQA applications.
3. The reframing is that an application's many tasks are not independent jobs but a related family with a shared history, so the right structure for computing their solutions is a tree that does the common work once and specializes late, branching exactly when the tasks' executions diverge. Because the tasks remain distinct and reach independent leaves, every one still converges to its own precise solution at the target accuracy. On scientific and combinatorial benchmarks, TreeVQA cuts shot counts by 25.9 times on average and by over 100 times for large-scale problems, with benefits growing as problems get bigger and demand more precision. The trade-offs: the savings depend on the tasks genuinely overlapping, the framework must decide when to branch and choose a faithful representative execution for each shared node, and it reduces shots rather than qubits, depth, or hardware noise.

Check yourself

Check your understanding

1. Why do variational quantum algorithms require an astronomical number of shots?
2. What redundancy does conventional per-task execution miss?
3. How does TreeVQA's tree-structured execution work?
4. What did TreeVQA achieve, and on what does its benefit depend?

Sources

The paper is “TreeVQA: A Tree-Structured Execution Framework for Shot Reduction in Variational Quantum Algorithms” by Yuewen Hou, Dhanvi Bharadwaj, and Gokul Subramanian Ravi (University of Michigan), published at ASPLOS 2026, DOI 10.1145/3779212.3790239. It is available on arXiv as 2512.12068, with code at github.com/isaachyw/TreeVQA.

This explainer is written from the paper’s full text (the authors’ arXiv copy). Variational quantum algorithms (VQAs) demand enormous shot counts because they are iterative, run many circuits per iteration (Hamiltonians with thousands of Pauli terms), and appear in applications comprising thousands of related tasks, driving executions into the billions. TreeVQA observes that these tasks are highly similar (their ground-state quantum states overlap) and executes them as a tree: all tasks begin as one shared quantum execution at the root, branching progressively as their executions diverge — dissimilar tasks earlier, similar tasks later — down to independent leaves where each converges to its own solution. It is implemented as a wrapper around typical VQA applications. On scientific and combinatorial benchmarks, the paper reports shot count reductions of 25.9 times on average and over 100 times for large-scale problems at the same target accuracy, with benefits growing with problem size and precision. Background on VQAs, shots, Hamiltonians, ground-state energy, and near-term quantum computing is standard context. The numbers are the paper’s own; exact mechanisms and full results should be confirmed in the paper.