QANTIS: A Hardware-Validated Quantum Platform for POMDP Planning and Multi-Target Data Association

Bayram Yüksel Eker; Suayb S. Arslan; Özgür Nazlı; Mustafa Serhat Demirgil; Furkan Deligöz

quant-phFeb 28, 2026

QANTIS: A Hardware-Validated Quantum Platform for POMDP Planning and Multi-Target Data Association

Authors: Bayram Yüksel Eker, Suayb S. Arslan, Özgür Nazlı, Mustafa Serhat Demirgil, Furkan Deligöz

Organizations: Neura Parse Ltd., London, United Kingdom · Department of Computer Engineering, Boğaziçi University, Istanbul, Turkey · İzmir Ekonomi Üniversitesi, İzmir, Turkey · Faculty of Engineering, University of Toronto, Toronto, Canada ·

Abstract

Autonomous navigation under uncertainty requires solving partially observable Markov decision processes (POMDPs) for planning and assigning sensor measurements to tracked targets--a task known as multi-target data association (MTDA). Both problems become computationally demanding at scale: belief conditioning costs $\mathcal{O}(P(e)^{-1})$ per node under rare evidence, while MTDA is NP-hard. Quantum amplitude amplification can quadratically reduce the belief-update query cost to $\mathcal{O}(P(e)^{-1/2})$ , while QUBO reformulations expose MTDA to quantum and quantum-inspired optimisation heuristics. We present QANTIS, a modular platform that integrates quantum belief update (Grover amplitude amplification and BIQAE), QUBO-based data association via FPC-QAOA, and composable error mitigation, and we report a 45-experiment hardware study on three IBM Heron backends. On hardware, a single Grover iterate applied to a Tiger belief oracle amplifies a rare observation probability from $0.179$ to $0.907$ ( $5.1\times$ ; ISA 18) while preserving the Bayesian posterior (Hellinger $0.0015$ ), increasing usable-shot yield from 1,463 to 7,429. We interpret this as a hardware validation of the quadratic query-complexity mechanism at $k=1$ with posterior preservation, rather than a wall-clock advantage claim. We further demonstrate, to our knowledge, the first closed-loop hybrid quantum-classical Tiger POMDP on superconducting hardware ( $T=8$ , max Hellinger below $0.015$ ), and empirically characterise NISQ feasibility boundaries: ZNE-based error mitigation is beneficial below ISA $\approx 100$ and harmful above ISA $\gtrsim 1{,}000$ ; FPC-QAOA is meaningful at $\leq 15$ QUBO variables (ISA $\lesssim 450$ ). These results characterise practical operating regimes on current superconducting hardware rather than wall-clock quantum advantage at today's problem scales.

Figures & tables

Symbol	Description	Symbol	Description
$S,A,\Omega$	State/action/observation spaces	$P(e)$	Evidence probability $P(o\|b,a)$
$T,O,R,\gamma$	Transition/obs/reward/discount	$\mathcal{B}$	Bayesian belief update operator
$b\in\Delta^{\|S\|-1}$	Belief state	$H$	Planning horizon
$N,M$	Track/measurement count	$x_{ij}\in\{0,1\}$	Assignment variable
$\bm{x}_{i}^{-},P_{i}^{-}$	Predicted state and covariance	$\lambda$	QUBO penalty coefficient
$d_{ij}^{2}$	Mahalanobis distance	$c_{ij}$	Association cost (NLL)

Table 1: Principal notation.

System	Q-Plan	Q-DA	HW	EM	CL
Aaronson (2014) [ 10 ]	✓	–	–	–	–
Stollenwerk et al. (2021) [ 18 ]	–	✓	✓	–	–
Cunha et al. (2025) [ 4 ]	✓	–	–	–	–
Ribeiro (2026) [ 23 ]	–	✓	✓	✓	–
TrackHHL (2026) [ 20 ]	–	✓	–	–	–
Marshall et al. (2026) [ 25 ]	–	✓	✓	–	–

