Late Breaking Results: A Game Theoretic Approach for Optimizing Quantum Error Budget Distribution Asif Akhtab Ronggon
Tasnuva Farheen
Louisiana State University Baton Rouge, Louisiana, USA [email protected]
Louisiana State University Baton Rouge, Louisiana, USA [email protected]
arXiv:2604.15603v1 [quant-ph] 17 Apr 2026
Abstract Current fault-tolerant quantum compilers allocate error budgets uniformly during resource estimation, causing suboptimal physical resource overhead. We optimize this allocation using a potential game formulation, where Nash Equilibrium yields a Pareto-optimal distribution across logical operations, T-state distillation, and rotation synthesis. An iterated best response (IBR) algorithm converges to this equilibrium through monotonic descent of the shared cost function. Evaluation across 433 MQT benchmarks demonstrates an average reduction of 30.22% in physical resource requirements relative to uniform baselines, with peak improvements of 97.81% for specific circuit instances. This establishes a game-theoretic foundation for strategic error budget optimization in fault-tolerant quantum design automation.
CCS Concepts • Theory of Computation → Algorithmic Game Theory; • Fault Tolerant Quantum Computing → Error Budget Distribution; • Resource Estimation → Nash Equilibrium.
Keywords Game theory, Nash equilibrium, fault-tolerant quantum computing, resource estimation, error budget optimization ACM Reference Format: Asif Akhtab Ronggon and Tasnuva Farheen. 2026. Late Breaking Results: A Game Theoretic Approach for Optimizing Quantum Error Budget Distribution. In . ACM, xxx, xx, xxx, 3 pages. https://doi.org/XXXXXXX.XXXXXXX Accepted at the Design Automation Conference (DAC), Late-Breaking Results Track.
1
Introduction
Resource estimation for fault-tolerant quantum computing[4] constitutes a critical bottleneck in the quantum design automation workflow, determining whether algorithms remain within the physical constraints of near-term hardware. As quantum applications scale beyond the noisy intermediate scale regime, the compilation process faces escalating demand to minimize space-time volume[7] Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. Conference’17, Washington, DC, USA © 2026 Copyright held by the owner/author(s). Publication rights licensed to ACM. ACM ISBN 978-x-xxxx-xxxx-x/YYYY/MM https://doi.org/XXXXXXX.XXXXXXX
while still meeting the strict error-correction thresholds that faulttolerant operation requires. To meet these requirements, the global error budget representing the maximum tolerable error rate must be distributed among logical operations, T-state distillation, and rotation synthesis[9]. Recent work has demonstrated that strategic non uniform allocation can significantly reduce hardware requirements compared to uniform baselines, employing supervised machine learning to predict optimized distributions from labeled training datasets [2]. While effective, this approach requires extensive data curation, suffers from black box opacity, and provides no convergence guarantees within the compilation flow[5, 8]. Moreover, the model’s accuracy depends entirely on the diversity of the training data risking unstable predictions for novel circuit topologies. In this paper, we propose error budget allocation using intrinsic game theoretic structure that provides direct analytical solution without training data. By formulating allocation as a common interest potential game, we establish that Nash Equilibrium corresponds to a Pareto optimal distribution where no component can unilaterally reduce resource cost without increasing total overhead. An IBR algorithm converges monotonically to this equilibrium, guaranteeing improvement at each step while eliminating training overhead. This analytical framework eliminates the data curation burden and provides deterministic convergence guarantees unavailable to learning based approaches. Evaluation across 433 MQT benchmark[10] circuits demonstrates 30.22% average resource reduction, nearly double the improvement of state of the art learning based methods, establishing a principled foundation for strategic error budget optimization in fault tolerant quantum design automation.
2
Game Formulation & Methodology
We formulate the error-budget allocation as a three-player commoninterest game G = (N, S, 𝐶). The players N = {𝐿,𝑇 , 𝑅} correspond to 𝐿, Logical error correction;𝑇 , T-state distillation; and 𝑅, Rotation synthesis. Each player 𝑖 ∈ N controls a budget fraction 𝑠𝑖 , with the strategy profile s = (𝑠𝐿 , 𝑠𝑇 , 𝑠𝑅 ) constrained to the 𝜀-interior of Í the 2-simplex S = {s ∈ R3+ | 𝑖 𝑠𝑖 = 1, 𝑠𝑖 ≥ 𝜀}, where 𝜀 > 0 ensures estimator feasibility. A resource oracle maps any allocation to physical qubits 𝑄 (s) and runtime 𝑅(s), yielding the shared cost function 𝐶 (s) = 𝑄 (s) 𝑤 𝑅(s) 1−𝑤 with weight 𝑤 ∈ (0, 1). Since all players minimize the identical objective, G is an exact potential game with potential Φ ≡ 𝐶; consequently, any profile minimizing 𝐶 constitutes a pure Nash equilibrium (NE)[3]. Figure 1 illustrates the compilation pipeline. The resource estimator computes physical qubit count 𝑄 and runtime 𝑅 from the error budget partition 𝜺; the allocator minimizes their space–time product 𝐶 = 𝑄 · 𝑅.
Conference’17, July 2017, Washington, DC, USA
Asif Akhtab Ronggon and Tasnuva Farheen
the 𝜀 -Nash threshold=10−6 , the minimum allocation= 0.005, and the cost weight= 𝑤 = 0.5, compared to a uniform baseline 1/3.
4 Figure 1: System architecture for resource optimization. The common-interest structure guarantees that every cost minimizing Nash equilibrium is Pareto optimal[6]. Identical objectives prevent any unilateral deviation that improves individual payoff without increasing the shared cost 𝐶 , ensuring global minimizer lies on Pareto frontier. Thus, convergence to a Nash equilibrium automatically satisfies Pareto efficiency without auxiliary constraints. We compute the equilibrium through IBR. For player 𝑖 facing s−𝑖 , the best response minimizes 𝐶 (𝑥𝑖 , s−𝑖 ) over 𝑥𝑖 ∈ [𝜀, 1 − 2𝜀]. When player 𝑖 deviates to allocation 𝑥𝑖 , the remaining budget 1 − 𝑥𝑖 is distributed among opponents 𝑗 and 𝑘 while preserving their fixed relative ratio 𝜌 = 𝑠 𝑗 /(𝑠 𝑗 + 𝑠𝑘 ). This univariate optimization is solved by Brent’s method [1]. Cycling through players yields a potential-decreasing sequence guaranteed to converge to a pure NE. To mitigate suboptimal local equilibria, we perform 𝐾 random restarts s (0) ∼ Dirichlet(1, 1, 1) and return the minimal-cost profile, as detailed in Algorithm 1. Algorithm 1 Game-Theoretic Error Budget Allocation via IBR Require: Cost oracle 𝐶 (·), budget allocation 𝜀, weight 𝑤, restarts 𝐾, max iterations 𝑇max , tolerance 𝛿 Ensure: Equilibrium allocation s★ ∈ Δ2 ⊲ Cost: 𝐶 (s) = 𝑄 (s) 𝑤 · 𝑅 (s) 1−𝑤 , 𝑄: physical qubits, 𝑅: runtime 1: s★ ← ( 31 , 31 , 31 ); 𝐶 ★ ← 𝐶 (s★ ) 2: for 𝑘 = 1, . . . , 𝐾 do 3: s (0) ∼ Dirichlet(1, 1, 1); clip to [𝜖, 1] and renormalise 4: for 𝑡 = 0, . . . ,𝑇max − 1 do 5: Δ←0 6: for 𝑖 ∈ {1, 2, 3} do ⊲ Cyclic best response 7: Fix ratio 𝜌 ← 𝑠 𝑗 /(𝑠 𝑗 + 𝑠𝑘 ) for opponents 𝑗, 𝑘 ≠ 𝑖 8: 𝑥𝑖★ ← arg min𝑥𝑖 ∈ [𝜖, 1−2𝜖 ] 𝐶 s(𝑥𝑖 , 𝜌 ) ⊲ Brent’s method 9: Update s (𝑡 ) from 𝑥𝑖★ and 𝜌; Δ ← max Δ, |𝐶 new − 𝐶 old | 10: end for 11: if Δ < 𝛿 then break ⊲ 𝜖-Nash condition 12: end if 13: end for 14: if 𝐶 (s (𝑡 ) ) < 𝐶 ★ then s★ ← s (𝑡 ) ; 𝐶 ★ ← 𝐶 (s (𝑡 ) ) 15: end if 16: end for 17: return s★
3
Experimental Setup
We evaluate our Nash equilibrium framework on 433 circuit instances from 31 circuit families in the MQT Bench suite [10], spanning state preparation, quantum algorithms, and arithmetic primitives. Circuits are transpiled using Qiskit 2.3.0 (optimization level=3) and characterized through the Azure Quantum Resource Estimator (𝜀 total = 0.1). The allocation of error budgets is formulated as a three-player game of common-interest solved through IBR with
Result
Table 1 establishes that equilibrium-based allocation achieves 1.94× improvement over state-of-the-art learning-based approach (30.22% versus 15.6% [2]), with peak reductions reaching 97.81% across an expanded benchmark suite of 433 circuits spanning 31 families. Table 1: Resource improvement over uniform budget allocation. Methodology
Samples
Average
Maximum
Forster et al. [2] This work
383 433
15.6% 30.22%
77.7% 97.81%
Figure 2 reveals significant heterogeneity in Overall Metric Improvement, defined as the space time volume computed as physical qubits multiplied by runtime, relative to the uniform distribution baseline, with gains strongly correlated with circuit architectural properties. Arithmetic primitives (e.g., ripple-carry adders) and state-preparation circuits (GHZ, W-state) exhibit right-skewed distributions with extensive upper tails approaching 100% improvement, whereas variational algorithms (QAOA, VQE) demonstrate tight variance around the mean. This dichotomy reflects structural asymmetries in error-budget sensitivity: circuits dominated by T-state distillation or high-depth logical operations present exploitable bottlenecks where aggressive redistribution yields disproportionate returns, while balanced workloads permit only marginal gains through uniform reallocation.
Figure 2: Resource metric improvements by circuit family. Critically, the game-theoretic framework captures these asymmetries without circuit-specific training or feature engineering. The monotonic convergence guarantee ensures robust performance even for outlier instances where uniform allocation incurs catastrophic overhead, establishing a principled foundation for resource optimization that generalizes across disparate circuit topologies.
5
Conclusion
In this work, we allocate error budgets using a natural game-theoretic formulation, achieving 30.22% average resource reduction while
Late Breaking Results: A Game Theoretic Approach for Optimizing Quantum Error Budget Distribution
providing convergence and Pareto optimality guarantees without requiring supervised learning overhead. The current methodology regarding fixed cost weighting and three-player structure presents opportunities for extension to heterogeneous architectures and additional error sources. Moreover, utilizing compiler optimization as a strategic interaction among competing resource offers a unifying framework applicable to gate scheduling, qubit mapping, and cross-layer co-design in fault-tolerant quantum systems.
References [1] Richard P Brent. 2013. Algorithms for minimization without derivatives. [2] Tobias Forster and Robert Wille. 2025. Improving Hardware Requirements for Fault-Tolerant Quantum Computing by Optimizing Error Budget Distributions.
Conference’17, July 2017, Washington, DC, USA
In 2025 IEEE International Conference on Quantum Computing and Engineering. [3] Charles A Holt and Alvin E Roth. 2004. The Nash equilibrium: A perspective. Proceedings of the National Academy of Sciences 101, 12 (2004), 3999–4002. [4] Katabarwa. 2024. Fault-tolerant quantum computing. PRX quantum (2024). [5] Sara Lumbreras and Pedro Ciller. 2025. Interpretable optimization: why and how we should explain optimization models. Applied Sciences 15, 10 (2025), 5732. [6] Dov Monderer. 1996. Potential games. Games and economic behavior (1996). [7] Andrew M Steane. 1998. Space, time, parallelism and noise requirements for reliable quantum computing. Fortschritte der Physik: Progress of Physics (1998). [8] Ruo-Yu Sun. 2020. Optimization for deep learning: An overview. Journal of the Operations Research Society of China 8, 2 (2020), 249–294. [9] van Dam. 2023. Using azure quantum resource estimator for assessing performance of fault tolerant quantum computation. In International Conference on High Performance Computing, Network, Storage, and Analysis. 1414–1419. [10] Robert Wille. 2023. MQT Bench: Benchmarking Software and Design Automation Tools. (2023). MQT Bench is available at https://www.cda.cit.tum.de/mqtbench/.