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

arXiv:1405.7381

On computation with 'probabilities' modulo k

Niel de Beaudrap

Published May 28, 2014• 8 citations
arXivHTMLPDF

Abstract

We propose a framework to study models of computation of indeterministic data, represented by abstract "distributions". In these distributions, probabilities are replaced by "amplitudes" drawn from a fixed semi-ring $S$, of which the non-negative reals, the complex numbers, finite fields $\mathbb F_{p^r}$, and cyclic rings $\mathbb Z_k$ are examples. Varying $S$ yields different models of computation, which we may investigate to better understand the (likely) difference in power between randomised and quantum computation. The "modal quantum states" of Schumacher and Westmoreland [arXiv:1010.2929] are examples of such distributions, for $S$ a finite field. For $S = \mathbb F_2$, Willcock and Sabry [arXiv:1102.3587] show that UNIQUE-SAT is solvable by polynomial-time uniform circuit families consisting of invertible gates. We characterize the decision problems solvable by polynomial uniform circuit families, using either invertible or "unitary" transformations over cyclic rings $S = \mathbb Z_k$, or (in the case that $k$ is a prime power) finite fields $S = \mathbb F_k$. In particular, for $k$ a prime power, these are precisely the problems in the class $\mathsf{Mod}_k\mathsf P$.

DOI
10.48550/arxiv.1405.7381

Related papers

On the Power of Quantum Computation

Daniel R. Simon

The quantum model of computation is a model, analogous to the probabilistic Turing machine (PTM), in which the normal laws of chance are replaced by those obeyed by particles on a quantum mechanical scale, rather than the rules familiar to us from the macroscopic world. We present here a problem of distinguishing between two fairly natural classes of functions, which can provably be solved exponentially faster in the quantum model than in the classical probabilistic one, when the function is given as an oracle drawn equiprobably from the uniform distribution on either class. We thus offer compelling evidence that the quantum model may have significantly more complexity theoretic power than the PTM. In fact, drawing on this work, Shor has recently developed remarkable new quantum polynomial-time algorithms for the discrete logarithm and integer factoring problems.

SIAM Journal on Computing•Oct 1, 1997•1,294 citations

Complexity of Sampling and Communication

Artur Riazanov

The unifying topic of this thesis is the relation of randomness to computation. We study two different facets of this: the hardness of sampling from probability distributions and the extent of usefulness of randomness in communication complexity. Hardness of Sampling. A circuit samples the distribution of its output on a uniformly random input. What distributions are samplable with small circuits? What about local circuits (NC0)? We make two contributions in this direction. The first is to show that sampling uniformly from the set of Hamming-weight-k n-bit string is hard for NC0-circuits (and even constant-width DNFs) as long as k=o(n). The second is to show that sampling a uniformly random permutation of [n] elements requires polylog(n) adaptive queries to a sequence of uniform input symbols from [n]---adaptive cell probes. These results refine our understanding of sampling by constant-depth de Morgan circuits (AC0). Randomness in Communication. The classical example separating deterministic and randomized communication is the Equality problem: Alice and Bob are to decide whether their n-bit inputs are equal. It requires transmitting n+1 in the deterministic model, but is solvable with a constant-cost protocol using public randomness. An active line of research found many non-trivial problems that are solvable with just constant-cost randomized communication [Harms-Wild-Zamaraev, STOC 2022; Hambardzumyan-Hatami-Hatami, Isr. J. Math.; Fang-Hambardzumyan-Harms-Hatami, STOC 2024; Fang-Göös-Harms-Hatami, STOC 2025]. All of those problems can be solved with polylog(n) queries to Equality oracle. Our first contribution is to exhibit a problem that is solvable with constant-cost randomized communication, but requires polynomially many calls to Equality oracle. This resolves an open problem in the survey [Hatami-Hatami, ACM SIGACT News]. Our second contribution is to investigate when the randomized communication complexity can be localized or condensed: for a matrix of randomized communication cost k, can we find its 2^k-by-2^k submatrix that retains communication cost at least linear in k$? In general this is impossible [Hambardzumyan-Hatami-Hatami, Discrete Appl. Math.]. We show, however, that in an important case it can be done: we condense randomized communication cost of sink-of-xor function---a recent counterexample to log-approximate-rank conjecture by [Chattopadhyay-Mande-Sherif, J. ACM], and thereby quantitatively improve the counterexample.

•Jan 1, 2026•0 citations

Solving UNIQUE-SAT in a Modal Quantum Theory

Jeremiah James Willcock, Amr Sabry