Table 2: Positioning of QANTIS relative to prior and concurrent work. Q-Plan: quantum POMDP planning. Q-DA: quantum data association. HW: real quantum hardware experiment. EM: error mitigation. CL: closed-loop action selection.

Panel of Figure 1 — Figure 1: Quantum belief update circuit for a single POMDP step (schematic; register sizes $n_{s}{=}\lceil\log_{2}|S|\rceil$ , $n_{a}{=}\lceil\log_{2}|A|\rceil$ , $n_{o}{=}\lceil\log_{2}|\Omega|\rceil$ , $n_{r}{=}$ reward precision bits). Unitaries $U_{1}$ , $U_{2}$ , $U_{3}$ encode the transition, observation, and reward models respectively. Measuring the observation register and conditioning on outcome $o$ (via amplitude amplification) yields the updated belief in the $S_{t+1}$ register. See Appendix A for the full hardware qubit allocation.

$P(e)$	pomcp	QBRL root	Speedup
$10^{-2}$	$100$	$\approx 10$	$10\times$
$10^{-3}$	$1{,}000$	$\approx 32$	$31.6\times$
$10^{-4}$	$10{,}000$	$\approx 100$	$100\times$

Table 3: Per-belief-node query cost (theoretical, fault-tolerant regime; circuit queries

\propto P(e)^{-1/2}

require gate fidelities

\lesssim 10^{-6}

for large

k^{\star}

). Speedup is QBRL over pomcp . Hardware demonstration at

P(e){\approx}0.18

5.1\!\times

amplification at ISA 18 on ibm_marrakesh (Section 8.6 ).

$N$	$M$	$n_{\text{var}}$	ISA ( $p=3$ )	NISQ feasibility
2	3	11	$\sim$ 435	Validated
3	4	19	$\sim$ 640	Marginal ( $20.4\%$ at $p=1$ )
5	8	53	$>$ 2 000	Beyond current NISQ
10	15	175	$\gg$ 10 000	FTQC target

Table 4: Estimated qubit resources for MTDA QUBO instances. Gate-model ISA depths use

p=3

FPC-QAOA on Heron R2 heavy-hex routing. Our hardware experiments (Section 8.6 ) validate the

N=2,M=3

(

n=11

) instance.

Panel of Figure 2 — Figure 2: Modular architecture of the QANTIS platform. The three packages maintain a strict acyclic dependency hierarchy: quantum-pomdp and quantum-mht depend on quantum-common but have no cross-dependency. The backend abstraction layer in quantum-common dispatches to three quantum hardware/simulator backends.

Backend	Qubits	Topology	2Q error	Use Case	Status
IBM Heron R1 (ibm_torino)	133	Heavy-hex	${\sim}2.5{\times}10^{-3}$	QAOA, BIQAE	Validated
IBM Heron R2 (ibm_fez)	156	Heavy-hex	${\sim}1.5{\times}10^{-3}$	QAOA, BIQAE	Validated
IBM Heron R2 (ibm_marrakesh)	156	Heavy-hex	${\sim}1.5{\times}10^{-3}$	Tiger, E2E loop	Validated
D-Wave Advantage2 †	4 400+	Zephyr	N/A	Annealing	Companion study
IonQ Aria-2 †	25	All-to-all	${\sim}3{\times}10^{-3}$	Small circuits	Planned

Table 5: Quantum hardware backends supported by QANTIS. Validated entries confirmed with real hardware experiments in this work (45-experiment pilot, Section 8.6 ). † Not part of the hardware campaign of this work.

Planner	Cumulative Reward			Belief KL
pomcp	$18.3$	$\pm$	$12.7$	—
despot	$19.1$	$\pm$	$11.4$	—
pbvi	$17.6$	$\pm$	$13.2$	$0.000$
QBRL (sim.) †	$18.7$	$\pm$	$12.1$	$0.014$

