Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics

Incomplete information and quantum decision trees

Subhash C. Kak

Published Oct 1, 2017• 2 citations
Publisher

Abstract

This paper considers the problem of the absent-minded driver who must choose between alternatives with different payoff under the conditions of imperfect recall and varying degrees of knowledge of the system. We show that agents with access to quantum resources, or with a quantum mechanical basis, can obtain superior performance as compared to classical agents. The paper also considers the problem of random tree representations of quantum decision processes. It is shown that in the general case where each node can have any branching probability value, a random tree can accurately represent the probabilities associated with an arbitrary quantum state.

DOI
10.1109/smc.2017.8122615

Related papers

Quantum Decision Theory

Adam M. Brandenburger, Pierfrancesco La Mura

We argue that, contrary to conventional wisdom, decision theory is not invariant to the physical environment in which a decision is made. Specifically, we show that a decision maker (DM) with access to quantum information resources may be able to do strictly better than a DM with access only to classical information resources. In this respect, our findings are somewhat akin to those in computer science that have established the superiority of quantum over classical algorithms for certain problems. We treat three kinds of decision tree: (i) Kuhn trees ([24, 1950], [25, 1953]) in which the DM has perfect recall; (ii) Kuhn trees in which the DM has imperfect recall; and (iii) non-Kuhn trees.

•Jul 1, 2011•2 citations

Quantum absentminded driver problem revisited

Piotr Frąckiewicz, Katarzyna Rycerz, M. Szopa

Abstract The aim of the paper is to study the problem of absentminded driver in the quantum domain. In the classical case, it is a well-known example of a decision problem with imperfect recall that exhibits lack of equivalence between mixed and behavioral strategies. The optimal payoff outcome is significantly lower than the maximum payoff appearing in the game. This raises the question whether a quantum approach to the problem can increase the strategic position of the decision maker. The results that we present in the paper clearly reveal the benefits from playing the absentminded problem with the aid of quantum objects. Through appropriately chosen initial quantum state, the unitary strategies enable the decision maker to obtain the maximum possible payoff. At the same time, our scheme comes down to the classical problem with a suitable restriction of unitary strategies.

Quantum Information Processing•Dec 31, 2021•2 citations

On Quantum Decision Trees

Subhash C. Kak

Quantum decision systems are being increasingly considered for use in artificial intelligence applications. Classical and quantum nodes can be distinguished based on certain correlations in their states. This paper investigates some properties of the states obtained in a decision tree structure. How these correlations may be mapped to the decision tree is considered. Classical tree representations and approximations to quantum states are provided.

arXiv:1703.03693•Mar 8, 2017•1 citation

Machine learning for decision-making under uncertainty

Lizhi Xin, Kevin Z. Xin, Houwen Xin

We live in a world brimming with uncertainty, where we constantly have to make a lot of decisions under incomplete information. We are firm believers that our subjective belief cannot be computed by rigorous mathematical formula; instead based on Darwin's natural selection (the evolution process is simulated by machine learning with genetic programming), a proposed computational model that incorporates insights from quantum theory to describe and explain decision-making under uncertainty. Unlike other decision-making theories that explain the decision-making process through probability theory, our proposed decision theory discovers "laws" of thought by learning observed historical data. There is no differential equation and no transition probability in our decision theory, our decision model has an emphasis on machine learning, where decision-makers build-up their experience by being rewarded or punished for each decision they make and prepare them for making better decisions in the future. We do not model with the usual utility function, but with quantum decision tree that simulates people's decision process. Each quantum decision tree includes a set of strategies; every time a decision is made, the decision-maker first chooses a strategy from the quantum decision tree's strategy pool, and then chooses an action based on the degree of belief which is obtained by genetic programming based on maximizing expected value.

arXiv:2212.04286•Dec 8, 2022•0 citations

Quantum computation and decision trees

Edward Farhi, Sam Gutmann

Many interesting computational problems can be reformulated in terms of decision trees. A natural classical algorithm is to then run a random walk on the tree, starting at the root, to see if the tree contains a node $n$ level from the root. We devise a quantum-mechanical algorithm that evolves a state, initially localized at the root, through the tree. We prove that if the classical strategy succeeds in reaching level $n$ in time polynomial in $n,$ then so does the quantum algorithm. Moreover, we find examples of trees for which the classical algorithm requires time exponential in $n,$ but for which the quantum algorithm succeeds in polynomial time. The examples we have so far, however, could also be solved in polynomial time by different classical algorithms.

arXiv:quant-ph/9706062•Physical Review A•Aug 1, 1998•1,232 citations

Imperfect-Information Games on Quantum Computers: A Case Study in Skat

Ulrich Armbrüster, Stefan Edelkamp, Gabriel Maresch +1 more

