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

ACM Symposium on Theory of Computing (STOC)

The computational complexity of ball permutations

Scott Aaronson, Adam Bouland, Greg Kuperberg, Saeed Adel Mehraban

Published Jun 15, 2017• 16 citations
Publisher

Abstract

We define several models of computation based on permuting distinguishable particles (which we call balls) and characterize their computational complexity. In the quantum setting, we use the representation theory of the symmetric group to find variants of this model which are intermediate between BPP and DQC1 (the class of problems solvable with one clean qubit) and between DQC1 and BQP. Furthermore, we consider a restricted version of this model based on an exactly solvable scattering problem of particles moving on a line. Despite the simplicity of this model from the perspective of mathematical physics, we show that if we allow intermediate destructive measurements and specific input states, then the model cannot be efficiently simulated classically up to multiplicative error unless the polynomial hierarchy collapses. Finally, we define a classical version of this model in which one can probabilistically permute balls. We find this yields a complexity class which is intermediate between L and BPP, and that a nondeterministic version of this model is NP-complete.

DOI
10.1145/3055399.3055453

Related papers

The Computational Complexity of Ball Permutations

Scott Aaronson, Adam Bouland, Greg Kuperberg +1 more

Inspired by connections to two dimensional quantum theory, we define several models of computation based on permuting distinguishable particles (which we call balls), and characterize their computational complexity. In the quantum setting, we find that the computational power of this model depends on the initial input states. More precisely, with a standard basis input state, we show how to approximate the amplitudes of this model within additive error using the model DQC1 (the class of problems solvable with one clean qubit), providing evidence that the model in this case is weaker than universal quantum computing. However, for specific choices of input states, the model is shown to be universal for BQP in an encoded sense. We use representation theory of the symmetric group to partially classify the computational complexity of this model for arbitrary input states. Interestingly, we find some input states which yield a model intermediate between DQC1 and BQP. Furthermore, we consider a restricted version of this model based on an integrable scattering problem in 1+1 dimensions. We show it is universal under postselection, if we allow intermediate destructive measurements and specific input states. Therefore, the existence of any classical procedure to sample from the output distribution of this model within multiplicative error implies collapse of polynomial hierarchy to its third level. Finally, we define a classical version of this model in which one can probabilistically permute balls. We find this yields a complexity class which is intermediate between L and BPP. Moreover, we find a nondeterministic version of this model is NP-complete.

arXiv:1610.06646•Oct 21, 2016•8 citations

Permutational quantum computing

Stephen P. Jordan

In topological quantum computation the geometric details of a particle trajectory are irrelevant; only the topology matters. Taking this one step further, we consider a model of computation that disregards even the topology of the particle trajectory, and computes by permuting particles. Whereas topological quantum computation requires anyons, permutational quantum computation can be performed with ordinary spin-1/2 particles, using a variant of the spin-network scheme of Marzuoli and Rasetti. We do not know whether permutational computation is universal. It may represent a new complexity class within BQP. Nevertheless, permutational quantum computers can in polynomial time approximate matrix elements of certain irreducible representations of the symmetric group and approximate certain transition amplitudes from the Ponzano-Regge spin foam model of quantum gravity. No polynomial time classical algorithms for these problems are known.

arXiv:0906.2508•Quantum Information and Computation•May 1, 2010•61 citations

Computational Complexity of Some Quantum Theories in $1+1$ Dimensions

Saeed Adel Mehraban

We study the computational complexity of certain integrable quantum theories in 1+1 dimensions. We formalize a model of quantum computation based on these theories. In this model, distinguishable particles start out with known momenta and initial superposition of different configurations. Then the label of these particles are measured at the end. We prove that additive approximation to single amplitudes of these models can be obtained by the one-clean-qubit model, if no initial superpositions are allowed. However, if arbitrary initial states and non-adaptive intermediate measurements are allowed, we show that conditioned on infinite polynomial hierarchy assumption it is hard to sample from the output distribution of these models on a classical randomized computer. A classical analogue of this model is also formalized and its computational power is pinned down within the complexity classes below BPP and NP.

arXiv:1512.09243•Dec 31, 2015•4 citations

Quantum complexity theory

Ethan Bernstein, Umesh V. Vazirani