Table 6: Tiger problem: mean cumulative reward (

\pm

std. dev.) over 100 episodes of 50 steps (Qiskit Aer simulation; seed 42). Horizon

H=5

. One-way ANOVA:

F(3,396){=}0.27

p{=}0.85

; all pairwise Welch

t

-tests

p>0.54

; Cohen

|d|<0.09

for all pairs. Tiger (

|S|{=}2

) is intentionally simple and does not discriminate among well-tuned planners—agreement of all methods is the expected result. Hardware-validated E2E QBRL results (

T{=}4

, ibm_marrakesh) are in Table 15 . †

Grid	pomcp	Exact Bayes (classical) / QBRL (sim.) †	Plan Time (ms)
$4\times 4$	$0.081\pm 0.024$	$0.043\pm 0.015$	$12.4$ / $34.7$
$6\times 6$	$0.127\pm 0.038$	$0.068\pm 0.021$	$41.3$ / $112.5$
$8\times 8$	$0.194\pm 0.052$	$0.091\pm 0.029$	$108.7$ / $347.2$

Table 7: GPS-denied navigation: Hellinger distance between belief and true posterior (lower is better) and planning time. Mean

\pm

std. dev., 50 episodes, 30 steps. QBRL (Aer sim.) calls classical_update() internally; it is numerically equivalent to Exact Bayes (classical) under the same action-selection policy. pomcp uses an approximate particle filter (1 000 particles). The Hellinger improvement reflects exact vs. approximate belief update, not quantum vs. classical.

$N$	$M$	Vars	Build (ms)	Hungarian (ms)	GNN (ms)
2	3	11	$0.3$	$0.02$	$0.01$
3	5	23	$0.5$	$0.04$	$0.02$
5	8	53	$1.2$	$0.11$	$0.05$
8	12	116	$3.1$	$0.38$	$0.12$
10	15	175	$5.4$	$0.72$	$0.19$
15	23	383	$14.8$	$2.41$	$0.48$

Table 8: QUBO scaling with target count (

M=\lceil 1.5N\rceil

). Times in milliseconds (single-threaded Python, Intel i7-12700K).

Solver	Obj.	Gap to opt.	Feas. (%)	Time (ms)
Hungarian (optimal)	$34.2$	$0.0\%$	$100.0$	$0.72$
GNN	$41.7$	$+21.9\%$	$100.0$	$0.19$
QAOA ( $p\!=\!2$ )	$52.3$	$+52.9\%$	$68.0$	$2\,140$
FPC-QAOA ( $k\!=\!3$ , $p\!=\!8$ )	$38.9$	$\mathbf{+13.7\%}$	$89.0$	$4\,580$

Table 9: Solver comparison (

N=10

M=15

, 175 variables, Aer simulation). Objective lower is better; gap = % above Hungarian optimum. FPC-QAOA outperforms GNN at this scale; hardware feasibility at 175 variables requires fault-tolerant gate fidelities. Real-hardware results at the ISA-feasible 11-variable scale are in Table 15 .

Scenario	CT	MD	FA	$\bar{t}$ (ms)
Crossing ( $N\!=\!5$ )	$5/5$	$2$	$4$	$8.3$
Dense clutter ( $N\!=\!3$ )	$3/3$	$1$	$12$	$6.1$
Swarm patrol	$5/5$	$3$	$7$	$14.7$

Table 10: End-to-end tracking pipeline (30 steps; Hungarian solver; seed 42). CT = confirmed tracks at final step; MD/FA = events accumulated over 30 steps.

Panel of Figure 3 — Figure 3: Log-log scaling of solve and build times with target count $N$ (data from Table 8 ). The Hungarian algorithm exhibits the expected cubic scaling; the QUBO build time scales quadratically. GNN provides the fastest heuristic but yields suboptimal assignments. All measurements are from classical simulation (single-threaded Python, Intel i7-12700K).