In recent work, Benjamin Schumacher and Michael D. Westmoreland investigate a version of quantum mechanics which they call modal quantum theory. This theory is obtained by instantiating the mathematical framework of Hilbert spaces with a finite field instead of the field of complex numbers. This instantiation collapses much the structure of actual quantum mechanics but retains several of its distinguishing characteristics including the notions of superposition, interference, and entanglement. Furthermore, modal quantum theory excludes local hidden variable models, has a no-cloning theorem, and can express natural counterparts of quantum information protocols such as superdense coding and teleportation. We show that the problem of UNIQUE-SAT --- which decides whether a given Boolean formula is unsatisfiable or has exactly one satisfying assignment --- is deterministically solvable in any modal quantum theory in constant time. The solution exploits the lack of orthogonality in modal quantum theories and is not directly applicable to actual quantum theory.

arXiv:1102.3587•Feb 17, 2011•2 citations

QUANTUM ALGORITHMS FOR GENERATING RANDOM SEQUENCES OF INTEGERS

Mario Rasetti, Giovanni Sburlati

We present two quantum algorithms which generate a random sequence of integers modula a given N ∈ ℕ in which the expected frequency distribution over the set ℤN is different from the uniform distribution.

International Journal of Modern Physics B•Jul 30, 2002•0 citations

Probability in quantum computation and quantum computational logics: a survey

María Luisa Dalla Chiara, Roberto Giuntini, Giuseppe Sergioli

Quantum computation and quantum computational logics give rise to some non-standard probability spaces that are interesting from a formal point of view. In this framework, events represent quantum pieces of information (qubits, quregisters, mixtures of quregisters), while operations on events are identified with quantum logic gates (which correspond to dynamic reversible quantum processes). We investigate the notion of Shi–Aharonov quantum computational algebra. This structure plays the role for quantum computation that is played by σ-complete Boolean algebras in classical probability theory.

Mathematical Structures in Computer Science•Mar 28, 2014•6 citations

Vistas of Algebraic Probability: Quantum Computation and Information

Antonio Falcó, Hermann G. Matthies

Kolmogorov's foundation of probability takes measure spaces, $σ$-algebras, and probability measures as basic objects. It is, however, widely recognized that this classical framework is inadequate for random phenomena involving quantum effects, and more generally for \emph{quantum-like} situations. A broader formulation is provided by an algebraic viewpoint: one starts from an algebra of random variables equipped with a distinguished linear functional -- the \emph{state} -- interpreted as expectation. In this sense, the approach can also be viewed as a modern reading of ideas already implicit in early probability (e.g., the Bernoullis), while its contemporary form has been developed and used extensively in quantum physics. The algebraic framework accommodates both classical and quantum-like behaviours, yet it remains underused in classical probability and uncertainty quantification, where it can nevertheless open new perspectives and clarify structural features. Although the language carries a physics flavor, the subject is purely probabilistic. The key distinction between classical and quantum-like behaviour is \emph{commutativity}: its failure produces the characteristic effects of quantum-like situations. The rise of quantum computing is a prominent setting in which such behaviour may become relevant even for practitioners in computational science. Here we focus on the purely algebraic core of the approach. By restricting attention to finite-dimensional algebras, we avoid many analytical subtleties while retaining the main ideas, their classical limit, and their applicability to quantum-like models and quantum computation.

