New Study Proposes Quantum Belief Function, Achieves Exponential Time Acceleration

The theory of belief functions, also referred to as evidence theory or Dempster–Shafer theory (DST), is a generalized scheme for expressing uncertainty. Unlike classical probability theory, DST uses a basic belief assignment (BBA) to enable some portion of the belief to remain “unassigned” to any of the candidate conclusions. DST can therefore express more uncertainty than traditional Bayesian distributions, making its application advantageous in research fields such as pattern recognition, multi-criteria decision-making, medical diagnosis, etc., where it is not always possible to get a complete probability distribution.

The exponential power explosion characteristics of DST however can add prohibitively high computational burdens when handling large amounts of elements on classical computer systems. To address this issue, a research team from the University of Electronic Science and Technology of China, Chinese Academy of Sciences, School of Education Shaanxi Normal University, Japan Advanced Institute of Science and Technology and ETH Zurich has proposed encoding the BBA into quantum states and implementing them on quantum circuits — a novel approach that aims to utilize the characteristics of quantum computation to more conveniently and effectively handle belief functions.

The team summarises their study’s contributions as:

1. BBA and belief function are encoded to quantum states called quantum basic belief assignment (QBBA) and quantum belief function, which provides qubits and elements with operational consistency.
2. According to QRAM (Giovannetti et al., 2008b), an algorithm for implementation QBBA is proposed, which proves that extraction QBBA in QRAM can be exponentially accelerated compared to classic computers in running time.
3. A method for implementing quantum belief functions is proposed and applied to the algorithm of plausibility transform method (Cobb and Shenoy, 2006), which also achieves exponential acceleration.
4. According to quantum fidelity (Nielsen and Chuang, 2002), a new method of inferring the similarity between BBAs called evidence fidelity is proposed and proven to achieve the same decision-making effect as the evidence distance (Jousselme et al., 2001) in classical methods.
5. The proposed evidence fidelity is expressed on quantum circuits based on the HHL algorithm (Harrow et al., 2009) and swap test (Buhrman, Cleve, Watrous and De Wolf, 2001), which can measure the similarity between QBBAs.

The overall goal of the study is to solve the power exponential explosion problem of Dempster-Shafer evidence theory (DSET) algorithms on classical computers. To this end, the team proposes QDSET and proves that its algorithms can be significantly accelerated on quantum computers.

The team first encodes the BBA to a quantum state, which allows qubits to directly control the corresponding elements’ mass functions. The researchers note that in classical computation, the order of mass function needs to be considered when dealing with BBA; whereas in quantum computation, the qubits operation is equivalent to directly changing the belief functions. The DSET thus has promising application prospects in quantum computation.

The researchers then propose an algorithm to extract QBBA based on QRAM, and show that even when the number of qubits is large, QBBA preparation can be exponentially accelerated in time.

The team also proposes evidence fidelity based on quantum fidelity and fractal-based matrices and validates that a fractal-based matrix achieves similar effects on the difference inference of BBAs with evidence distance. This discovery not only reduces the complexity in classical computation, but can also be implemented on quantum circuits. The study’s complexity analysis shows that quantum evidence fidelity can achieve exponential acceleration compared to classical methods.

The researchers believe their work can shed light on utilizing the characteristics of quantum computation to handle belief functions more conveniently and effectively.

The paper Quantum Belief Function is on arXiv.

---

Author: Hecate He | Editor: Michael Sarazen, Chain Zhang

---

We know you don’t want to miss any news or research breakthroughs. Subscribe to our popular newsletter Synced Global AI Weekly to get weekly AI updates.