$\|S\|$	State qubits	ISA depth	Circuit fidelity	Regime
2	1	12	$>0.98$	NISQ (confirmed)
4	2	162	$>0.78$	NISQ (confirmed)
8	3	${\sim}800^{\dagger}$	${\sim}0.30$	Marginal NISQ
16	4	${\sim}5{,}000^{\dagger}$	${\sim}10^{-4}$	FTQC required
64	6	${\sim}100{,}000^{\dagger}$	$\approx 0$	FTQC only

Table 11: Belief-update circuit ISA depth vs. state-space size on Heron R2. Confirmed values from hardware; projected values (

\dagger

) extrapolated from

O(|S|\cdot(\log_{2}|S|)^{2})

CNOT scaling. Heron R2 two-qubit error

{\sim}1.5{\times}10^{-3}

; circuit fidelity

{\approx}(1-\epsilon)^{\text{ISA}}

$N$	Variables	Hungarian (ms)	Frame rate	Real-time?
20	650	$5.9$	$170$ Hz	✓
50	4,100	$\sim\!92$	$11$ Hz	✓(slow UAV)
100	15,200	$\sim\!730$	$1.4$ Hz	$\times$
200	60,800	$\sim\!5{,}900$	$0.2$ Hz	$\times$
500	376,000	$\sim\!91{,}000$	$<\!0.1$ Hz	$\times$

Table 12: Hungarian solver runtime vs. target count (extrapolated from

N\!=\!20

M\!=\!30

measured at

5.87

ms; single-threaded Python, Intel i7-12700K;

M\!=\!\lceil 1.5N\rceil

). Real-time budget:

33

ms at 30 Hz.

True $a$	R1 (torino) $\|\hat{a}-a\|$	R2 (fez) $\|\hat{a}-a\|$	R2 (marrakesh) $\|\hat{a}-a\|$
0.10	0.346 / 0.008 §	—	0.006 §
0.20	0.144 / 0.002 §	0.140	—
0.30	0.040	0.039	—
0.40	0.006	—	—
0.50	0.008	0.0001	—
0.60	0.008	—	—

Table 13: BIQAE amplitude sweep on ibm_torino / ibm_fez / ibm_marrakesh . Uniform-prior runs: 6 iterations, 300 shots,

K_{t}=3^{t}

. All 95% credible intervals cover truth. § Prior-matched:

\text{prior\_mean}=a_{\text{true}}

\text{prior\_std}=0.05

, 10 iter., 500 shots. “—” denotes not tested on this backend.

Method	Wall-clock	Quality	Notes
Hungarian (optimal)	$<\!0.1$ ms	$100\%$	$\mathcal{O}(n^{3})$ exact
GNN (greedy)	$<\!0.1$ ms	$100\%$	$\mathcal{O}(NM\!\log NM)$ ; optimal at $N{=}2$
FPC-QAOA $p{=}3$ (Aer)	${\sim}5$ s	${\sim}91\%$	COBYLA convergence
FPC-QAOA $p{=}3$ (Heron R2)	${\sim}180$ s	$64.1\%{\pm}3.3\%$	ISA 433, 3 runs

Table 14: Classical vs. quantum solver on the

N{=}2

M{=}3

benchmark (Hungarian optimal

=-92.4

; full QUBO objective including false-alarm terms).

Experiment	Metric	Simulator	Hardware
Bell ZNE, 2 q (4096 shots)	$\langle ZZ\rangle$ $\uparrow$	1.000	0.938 raw / 0.953 ZNE
Tiger ZNE, 11 q (4096 shots)	Hellinger $\downarrow$	0.004	0.228 raw / 0.277 ZNE $\uparrow$
Tiger belief, 11 q (4096 shots)	Hellinger $\downarrow$	0.004	0.235
Tiger minimal, 2 q, obs $=0$ (8192 shots)	Hellinger $\downarrow$	0.005	0.025 ¶¶
Tiger minimal, 2 q, obs $=1$ (8192 shots)	Hellinger $\downarrow$	0.007	0.014 ¶¶
FPC-QAOA $p{=}1$ , 11 q (4096 shots)	ISA depth / hw obj	2 / $-47.4$	154 ¶ / $-33.0$

