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

Theory of Quantum Computing and its Analog of the Haltingproblem. Extensions of Logic to Nondeterminism, Decidability,And Nonexistence

Andrii Hopanchuk

Published Jan 1, 2025• 0 citations
Publisher
DOI
10.2139/ssrn.5119716

Related papers

Control Implemented on Quantum Computers: Effects of Noise, Nondeterminism, and Entanglement

Kip Nieman, Keshav Kasturi Rangan, Helen Durand

Quantum computing has advanced in recent years to the point that there are now some quantum computers and quantum simulators available to the public for use. In addition, quantum computing is beginning to receive attention within the process systems engineering community for directions such as machine learning and optimization. A logical next step for its evaluation within process systems engineering is for control, specifically for computing control actions to be applied to process systems. In this work, we provide some initial studies regarding the implementation of control on quantum computers, including the implementation of a single-input/single-output proportional control law on a quantum simulator with noise, evaluation of potential impacts of nondeterminism on theory for advanced control laws, and discussion of consequences of the way that entanglement works for next-generation manufacturing communication objectives.

Industrial & Engineering Chemistry Research•Jul 11, 2022•14 citations

Theory of Quantum Computing and its Analog of the Halting Problem

Andrii Hopanchuk

•Jan 1, 2025•0 citations

Applications of Mathematics and Logics in Quantum Computing

Shambhavi Awasthi, Shikhar Singh

Algorithms for intelligent systems•Jan 1, 2026•0 citations

Quantum Randomness and Nondeterminism

Emanuel H. Knill

Does the notion of a quantum randomized or nondeterministic algorithm make sense, and if so, does quantum randomness or nondeterminism add power? Although reasonable quantum random sources do not add computational power, the discussion of quantum randomness naturally leads to several definitions of the complexity of quantum states. Unlike classical string complexity, both deterministic and nondeterministic quantum state complexities are interesting. A notion of \emph{total quantum nondeterminism} is introduced for decision problems. This notion may be a proper extension of classical nondeterminism.

arXiv:quant-ph/9610012•Oct 9, 1996•52 citations

Automata and Quantum Computing

Andris Ambainis, Abuzer Yakaryılmaz

Quantum computing is a new model of computation, based on quantum physics. Quantum computers can be exponentially faster than conventional computers for problems such as factoring. Besides full-scale quantum computers, more restricted models such as quantum versions of finite automata have been studied. In this paper, we survey various models of quantum finite automata and their properties. We also provide some open questions and new directions for researchers. Keywords: quantum finite automata, probabilistic finite automata, nondeterminism, bounded error, unbounded error, state complexity, decidability and undecidability, computational complexity

arXiv:1507.01988•Jul 7, 2015•16 citations

Quantum logic and quantum computation

Mladen Pavičić, Norman D. Megill

Elsevier eBooks•Jan 1, 2007•17 citations
Quantum computing has advanced in recent years to the point that there are now some quantum computers and quantum simulators available to the public for use. In addition, quantum computing is beginning to receive attention within the process systems engineering community for directions such as machine learning and optimization. A logical next step for its evaluation within process systems engineering is for control, specifically for computing control actions to be applied to process systems. In this work, we provide some initial studies regarding the implementation of control on quantum computers, including the implementation of a single-input/single-output proportional control law on a quantum simulator with noise, evaluation of potential impacts of nondeterminism on theory for advanced control laws, and discussion of consequences of the way that entanglement works for next-generation manufacturing communication objectives.
Does the notion of a quantum randomized or nondeterministic algorithm make sense, and if so, does quantum randomness or nondeterminism add power? Although reasonable quantum random sources do not add computational power, the discussion of quantum randomness naturally leads to several definitions of the complexity of quantum states. Unlike classical string complexity, both deterministic and nondeterministic quantum state complexities are interesting. A notion of \emph{total quantum nondeterminism} is introduced for decision problems. This notion may be a proper extension of classical nondeterminism.
Quantum computing is a new model of computation, based on quantum physics. Quantum computers can be exponentially faster than conventional computers for problems such as factoring. Besides full-scale quantum computers, more restricted models such as quantum versions of finite automata have been studied. In this paper, we survey various models of quantum finite automata and their properties. We also provide some open questions and new directions for researchers. Keywords: quantum finite automata, probabilistic finite automata, nondeterminism, bounded error, unbounded error, state complexity, decidability and undecidability, computational complexity