Abstract. In this paper we study quantum computation from a complexity theoretic viewpoint. Our rst result is the existence of an ecient universal quantum Turing machine in Deutsch’s model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97{117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specied. We prove that O(log T) bits of precision suce to support a T step computation. This justies the claim that the quantum Turing machine model should be regarded as a discrete model of computation and not an analog one. We give the rst formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church{Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class BPP. The class BQP of languages that are eciently decidable (with small error-probability) on a quantum Turing machine satises BPP ⊆ BQP ⊆ P]P. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.

ACM Symposium on Theory of Computing (STOC)•Jan 1, 1993•1,413 citations

The complexity of parameters for probabilistic and quantum computation

Josef Michael Breutzmann

In this dissertation we study some effects of allowing computational models that use parameters whose own computational complexity has a strong effect on the computational complexity of the languages computable from the model. We show that in the probabilistic and quantum models there are parameter sets that allow one to obtain noncomputable outcomes;In Chapter 3 we define BP[beta]P the BPP class based on a coin with bias [beta]. We then show that if [beta] is BPP-computable then it is the case that BP[beta]P = BPP. We also show that each language L in P/CLog is in BP[beta]P for some [beta]. Hence there are some [beta] from which we can compute noncomputable languages. We also examine the robustness of the class BPP with respect to small variations from fairness in the coin;In Chapter 4 we consider measures that are based on polynomial-time computable sequences of biased coins in which the biases are bounded away from both zero and one (strongly positive P-sequences). We show that such a sequence [vector][beta] generates a measure [mu][vector][beta] equivalent to the uniform measure in the sense that if C is a class of languages closed under positive, polynomial-time, truth-table reductions with queries of linear length then C has [mu][vector][beta]-measure zero if and only if it has measure zero relative to the uniform measure [mu]. The classes P, NP, BPP, P/Poly, PH, and PSPACE are among those to which this result applies. Thus the measures of these much-studied classes are robust with respect to changes of this type in the underlying probability measure;In Chapter 5 we introduce the quantum computation model and the quantum complexity class BQP. We claim that the computational complexity of the amplitudes is a critical factor in determining the languages computable using the quantum model. Using results from chapter 3 we show that the quantum model can also compute noncomputable languages from some amplitude sets. Finally, we determine a restriction on the amplitude set to limit the model to the range of languages implicit in others' typical meaning of the class BQP.

•Jan 1, 1996•0 citations

Hardness of Classically Simulating the One-Clean-Qubit Model

Tomoyuki Morimae, Keisuke Fujii, Joseph F. Fitzsimons

Deterministic quantum computation with one quantum bit (DQC1) [E. Knill and R. Laflamme, Phys. Rev. Lett. 81, 5672 (1998)] is a model of quantum computing where the input is restricted to containing a single qubit in a pure state and has all other qubits in a completely mixed state. Only the single pure qubit is measured at the end of the computation. While it is known that DQC1 can efficiently solve several problems for which no known classical efficient algorithms exist, the question of whether DQC1 is really more powerful than classical computation remains open. In this Letter, we introduce a slightly modified version of DQC1, which we call DQC1(k), where k output qubits are measured, and show that DQC1(k) cannot be classically efficiently simulated for any k≥3 unless the polynomial hierarchy collapses at the third level.

arXiv:1312.2496•Physical Review Letters•Apr 2, 2014•108 citations
We define several models of computation based on permuting distinguishable particles (which we call balls) and characterize their computational complexity. In the quantum setting, we use the representation theory of the symmetric group to find variants of this model which are intermediate between BPP and DQC1 (the class of problems solvable with one clean qubit) and between DQC1 and BQP. Furthermore, we consider a restricted version of this model based on an exactly solvable scattering problem of particles moving on a line. Despite the simplicity of this model from the perspective of mathematical physics, we show that if we allow intermediate destructive measurements and specific input states, then the model cannot be efficiently simulated classically up to multiplicative error unless the polynomial hierarchy collapses. Finally, we define a classical version of this model in which one can probabilistically permute balls. We find this yields a complexity class which is intermediate between L and BPP, and that a nondeterministic version of this model is NP-complete.
Inspired by connections to two dimensional quantum theory, we define several models of computation based on permuting distinguishable particles (which we call balls), and characterize their computational complexity. In the quantum setting, we find that the computational power of this model depends on the initial input states. More precisely, with a standard basis input state, we show how to approximate the amplitudes of this model within additive error using the model DQC1 (the class of problems solvable with one clean qubit), providing evidence that the model in this case is weaker than universal quantum computing. However, for specific choices of input states, the model is shown to be universal for BQP in an encoded sense. We use representation theory of the symmetric group to partially classify the computational complexity of this model for arbitrary input states. Interestingly, we find some input states which yield a model intermediate between DQC1 and BQP. Furthermore, we consider a restricted version of this model based on an integrable scattering problem in 1+1 dimensions. We show it is universal under postselection, if we allow intermediate destructive measurements and specific input states. Therefore, the existence of any classical procedure to sample from the output distribution of this model within multiplicative error implies collapse of polynomial hierarchy to its third level. Finally, we define a classical version of this model in which one can probabilistically permute balls. We find this yields a complexity class which is intermediate between L and BPP. Moreover, we find a nondeterministic version of this model is NP-complete.
In topological quantum computation the geometric details of a particle trajectory are irrelevant; only the topology matters. Taking this one step further, we consider a model of computation that disregards even the topology of the particle trajectory, and computes by permuting particles. Whereas topological quantum computation requires anyons, permutational quantum computation can be performed with ordinary spin-1/2 particles, using a variant of the spin-network scheme of Marzuoli and Rasetti. We do not know whether permutational computation is universal. It may represent a new complexity class within BQP. Nevertheless, permutational quantum computers can in polynomial time approximate matrix elements of certain irreducible representations of the symmetric group and approximate certain transition amplitudes from the Ponzano-Regge spin foam model of quantum gravity. No polynomial time classical algorithms for these problems are known.
Computational Complexity of Some Quantum Theories in 1+11+11+1 Dimensions
We study the computational complexity of certain integrable quantum theories in 1+1 dimensions. We formalize a model of quantum computation based on these theories. In this model, distinguishable particles start out with known momenta and initial superposition of different configurations. Then the label of these particles are measured at the end. We prove that additive approximation to single amplitudes of these models can be obtained by the one-clean-qubit model, if no initial superpositions are allowed. However, if arbitrary initial states and non-adaptive intermediate measurements are allowed, we show that conditioned on infinite polynomial hierarchy assumption it is hard to sample from the output distribution of these models on a classical randomized computer. A classical analogue of this model is also formalized and its computational power is pinned down within the complexity classes below BPP and NP.
Abstract. In this paper we study quantum computation from a complexity theoretic viewpoint. Our rst result is the existence of an ecient universal quantum Turing machine in Deutsch’s model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97{117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specied. We prove that O(log T) bits of precision suce to support a T step computation. This justies the claim that the quantum Turing machine model should be regarded as a discrete model of computation and not an analog one. We give the rst formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church{Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class BPP. The class BQP of languages that are eciently decidable (with small error-probability) on a quantum Turing machine satises BPP ⊆ BQP ⊆ P]P. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.
In this dissertation we study some effects of allowing computational models that use parameters whose own computational complexity has a strong effect on the computational complexity of the languages computable from the model. We show that in the probabilistic and quantum models there are parameter sets that allow one to obtain noncomputable outcomes;In Chapter 3 we define BP[beta]P the BPP class based on a coin with bias [beta]. We then show that if [beta] is BPP-computable then it is the case that BP[beta]P = BPP. We also show that each language L in P/CLog is in BP[beta]P for some [beta]. Hence there are some [beta] from which we can compute noncomputable languages. We also examine the robustness of the class BPP with respect to small variations from fairness in the coin;In Chapter 4 we consider measures that are based on polynomial-time computable sequences of biased coins in which the biases are bounded away from both zero and one (strongly positive P-sequences). We show that such a sequence [vector][beta] generates a measure [mu][vector][beta] equivalent to the uniform measure in the sense that if C is a class of languages closed under positive, polynomial-time, truth-table reductions with queries of linear length then C has [mu][vector][beta]-measure zero if and only if it has measure zero relative to the uniform measure [mu]. The classes P, NP, BPP, P/Poly, PH, and PSPACE are among those to which this result applies. Thus the measures of these much-studied classes are robust with respect to changes of this type in the underlying probability measure;In Chapter 5 we introduce the quantum computation model and the quantum complexity class BQP. We claim that the computational complexity of the amplitudes is a critical factor in determining the languages computable using the quantum model. Using results from chapter 3 we show that the quantum model can also compute noncomputable languages from some amplitude sets. Finally, we determine a restriction on the amplitude set to limit the model to the range of languages implicit in others' typical meaning of the class BQP.
Deterministic quantum computation with one quantum bit (DQC1) [E. Knill and R. Laflamme, Phys. Rev. Lett. 81, 5672 (1998)] is a model of quantum computing where the input is restricted to containing a single qubit in a pure state and has all other qubits in a completely mixed state. Only the single pure qubit is measured at the end of the computation. While it is known that DQC1 can efficiently solve several problems for which no known classical efficient algorithms exist, the question of whether DQC1 is really more powerful than classical computation remains open. In this Letter, we introduce a slightly modified version of DQC1, which we call DQC1(k), where k output qubits are measured, and show that DQC1(k) cannot be classically efficiently simulated for any k≥3 unless the polynomial hierarchy collapses at the third level.