Table 15: Hardware pilot results on ibm_torino / ibm_fez / ibm_marrakesh (Heron R1/R2, 2026-02-25–26): forty-five experiments across four algorithm families (ZNE/error mitigation, BIQAE, FPC-QAOA, and quantum POMDP/E2E loop). FPC-QAOA hw obj decoded from top-10 bitstrings;

E_{\lambda}[f]

= avg QUBO expectation at scale

\lambda

; optimal Hungarian

=-92.4

Step	Prior $b_{t}$	Action	$a_{\text{true}}$	BIQAE HW est.	BIQAE err.	CI?	Tiger HW post.	Hellinger
$t=0$	$[0.500,0.500]$	listen	0.500	0.4945	0.0055	✓	$[0.846,0.154]$	0.0043
$t=1$	$[0.846,0.154]$	listen	0.154	0.1715	0.0171	✓	$[0.972,0.028]$	0.0066
$t=2$	$[0.972,0.028]$	open-right	0.028	0.0268	0.0012	✓	$[0.500,0.500]$	0.0003
$t=3$	$[0.500,0.500]$	listen	0.500	0.4964	0.0033	✓	$[0.867,0.133]$	0.0169

Table 16: End-to-end quantum POMDP closed loop with QBRL action selection: per-step hardware results on ibm_marrakesh (Heron R2, 2026-02-26, obs

=[0,0,0,0]

). BIQAE ISA depth 11; Tiger minimal ISA depth 12–13 (listen) or 4 (open-right at

t=2

). All four BIQAE credible intervals cover ground truth; max Hellinger

0.0169

(PASS). Three additional independent hardware replications of the same pipeline (different shot realisations) yield Tiger max Hellinger

0.0095

0.0141

0.0148

(all PASS), confirming stable operation.

Step	Obs	Action	$a_{\text{true}}$	BIQAE HW	Tiger HW post.	Hell.	ISA
$t{=}0$	0	listen	0.500	0.503	$[0.847,0.153]$	0.0031	12
$t{=}1$	0	listen	0.153	0.163	$[0.973,0.027]$	0.0091	13
$t{=}2$	0	open-right	0.027	0.029	$[0.518,0.482]$	0.0128	4
$t{=}3$	1	listen	0.482	0.479	$[0.175,0.825]$	0.0149	13
$t{=}4$	1	listen	0.825	0.824	$[0.043,0.957]$	0.0124	13
$t{=}5$	1	open-left	0.957	0.959	$[0.505,0.495]$	0.0036	4

Table 17:

T{=}8

end-to-end quantum POMDP closed loop on ibm_marrakesh (Heron R2, obs

=[0,0,0,1,1,1,0,0]

). Two action events at

t{=}2

(open-right) and

t{=}5

(open-left) trigger ISA 4 Hadamard-only circuits and near-exact belief resets. Max Hellinger

0.0149

(PASS). Single fixed-seed hardware trial; the observation sequence is chosen to elicit two symmetric action events and validate belief resets.

Metric	Heron R1 (ibm_torino)	Heron R2 (ibm_fez)
Bell $\langle ZZ\rangle$ raw	0.9424	0.9507
Bell $\langle ZZ\rangle$ ZNE	0.9580	0.9622
BIQAE $\|\hat{a}-a\|$ ( $a{=}0.50$ )	0.0045	0.0001
FPC-QAOA $p{=}2$ ISA depth	283	290
Tiger ISA depth	4 107	4 309
Tiger Hellinger (raw)	0.231	0.259