quant-pharXiv:2602.04351•Feb 5, 2026•0 citations
We propose a framework to study models of computation of indeterministic data, represented by abstract "distributions". In these distributions, probabilities are replaced by "amplitudes" drawn from a fixed semi-ring SSS, of which the non-negative reals, the complex numbers, finite fields Fpr\mathbb F_{p^r}Fpr​, and cyclic rings Zk\mathbb Z_kZk​ are examples. Varying SSS yields different models of computation, which we may investigate to better understand the (likely) difference in power between randomised and quantum computation. The "modal quantum states" of Schumacher and Westmoreland [arXiv:1010.2929] are examples of such distributions, for SSS a finite field. For S=F2S = \mathbb F_2S=F2​, Willcock and Sabry [arXiv:1102.3587] show that UNIQUE-SAT is solvable by polynomial-time uniform circuit families consisting of invertible gates. We characterize the decision problems solvable by polynomial uniform circuit families, using either invertible or "unitary" transformations over cyclic rings S=ZkS = \mathbb Z_kS=Zk​, or (in the case that kkk is a prime power) finite fields S=FkS = \mathbb F_kS=Fk​. In particular, for kkk a prime power, these are precisely the problems in the class ModkP\mathsf{Mod}_k\mathsf PModk​P.
The quantum model of computation is a model, analogous to the probabilistic Turing machine (PTM), in which the normal laws of chance are replaced by those obeyed by particles on a quantum mechanical scale, rather than the rules familiar to us from the macroscopic world. We present here a problem of distinguishing between two fairly natural classes of functions, which can provably be solved exponentially faster in the quantum model than in the classical probabilistic one, when the function is given as an oracle drawn equiprobably from the uniform distribution on either class. We thus offer compelling evidence that the quantum model may have significantly more complexity theoretic power than the PTM. In fact, drawing on this work, Shor has recently developed remarkable new quantum polynomial-time algorithms for the discrete logarithm and integer factoring problems.
The unifying topic of this thesis is the relation of randomness to computation. We study two different facets of this: the hardness of sampling from probability distributions and the extent of usefulness of randomness in communication complexity. Hardness of Sampling. A circuit samples the distribution of its output on a uniformly random input. What distributions are samplable with small circuits? What about local circuits (NC0)? We make two contributions in this direction. The first is to show that sampling uniformly from the set of Hamming-weight-k n-bit string is hard for NC0-circuits (and even constant-width DNFs) as long as k=o(n). The second is to show that sampling a uniformly random permutation of [n] elements requires polylog(n) adaptive queries to a sequence of uniform input symbols from [n]---adaptive cell probes. These results refine our understanding of sampling by constant-depth de Morgan circuits (AC0). Randomness in Communication. The classical example separating deterministic and randomized communication is the Equality problem: Alice and Bob are to decide whether their n-bit inputs are equal. It requires transmitting n+1 in the deterministic model, but is solvable with a constant-cost protocol using public randomness. An active line of research found many non-trivial problems that are solvable with just constant-cost randomized communication [Harms-Wild-Zamaraev, STOC 2022; Hambardzumyan-Hatami-Hatami, Isr. J. Math.; Fang-Hambardzumyan-Harms-Hatami, STOC 2024; Fang-Göös-Harms-Hatami, STOC 2025]. All of those problems can be solved with polylog(n) queries to Equality oracle. Our first contribution is to exhibit a problem that is solvable with constant-cost randomized communication, but requires polynomially many calls to Equality oracle. This resolves an open problem in the survey [Hatami-Hatami, ACM SIGACT News]. Our second contribution is to investigate when the randomized communication complexity can be localized or condensed: for a matrix of randomized communication cost k, can we find its 2^k-by-2^k submatrix that retains communication cost at least linear in k$? In general this is impossible [Hambardzumyan-Hatami-Hatami, Discrete Appl. Math.]. We show, however, that in an important case it can be done: we condense randomized communication cost of sink-of-xor function---a recent counterexample to log-approximate-rank conjecture by [Chattopadhyay-Mande-Sherif, J. ACM], and thereby quantitatively improve the counterexample.
In recent work, Benjamin Schumacher and Michael D. Westmoreland investigate a version of quantum mechanics which they call modal quantum theory. This theory is obtained by instantiating the mathematical framework of Hilbert spaces with a finite field instead of the field of complex numbers. This instantiation collapses much the structure of actual quantum mechanics but retains several of its distinguishing characteristics including the notions of superposition, interference, and entanglement. Furthermore, modal quantum theory excludes local hidden variable models, has a no-cloning theorem, and can express natural counterparts of quantum information protocols such as superdense coding and teleportation. We show that the problem of UNIQUE-SAT --- which decides whether a given Boolean formula is unsatisfiable or has exactly one satisfying assignment --- is deterministically solvable in any modal quantum theory in constant time. The solution exploits the lack of orthogonality in modal quantum theories and is not directly applicable to actual quantum theory.
Quantum computation and quantum computational logics give rise to some non-standard probability spaces that are interesting from a formal point of view. In this framework, events represent quantum pieces of information (qubits, quregisters, mixtures of quregisters), while operations on events are identified with quantum logic gates (which correspond to dynamic reversible quantum processes). We investigate the notion of Shi–Aharonov quantum computational algebra. This structure plays the role for quantum computation that is played by σ-complete Boolean algebras in classical probability theory.
Kolmogorov's foundation of probability takes measure spaces, σσσ-algebras, and probability measures as basic objects. It is, however, widely recognized that this classical framework is inadequate for random phenomena involving quantum effects, and more generally for \emph{quantum-like} situations. A broader formulation is provided by an algebraic viewpoint: one starts from an algebra of random variables equipped with a distinguished linear functional -- the \emph{state} -- interpreted as expectation. In this sense, the approach can also be viewed as a modern reading of ideas already implicit in early probability (e.g., the Bernoullis), while its contemporary form has been developed and used extensively in quantum physics. The algebraic framework accommodates both classical and quantum-like behaviours, yet it remains underused in classical probability and uncertainty quantification, where it can nevertheless open new perspectives and clarify structural features. Although the language carries a physics flavor, the subject is purely probabilistic. The key distinction between classical and quantum-like behaviour is \emph{commutativity}: its failure produces the characteristic effects of quantum-like situations. The rise of quantum computing is a prominent setting in which such behaviour may become relevant even for practitioners in computational science. Here we focus on the purely algebraic core of the approach. By restricting attention to finite-dimensional algebras, we avoid many analytical subtleties while retaining the main ideas, their classical limit, and their applicability to quantum-like models and quantum computation.