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• 9 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,368 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

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

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•5 citations

Exact discrete logarithms from a flagged polygonal transform

Myeongjin Kang

Assume the flagged polygonal-transform and exact-factoring interfaces specified in the paper. We construct a polynomial-time uniform quantum circuit family over one fixed finite gate set that computes discrete logarithms in prime fields with probability one and polynomial worst-case resources. For prime-order inputs, each verified Fourier-bin label has probability at least 1/(81q). Given its verified logarithm, that probability is computable exactly by a bounded number of lattice-point counts in dimension at most thirteen. Dyadic completion produces success probability exactly one quarter, followed by one exact amplification step. All sampled probabilities are dyadic; no input-dependent rotation or postselection is used.

•Oct 13, 2026•0 citations

Randomness in Quantum Computation

Juan Pablo Paz

In ordinary computers, it is sometimes useful to flip a coin. Non?deterministic algorithms (those programs that involve making such random choices at some steps) can be far more efficient in finding solutions to a variety of problems

Science•Dec 18, 2003•2 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.
Assume the flagged polygonal-transform and exact-factoring interfaces specified in the paper. We construct a polynomial-time uniform quantum circuit family over one fixed finite gate set that computes discrete logarithms in prime fields with probability one and polynomial worst-case resources. For prime-order inputs, each verified Fourier-bin label has probability at least 1/(81q). Given its verified logarithm, that probability is computable exactly by a bounded number of lattice-point counts in dimension at most thirteen. Dyadic completion produces success probability exactly one quarter, followed by one exact amplification step. All sampled probabilities are dyadic; no input-dependent rotation or postselection is used.