Table 18: Heron R1 (ibm_torino) vs. Heron R2 (ibm_fez) comparison (separate calibration run from Table 15 ). ZNE: scale

\{1,3,5\}

, 4 096 shots. BIQAE:

a=0.50

, 6 iter., 300 shots.

\uparrow

= ZNE counter-productive.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Register	Purpose	Tiger	Grid- $4{\times}4$	Grid- $8{\times}8$
		( $\|S\|\!=\!2$ )	( $\|S\|\!=\!16$ )	( $\|S\|\!=\!64$ )
$k_{1}$ : State ( $\|s\rangle$ )	Current state	1	4	6
$k_{2}$ : Next state ( $\|s^{\prime}\rangle$ )	Successor state	1	4	6
$k_{3}$ : Observation ( $\|o\rangle$ )	Observation	1	4	6
$k_{4}$ : Amplitude ( $\|p\rangle$ )	Probability amplitudes	4	6	8
$k_{5}$ : Action ( $\|a\rangle$ )	Selected action	2	3	3

Appendix

Table 19: Quantum register allocation for the belief update circuit.

n_{s}=\lceil\log_{2}|S|\rceil

state qubits,

n_{o}=\lceil\log_{2}|\Omega|\rceil

observation qubits,

n_{p}

amplitude precision bits.

$k$	$p$	Parameters ( $2k$ )	Objective	Feasibility (%)
2	4	4	$48.1$	$72.0$
2	8	4	$44.6$	$78.0$
3	4	6	$43.2$	$80.0$
3	8	6	$38.9$	$89.0$
3	16	6	$37.4$	$91.0$
4	8	8	$39.5$	$87.0$

Appendix

Table 20: FPC-QAOA sensitivity to parameter count

k

and circuit depth

p

. Objective value and feasibility rate are averaged over 50 independent runs. Schedule type: polynomial.

$G$	Hellinger ( $\downarrow$ )	KL Div. ( $\downarrow$ )	Amplified $P(e)$
0	$0.312$	$0.487$	$0.050$
1	$0.184$	$0.201$	$0.192$
2	$0.097$	$0.064$	$0.485$
3	$0.038$	$0.009$	$0.912$
4	$0.071$	$0.031$	$0.721$
5	$0.156$	$0.143$	$0.298$

Appendix

Table 21: Belief update accuracy vs. Grover iterations

G

for Grid-

4\times 4

(

|S|=16

P(e)=0.05

). Theoretical optimal

G^{*}=\lfloor\frac{\pi}{4}\sqrt{1/P(e)}\rfloor=3

. Hellinger distance and KL divergence to exact posterior, averaged over 200 belief updates.

Partially Observable Markov Decision Processes

Partially Observable Markov Decision Processes study sequential decisions when agents must act from incomplete, noisy observations of hidden states.

See all 88 papers

Jul 7, 2026

QANTIS: Hardware-Calibrated Sequential POMDP Belief Updates on IBM Heron

Autonomous systems under partial observability act on beliefs, not raw sensor events. QANTIS treats the quantum processor as a calibrated belief-update service in that loop: it receives a prior and an observation model, estimates the rare-event evidence term, and returns an ordinary posterior to a classical planner. This paper asks whether that service can be reused across a sequential Tiger POMDP horizon on present IBM Heron hardware without corrupting the planner-facing posterior. We answer with a controlled hardware case study rather than an end-to-end autonomy or wall-clock speedup claim. The study compares no amplification, guarded Grover amplification, and all-step fixed-point amplification on the same trajectory, then checks whether the returned posterior would change the downstream action. All-step FPAA preserves the Tiger posterior across the reported 8-step and 12-step primary runs, and the 20-step and 32-step controls remain inside the same operating band. In every reported decision check, the hardware posterior and the exact Bayes posterior select the same immediate action. Boundary-aware BIQAE stabilizes amplitude estimation near zero and near one, while a rare-event sweep maps the logical sample-complexity envelope for one-in-a-million evidence. The result is an operating envelope for a hardware-calibrated belief-update primitive, not a standalone hardware-advantage claim.