We demonstrate how quantum computing can provide a promising framework for addressing imperfect information games, using the popular German card game Skat as a case study. Our approach employs quantum registers to encode the game's hidden and public information, along with tailored quantum gates to model the game's progress while respecting its rules. To evaluate player decisions, we introduce a score operator that projects the quantum state onto the winning subspace, enabling the estimation of winning probabilities via quantum algorithms such as quantum counting. This allows the efficient exploration of alternative strategies and potential improvements in computational speed compared to classical methods. By maximizing the payoff function, our framework yields actionable recommendations for optimal play. As classical computation faces severe limitations due to the exponential complexity of the game tree, we discuss the specific structural properties of Skat that may give rise to a quantum advantage once the problem size surpasses classical feasibility.

arXiv:2411.15294•Adaptive Agents and Multi-Agents Systems•May 24, 2026•0 citations
This paper considers the problem of the absent-minded driver who must choose between alternatives with different payoff under the conditions of imperfect recall and varying degrees of knowledge of the system. We show that agents with access to quantum resources, or with a quantum mechanical basis, can obtain superior performance as compared to classical agents. The paper also considers the problem of random tree representations of quantum decision processes. It is shown that in the general case where each node can have any branching probability value, a random tree can accurately represent the probabilities associated with an arbitrary quantum state.
We argue that, contrary to conventional wisdom, decision theory is not invariant to the physical environment in which a decision is made. Specifically, we show that a decision maker (DM) with access to quantum information resources may be able to do strictly better than a DM with access only to classical information resources. In this respect, our findings are somewhat akin to those in computer science that have established the superiority of quantum over classical algorithms for certain problems. We treat three kinds of decision tree: (i) Kuhn trees ([24, 1950], [25, 1953]) in which the DM has perfect recall; (ii) Kuhn trees in which the DM has imperfect recall; and (iii) non-Kuhn trees.
Abstract The aim of the paper is to study the problem of absentminded driver in the quantum domain. In the classical case, it is a well-known example of a decision problem with imperfect recall that exhibits lack of equivalence between mixed and behavioral strategies. The optimal payoff outcome is significantly lower than the maximum payoff appearing in the game. This raises the question whether a quantum approach to the problem can increase the strategic position of the decision maker. The results that we present in the paper clearly reveal the benefits from playing the absentminded problem with the aid of quantum objects. Through appropriately chosen initial quantum state, the unitary strategies enable the decision maker to obtain the maximum possible payoff. At the same time, our scheme comes down to the classical problem with a suitable restriction of unitary strategies.
We live in a world brimming with uncertainty, where we constantly have to make a lot of decisions under incomplete information. We are firm believers that our subjective belief cannot be computed by rigorous mathematical formula; instead based on Darwin's natural selection (the evolution process is simulated by machine learning with genetic programming), a proposed computational model that incorporates insights from quantum theory to describe and explain decision-making under uncertainty. Unlike other decision-making theories that explain the decision-making process through probability theory, our proposed decision theory discovers "laws" of thought by learning observed historical data. There is no differential equation and no transition probability in our decision theory, our decision model has an emphasis on machine learning, where decision-makers build-up their experience by being rewarded or punished for each decision they make and prepare them for making better decisions in the future. We do not model with the usual utility function, but with quantum decision tree that simulates people's decision process. Each quantum decision tree includes a set of strategies; every time a decision is made, the decision-maker first chooses a strategy from the quantum decision tree's strategy pool, and then chooses an action based on the degree of belief which is obtained by genetic programming based on maximizing expected value.
Many interesting computational problems can be reformulated in terms of decision trees. A natural classical algorithm is to then run a random walk on the tree, starting at the root, to see if the tree contains a node nnn level from the root. We devise a quantum-mechanical algorithm that evolves a state, initially localized at the root, through the tree. We prove that if the classical strategy succeeds in reaching level nnn in time polynomial in n,n,n, then so does the quantum algorithm. Moreover, we find examples of trees for which the classical algorithm requires time exponential in n,n,n, but for which the quantum algorithm succeeds in polynomial time. The examples we have so far, however, could also be solved in polynomial time by different classical algorithms.
We demonstrate how quantum computing can provide a promising framework for addressing imperfect information games, using the popular German card game Skat as a case study. Our approach employs quantum registers to encode the game's hidden and public information, along with tailored quantum gates to model the game's progress while respecting its rules. To evaluate player decisions, we introduce a score operator that projects the quantum state onto the winning subspace, enabling the estimation of winning probabilities via quantum algorithms such as quantum counting. This allows the efficient exploration of alternative strategies and potential improvements in computational speed compared to classical methods. By maximizing the payoff function, our framework yields actionable recommendations for optimal play. As classical computation faces severe limitations due to the exponential complexity of the game tree, we discuss the specific structural properties of Skat that may give rise to a quantum advantage once the problem size surpasses classical feasibility.