Reinforcement learning has powered some of artificial intelligence’s most celebrated achievements, from mastering the ancient game of Go to sharpening the reasoning abilities of large language models. Yet one of its hardest problems has remained stubbornly classical: what happens when an agent must make good decisions in a world it cannot fully see? Now, a research team from Portugal has shown that quantum computers may offer a concrete helping hand in exactly this scenario. In a study published in the journal Quantum Machine Intelligence, researchers led by Gilberto Cunha, Alexandra Ramôa, André Sequeira, Michael de Oliveira, and Luís Barbosa, working across the High-Assurance Software Laboratory at INESC TEC, the University of Minho’s Department of Computer Science, and the International Iberian Nanotechnology Laboratory, introduce a hybrid quantum-classical algorithm that accelerates reinforcement learning in partially observable environments, and they back it with one of the most rigorous complexity analyses yet attempted in this field.
The heart of the difficulty lies in what computer scientists call partial observability. When a robot’s sensors are noisy, when visibility is limited, or when crucial information is simply hidden, an agent cannot directly observe the true state of its environment. Such problems are formalized as partially observable Markov decision processes, or POMDPs, and they are notoriously harder than their fully observable cousins. In fact, computing exact solutions to POMDPs is PSPACE-complete, a complexity class that places them among the most computationally demanding problems known. The classical trick for coping with uncertainty is to maintain a belief state, a probability distribution over all possible underlying states, updated each time the agent takes an action and receives an observation. Updating and reasoning with these beliefs is where the computational burden accumulates, and it is precisely this bottleneck that the Portuguese team targets.
Their approach rests on a well-established modeling framework known as dynamic decision networks. These are Bayesian networks, directed acyclic graphs whose nodes represent random variables and whose edges encode dependencies between them, extended to capture the flow of time and the influence of the agent’s actions. States, actions, observations, and rewards each become nodes in the network, and the conditional probability tables attached to those nodes encode the environment’s transition dynamics, its sensor model, and its reward structure. Once a POMDP is cast in this form, the fundamental operation of belief updating becomes a probabilistic inference problem. For the reward and observation distributions, classical direct sampling suffices, drawing samples from the network without rejection. But belief updates are different: they require conditioning on evidence, and the standard technique, rejection sampling, discards every sample that does not match the observed evidence. As the number of variables grows, the acceptance probability of such samples shrinks exponentially, making belief updating the dominant cost of any look-ahead planner.
This is where quantum mechanics enters the picture. The team’s algorithm, which they call Quantum Bayesian Reinforcement Learning, or QBRL, encodes the Bayesian network into the amplitudes of a quantum state using a sequence of uniformly controlled rotation gates, one for each node and each configuration of its parent variables. Measuring the resulting quantum state then amounts to sampling from the joint distribution the network represents. The crucial step follows: an evidence phase-flip operator marks the quantum states that match the desired observation, and the Grover diffusion operator, applied repeatedly through an amplitude amplification circuit, boosts the amplitude of the good subspace. After a number of iterations on the order of the inverse square root of the evidence probability, the acceptance probability is pushed toward certainty. The upshot is a quadratic speedup: where classical rejection sampling needs a number of operations scaling as the inverse of the evidence probability, the quantum routine scales as its inverse square root. If the acceptance probability becomes one hundred times smaller, classical cost grows a hundredfold while quantum cost grows only tenfold.
Crucially, the authors prove that this quantum belief update is mathematically equivalent to its classical counterpart. By constructing explicit quantum circuits for every component of the POMDP, operators encoding the belief state, the action, the transition dynamics, the sensor model, and the reward function, and by applying the amplitude amplification operator to the observation qubits, they show that the probability of measuring any given next state exactly reproduces the classical belief update rule. This equivalence means the quantum subroutine can be dropped into a standard look-ahead planner without altering the algorithm’s decision-making logic. The planner explores a tree of possible futures up to a horizon, backs up expected rewards from the leaves to the root, and selects the action with the highest value; only the engine producing the samples underneath has changed.
What distinguishes this work from much of the quantum machine learning literature is the care taken with honest accounting. Many claimed quantum speedups assume access to a black-box oracle whose cost is swept under the rug. Here the researchers explicitly specify the inference process and derive their complexity bounds by counting primitive quantum operations, under fault-tolerant hardware assumptions. Their analysis yields a clear picture of when the advantage survives. The quantum state-preparation circuit scales exponentially in the maximum number of parents of any node in the network, a quantity denoted M, while classical direct sampling scales only linearly. For sparse networks, where 2^M can be approximated by M, this overhead vanishes and the quadratic advantage dominates. For dense networks, or for fully observable environments where direct sampling suffices and no rejection is needed, the quantum approach offers nothing, and may even be exponentially slower.
The main theoretical results quantify the speedup as a ratio between two sums, one aggregating inverse evidence probabilities across the look-ahead tree and the other aggregating inverse square roots of the same quantities. Because the sum of square roots generally exceeds the square root of a sum, this ratio lies between one and its square-root bound: the quantum algorithm is guaranteed to be no worse than the classical one in complexity, and at best quadratically faster, with most realistic cases falling somewhere in between. The break-even condition is explicit: the quantum advantage survives only when the ratio of these aggregate costs is large enough to compensate the exponential penalty in the network’s maximum in-degree. This kind of transparency about where the speedup lives, and where it dies, is rare and valuable in a field often criticized for optimistic assumptions.
To test whether these abstract bounds translate into practical gains, the team ran numerical simulations on two classic benchmark problems. The first is the tiger problem, in which an agent faces two doors, one concealing a tiger and one a treasure; opening the tiger’s door costs a reward of minus ten, finding the treasure earns five, and listening, which carries a fifteen percent error rate, costs one. The second is a robot exploration task, in which a robot navigates four rooms arranged in a circle searching for a treasure room containing two levers with different success rates and different damage penalties. Each algorithm was run hundreds of times, and the comparison was performed under two complementary protocols: fixing the query budget to see which agent earns more reward for equal cost, and fixing the effective sample count to see which agent spends fewer resources for equal quality.
The results were revealing in their unevenness. In the tiger problem, where decision quality is exquisitely sensitive to the number of samples available for the belief update, the quantum-enhanced agent achieved a 94 percent improvement in cumulative reward after fifty time steps compared with its classical counterpart. In the robot problem, the improvement was a more modest 8 percent, because extra samples saturate in value beyond a certain point; once estimates are already good enough, more of them buy little. Conversely, when the metric was cost rather than reward, the robot problem showed the larger discrepancy in resources, since its larger sample counts amplified the multiplicative savings of the faster sampling routine. The authors stress that the magnitude of the advantage is problem-dependent, governed by the ratio of aggregate evidence costs and by how sensitive performance is to belief accuracy.
The practical implications point toward regimes where quantum assistance would matter most: situations in which decisions must be made quickly or with tightly limited computational resources, and environments in which the fidelity of the belief update directly determines the quality of the chosen action. Real-world domains marked by noisy sensors and partial information, from autonomous robotics to industrial process control, fit this description. The authors are careful to note that their approach is not a general-purpose quantum solution to all partially observable reinforcement learning; it is a targeted acceleration of one subroutine, applicable when the environment’s dynamics form a sparse Bayesian network. They also situate their contribution relative to other strands of quantum reinforcement learning, including parameterized quantum circuit policies and methods granting agents quantum access to the environment, noting that their setting involves a classical environment and fault-tolerant, non-variational circuits.
Looking ahead, the researchers outline several directions for extending the work. Model-free approaches, in which the dynamic decision network itself must be learned from data, could combine with their algorithm to handle environments whose structure is unknown in advance. A fully quantum action-selection mechanism, encoding look-ahead paths as quantum states and expected rewards as amplitudes, could push the speedup beyond the belief update itself. And, inevitably, the decisive test will come from deployment on real quantum hardware rather than simulation, something that becomes increasingly feasible as fault-tolerant devices scale up. For now, the study stands as a disciplined demonstration that a known quantum speedup in probabilistic inference can propagate, under carefully mapped conditions, into faster and better sequential decision-making, and it offers the community both a reproducible codebase and a candid map of where quantum advantage begins and ends.
Subject of Research: Hybrid quantum-classical reinforcement learning in partially observable environments, using quantum rejection sampling and amplitude amplification to accelerate belief updates in sparse dynamic decision Bayesian networks.
Subject of Research: Technology and Engineering
Article Title: Quantum Bayesian networks can speed up reinforcement learning in partially observable environments
Article References: Cunha, G., Ramôa, A., Sequeira, A., de Oliveira, M., & Barbosa, L. (2026). Quantum Bayesian networks can speed up reinforcement learning in partially observable environments. Quantum Machine Intelligence, 8(2), Article 65. https://doi.org/10.1007/s42484-026-00401-9
Image Credits: AI Generated
DOI: 10.1007/s42484-026-00401-9
Keywords: reinforcement learning, partially observable Markov decision process, Bayesian networks, quantum algorithms, quantum amplitude amplification, quantum rejection sampling, dynamic decision networks, belief updating, hybrid quantum-classical algorithm, quantum machine learning
Cite Scienmag News
APA
MLA
Chicago
Katie Riggs. (September 10, 2026). Quantum Bayesian networks boost reinforcement learning in partially observable settings. Scienmag. https://scienmag.com/quantum-bayesian-networks-boost-reinforcement-learning-in-partially-observable-settings/
Katie Riggs. “Quantum Bayesian networks boost reinforcement learning in partially observable settings.” Scienmag, 10 September 2026, https://scienmag.com/quantum-bayesian-networks-boost-reinforcement-learning-in-partially-observable-settings/. Accessed 10 September 2026.
Katie Riggs. “Quantum Bayesian networks boost reinforcement learning in partially observable settings.” Scienmag. September 10, 2026. https://scienmag.com/quantum-bayesian-networks-boost-reinforcement-learning-in-partially-observable-settings/
Copy citation
Download RIS
Tags: AI in limited visibility scenariosAI in partially observable Markov decision processesapplications of quantum neural networkscomplex environment modelingcomplexity analysis of quantum algorithmscomplexity analysis of quantum reinforcement learningdecision-making under uncertaintyHybrid quantum-classical algorithmsnanotechnology in AI researchnoisy sensor data in AIpartially observable environmentspartially observable Markov decision processesQuantum Bayesian networksquantum computing for AIquantum computing in AIquantum machine intelligencequantum-enhanced machine learningquantum-enhanced reasoning in artificial intelligencereinforcement learningreinforcement learning in partially observable environments