Bayram Yuksel Eker, Suayb S. Arslan, Ozgur Nazli +2

Neura Parse Ltd. London, United Kingdom · Dept. of Computer Engineering Boğaziçi University Istanbul, Turkey · Dept. of Physics Izmir University of Economics Izmir, Turkey +2

Belief-Space Planning Bayesian Filtering Partially Observable Markov Decision Processes

Ask PDF

Jul 13, 2026

Fixed-Protocol Amortized MPS Tomography with Conformalized Predictive Uncertainty

Quantum state tomography is sample-starved, and the states one prepares live on a narrow, learnable manifold. A

k{=}0

prior-only control shows that on concentrated families a prior estimate is already near-optimal, so ``high fidelity at few measurements'' can be family memorization rather than tomography; genuine measurement-efficiency needs a model that conditions on the measurements and demonstrably uses them. On a shared matrix-product-state (MPS) core parameterization we study two routes. Approach~~A learns a generative prior over MPS cores with measurement-guided posterior inference (gold-standard-validated, but whose few-measurement accuracy the control shows is largely the prior). Approach~~B, our main proposal, is a fixed-protocol amortized MPS estimator trained once with a gauge-invariant fidelity loss; we deliberately do not rest it on a permutation-invariant set encoder (a plain MLP matches it). The decisive lever is the measurement design: motivated by the fact that local reduced density matrices determine a

χ

-MPS, conditioning on an informative local Pauli set rather than random strings turns a modest, memorization-prone estimator into a high-fidelity one (

\approx\!0.95

, up to

+0.59

over prior-only, decisively passing a shuffled-measurement control). A dropout ensemble, conformally recalibrated, gives

\approx\!90\%

-coverage intervals -- including for observables never measured, where a shot-based interval does not exist. Quality holds as the system grows (fidelity

0.90

n{=}10

, gain growing in

n

;

0.88

at bond dimension

χ{=}4

), the parameterization is polynomial (native contraction to

20

qubits), and we close the loop on IBM hardware (

5

states at

0.97

from hardware-measured Paulis).

Jian Xu, Delu Zeng, John Paisley +1

1RIKEN iTHEMS · 2RIKEN AIP · 3South China University of Technology +1

Quantum State Tomography Amortized Inference

Ask PDF

Sep 27, 2026

Quantum Monte Carlo Tree Search with Fixed Confidence

Recent advances in quantum computing are opening new opportunities for computationally intensive decision problems. This paper studies how quantum computing can improve Monte Carlo tree search (MCTS) in the fixed-confidence setting, where the goal is to identify a near-optimal move in a given game tree with high probability while minimizing query complexity. We first formulate MCTS under a quantum oracle model. We then develop a quantum MCTS algorithm (QMCTS) that combines threshold-based elimination on the search tree with quantum Monte Carlo estimation to reduce the cost of evaluating stochastic leaf values. We establish an instance-dependent lower bound on the query complexity and derive a corresponding upper bound for QMCTS. The lower-bound analysis introduces a new quantum phase-testing result that may also be useful beyond MCTS. We validate the theoretical results through simulation experiments and further demonstrate the feasibility of QMCTS on real quantum hardware.

Mingjie Hu, Jian-Qiang Hu, Enlu Zhou

School of Management, Fudan University · H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology

Monte Carlo Tree Search Best-Arm Identification

Ask PDF

Abstract

Partially Observable Markov Decision Processes

Explore similar work

QANTIS: Hardware-Calibrated Sequential POMDP Belief Updates on IBM Heron

Fixed-Protocol Amortized MPS Tomography with Conformalized Predictive Uncertainty

Quantum Monte Carlo Tree Search with Fixed Confidence