Michael Jarret, Brad Lackey, Aike Liu, Kianna Wan
2018-10-10
Quantum adiabatic optimization (QAO) is performed using a time-dependent Hamiltonian
with spectral gap . Assuming the existence of an oracle such that , we provide an algorithm that reliably performs QAO in time with oracle queries, where . Our strategy is not heuristic and does not require guessing time parameters or annealing paths. Rather, our algorithm naturally produces an annealing path such that and chooses its own runtime to be as close as possible to optimal while promising convergence to the ground state. We then demonstrate the feasibility of this approach in practice by explicitly constructing a gap oracle for the problem of finding the minimum point of the cost function , restricting ourselves to computational basis measurements and driving Hamiltonian . Requiring only that have a constant lower bound on its spectral gap and upper bound on its spectral ratio, our QAO algorithm returns with probability in time . This achieves a quantum advantage for all , and recovers Grover scaling up to logarithmic factors when . We implement the algorithm as a subroutine in an optimization procedure that produces with exponentially small failure probability and expected runtime even when is not known beforehand.
Penghui Yao
2019-04-18
This paper initiates the study of a class of entangled-games, mono-state games, denoted by
, where is a two-player one-round game and is a bipartite state independent of the game . In the mono-state game , the players are only allowed to share arbitrary copies of . This paper provides a doubly exponential upper bound on the copies of for the players to approximate the value of the game to an arbitrarily small constant precision for any mono-state binary game , if is a noisy EPR state, which is a two-qubit state with completely mixed states as marginals and maximal correlation less than . In particular, it includes , an EPR state with an arbitrary depolarizing noise . This paper develops a series of new techniques about the Fourier analysis on matrix spaces and proves a quantum invariance principle and a hypercontractive inequality of random operators. The structure of the proofs is built the recent framework about the decidability of the non-interactive simulation of joint distributions, which is completely different from all previous optimization-based approaches or "Tsirelson's problem"-based approaches. This novel approach provides a new angle to study the decidability of the complexity class MIP , a longstanding open problem in quantum complexity theory.
Mosab Hassaan, Karam Gouda
2019-04-18
Graphs are widely used to model complicated data semantics in many application domains. In this paper, two novel and efficient algorithms Fast-ON and Fast-P are proposed for solving the subgraph isomorphism problem. The two algorithms are based on Ullman algorithm [Ullmann 1976], apply vertex-at-a-time matching manner and path-at-a-time matching manner respectively, and use effective heuristics to cut the search space. Comparing to the well-known algorithms, Fast-ON and Fast-P achieve up to 1-4 orders of magnitude speed-up for both dense and sparse graph data.
Arnaud Mary, Yann Strozecki
2017-12-11
In this paper we address the problem of generating all elements obtained by the saturation of an initial set by some operations. More precisely, we prove that we can generate the closure of a boolean relation (a set of boolean vectors) by polymorphisms with a polynomial delay. Therefore we can compute with polynomial delay the closure of a family of sets by any set of "set operations": union, intersection, symmetric difference, subsets, supersets
). To do so, we study the problem: for a set of operations , decide whether an element belongs to the closure by of a family of elements. In the boolean case, we prove that is in P for any set of boolean operations . When the input vectors are over a domain larger than two elements, we prove that the generic enumeration method fails, since is NP-hard for some . We also study the problem of generating minimal or maximal elements of closures and prove that some of them are related to well known enumeration problems such as the enumeration of the circuits of a matroid or the enumeration of maximal independent sets of a hypergraph. This article improves on previous works of the same authors.
Ortho Flint, Asanka Wickramasinghe, Jason Brasse, Christopher Fowler
2019-03-24
In this paper, we provide a polynomial time (and space), algorithm that determines satisfiability of 3-SAT. The complexity analysis for the algorithm takes into account no efficiency and yet provides a low enough bound, that efficient versions are practical with respect to today's hardware. We accompany this paper with a serial version of the algorithm without non-trivial efficiencies.
Alexander Barvinok
2018-06-13
We show that the mixed discriminant of
positive semidefinite real symmetric matrices can be approximated within a relative error in quasi-polynomial time, provided the distance of each matrix to the identity matrix in the operator norm does not exceed some absolute constant . We deduce a similar result for the mixed discriminant of doubly stochastic -tuples of matrices from the Marcus - Spielman - Srivastava bound on the roots of the mixed characteristic polynomial. Finally, we construct a quasi-polynomial algorithm for approximating the sum of -th powers of principal minors of a matrix, provided the operator norm of the matrix is strictly less than 1. As is shown by Gurvits, for the problem is -hard and covers the problem of computing the mixed discriminant of positive semidefinite matrices of rank 2.
Rohit Agrawal
2019-04-17
Blasiok (SODA'18) recently introduced the notion of a subgaussian sampler, defined as an averaging sampler for approximating the mean of functions
such that has subgaussian tails, and asked for explicit constructions. In this work, we give the first explicit constructions of subgaussian samplers (and in fact averaging samplers for the broader class of subexponential functions) that match the best-known constructions of averaging samplers for -bounded functions in the regime of parameters where the approximation error and failure probability are subconstant. Our constructions are established via an extension of the standard notion of randomness extractor (Nisan and Zuckerman, JCSS'96) where the error is measured by an arbitrary divergence rather than total variation distance, and a generalization of Zuckerman's equivalence (Random Struct. Alg.'97) between extractors and samplers. We believe that the framework we develop, and specifically the notion of an extractor for the Kullback-Leibler (KL) divergence, are of independent interest. In particular, KL-extractors are stronger than both standard extractors and subgaussian samplers, but we show that they exist with essentially the same parameters (constructively and non-constructively) as standard extractors.
Sebastian Forster, Liu Yang
2019-04-17
Consider the following "local" cut-detection problem in a directed graph: We are given a starting vertex
and need to detect whether there is a cut with at most edges crossing the cut such that the side of the cut containing has at most interior edges. If we are given query access to the input graph, then this problem can in principle be solved in sublinear time without reading the whole graph and with query complexity depending on and . We design an elegant randomized procedure that solves a slack variant of this problem with queries, improving in particular a previous bound of by Chechik et al. [SODA 2017]. In this slack variant, the procedure must successfully detect a component containing with at most outgoing edges and interior edges if such a component exists, but the component it actually detects may have up to interior edges. Besides being of interest on its own, such cut-detection procedures have been used in many algorithmic applications for higher-connectivity problems. Our new cut-detection procedure therefore almost readily implies (1) a faster vertex connectivity algorithm which in particular has nearly linear running time for polylogarithmic value of the vertex connectivity, (2) a faster algorithm for computing the maximal -edge connected subgraphs, and (3) faster property testing algorithms for higher edge and vertex connectivity, which resolves two open problems, one by Goldreich and Ron [STOC '97] and one by Orenstein and Ron [TCS 2011].
Laxman Dhulipala, Julian Shun, Guy Blelloch
2019-04-17
Due to the dynamic nature of real-world graphs, there has been a growing interest in the graph-streaming setting where a continuous stream of graph updates is mixed with arbitrary graph queries. In principle, purely-functional trees are an ideal choice for this setting due as they enable safe parallelism, lightweight snapshots, and strict serializability for queries. However, directly using them for graph processing would lead to significant space overhead and poor cache locality. This paper presents C-trees, a compressed purely-functional search tree data structure that significantly improves on the space usage and locality of purely-functional trees. The key idea is to use a chunking technique over trees in order to store multiple entries per tree-node. We design theoretically-efficient and practical algorithms for performing batch updates to C-trees, and also show that we can store massive dynamic real-world graphs using only a few bytes per edge, thereby achieving space usage close to that of the best static graph processing frameworks. To study the efficiency and applicability of our data structure, we designed Aspen, a graph-streaming framework that extends the interface of Ligra with operations for updating graphs. We show that Aspen is faster than two state-of-the-art graph-streaming systems, Stinger and LLAMA, while requiring less memory, and is competitive in performance with the state-of-the-art static graph frameworks, Galois, GAP, and Ligra+. With Aspen, we are able to efficiently process the largest publicly-available graph with over two hundred billion edges in the graph-streaming setting using a single commodity multicore server with 1TB of memory.
Dušan Knop, Tomáš Masařík, Tomáš Toufar
2018-03-19
A prototypical graph problem is centered around a graph theoretic property for a set of vertices and a solution is a set of vertices for which the desired property holds. The task is to decide whether, in the given graph, there exists a solution of certain quality, where we use size as a quality measure. In this work we are changing the measure to the fair measure [Lin&Sahni: Fair edge deletion problems. IEEE Trans. Comput. 89]. The measure is k if the number of solution neighbors does not exceed k for any vertex in the graph. One possible way to study graph problems is by defining the property in a certain logic. For a given objective an evaluation problem is to find a set (of vertices) that simultaneously minimizes the assumed measure and satisfies an appropriate formula. In the presented paper we show that there is an FPT algorithm for the MSO Fair Vertex Evaluation problem for formulas with one free variable parameterized by the twin cover number of the input graph. Here, the free variable corresponds to the solution sought. One may define an extended variant of MSO Fair Vertex Evaluation for formulas with l free variables; here we measure maximum number of neighbors in each of the l sets. However, such variant is W[1]-hard even on graphs with twin cover one. Furthermore, we study the Fair Vertex Cover (Fair VC) problem. Fair VC is among the simplest problems with respect to the demanded property (i.e., the rest forms an edgeless graph). On the negative side, Fair VC is W[1]-hard when parameterized by both treedepth and feedback vertex set of the input graph. On the positive side, we provide an FPT algorithm for the parameter modular width.
