Quantum Nondeterministic Computation

Tarsem S. Purewal

Yangjia Li, Nengkun Yu, Mingsheng Ying

Aida Gainutdinova

In this paper we investigate ordered binary decision diagrams (OBDD) – a model for computing Boolean functions. The aim of this work is a comparative complexity analysis of quantum and classical nondeterministic OBDDs of large width. We study the complexity of computing the Boolean function "Equality" in nondeterministic quantum OBDDs for different order of reading variables in comparison with the classical complexity. We show that when using the order of reading for which the width of the classical nondeterministic OBDD is constant, the width of the quantum model is linear and the proved lower bound is tight. We define a Boolean function for which the width of nondeterministic quantum OBDD is exponential for any order of reading variables. We construct a quantum algorithm for computing this function with zero error. We present a result on the relationship between complexity classes for quantum and classical nondeterministic OBDDs of large width.

Stanley Gudder

Csaba Czabán, Zoltán Kolarovszki, Márton Karácsony +1 more

Photonic quantum computing has recently emerged as a promising candidate for fault-tolerant quantum computing by photonic qubits. These protocols make use of nondeterministic gates, enabling universal quantum computation. However, the suggested solutions heavily use particle number resolving detectors (PNRDs), which are experimentally hard to realize and are usually biased in practice. We investigate the possibility of suppressing such errors caused by such photodetector imperfections by adjusting the optimal beamsplitter and phaseshifter angles in the interferometer corresponding to nondeterministic gates. Moreover, we devise an optimization method for determining the adjusted angles, which may achieve higher output state fidelities while controlling the success probabilities of the nondeterministic gates.