Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Computational Complexity of Ball Permutations
58
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
The classic Ham-Sandwich theorem states that for any $d$ measurable sets in $mathbb{R}^d$, there is a hyperplane that bisects them simultaneously. An extension by Barany, Hubard, and Jeronimo [DCG 2008] states that if the sets are convex and emph{well-separated}, then for any given $alpha_1, dots, alpha_d in [0, 1]$, there is a unique oriented hyperplane that cuts off a respective fraction $alpha_1, dots, alpha_d$ from each set. Steiger and Zhao [DCG 2010] proved a discrete analogue of this theorem, which we call the emph{$alpha$-Ham-Sandwich theorem}. They gave an algorithm to find the hyperplane in time $O(n (log n)^{d-3})$, where $n$ is the total number of input points. The computational complexity of this search problem in high dimensions is open, quite unlike the complexity of the Ham-Sandwich problem, which is now known to be PPA-complete (Filos-Ratsikas and Goldberg [STOC 2019]). Recently, Fearley, Gordon, Mehta, and Savani [ICALP 2019] introduced a new sub-class of CLS (Continuous Local Search) called emph{Unique End-of-Potential Line} (UEOPL). This class captures problems in CLS that have unique solutions. We show that for the $alpha$-Ham-Sandwich theorem, the search problem of finding the dividing hyperplane lies in UEOPL. This gives the first non-trivial containment of the problem in a complexity class and places it in the company of classic search problems such as finding the fixed point of a contraction map, the unique sink orientation problem and the $P$-matrix linear complementarity problem.
Diffusion-Limited Aggregation (DLA) is a cluster-growth model that consists in a set of particles that are sequentially aggregated over a two-dimensional grid. In this paper, we introduce a biased version of the DLA model, in which particles are limited to move in a subset of possible directions. We denote by $k$-DLA the model where the particles move only in $k$ possible directions. We study the biased DLA model from the perspective of Computational Complexity, defining two decision problems The first problem is Prediction, whose input is a site of the grid $c$ and a sequence $S$ of walks, representing the trajectories of a set of particles. The question is whether a particle stops at site $c$ when sequence $S$ is realized. The second problem is Realization, where the input is a set of positions of the grid, $P$. The question is whether there exists a sequence $S$ that realizes $P$, i.e. all particles of $S$ exactly occupy the positions in $P$. Our aim is to classify the Prediciton and Realization problems for the differe
The 2008 financial crisis has been attributed to excessive complexity of the financial system due to financial innovation. We employ computational complexity theory to make this notion precise. Specifically, we consider the problem of clearing a financial network after a shock. Prior work has shown that when banks can only enter into simple debt contracts with each other, then this problem can be solved in polynomial time. In contrast, if they can also enter into credit default swaps (CDSs), i.e., financial derivative contracts that depend on the default of another bank, a solution may not even exist. In this work, we show that deciding if a solution exists is NP-complete if CDSs are allowed. This remains true if we relax the problem to $varepsilon$-approximate solutions, for a constant $varepsilon$. We further show that, under sufficient conditions where a solution is guaranteed to exist, the approximate search problem is PPAD-complete for constant $varepsilon$. We then try to isolate the origin of the complexity. It turns out that already determining which banks default is hard. Further, we show that the complexity is not driven by the dependence of counterparties on each other, but rather hinges on the presence of so-called naked CDSs. If naked CDSs are not present, we receive a simple polynomial-time algorithm. Our results are of practical importance for regulators stress tests and regulatory policy.
We show the problem of counting homomorphisms from the fundamental group of a homology $3$-sphere $M$ to a finite, non-abelian simple group $G$ is #P-complete, in the case that $G$ is fixed and $M$ is the computational input. Similarly, deciding if there is a non-trivial homomorphism is NP-complete. In both reductions, we can guarantee that every non-trivial homomorphism is a surjection. As a corollary, for any fixed integer $m ge 5$, it is NP-complete to decide whether $M$ admits a connected $m$-sheeted covering. Our construction is inspired by universality results in topological quantum computation. Given a classical reversible circuit $C$, we construct $M$ so that evaluations of $C$ with certain initialization and finalization conditions correspond to homomorphisms $pi_1(M) to G$. An intermediate state of $C$ likewise corresponds to a homomorphism $pi_1(Sigma_g) to G$, where $Sigma_g$ is a pointed Heegaard surface of $M$ of genus $g$. We analyze the action on these homomorphisms by the pointed mapping class group $text{MCG}_*(Sigma_g)$ and its Torelli subgroup $text{Tor}_*(Sigma_g)$. By results of Dunfield-Thurston, the action of $text{MCG}_*(Sigma_g)$ is as large as possible when $g$ is sufficiently large; we can pass to the Torelli group using the congruence subgroup property of $text{Sp}(2g,mathbb{Z})$. Our results can be interpreted as a sharp classical universality property of an associated combinatorial $(2+1)$-dimensional TQFT.
We study the quantum query complexity of finding a certificate for a d-regular, k-level balanced NAND formula. Up to logarithmic factors, we show that the query complexity is Theta(d^{(k+1)/2}) for 0-certificates, and Theta(d^{k/2}) for 1-certificates. In particular, this shows that the zero-error quantum query complexity of evaluating such formulas is O(d^{(k+1)/2}) (again neglecting a logarithmic factor). Our lower bound relies on the fact that the quantum adversary method obeys a direct sum theorem.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
