- arXiv.org
- Applied Physics
- Popular Physics
- Physics and Society
- Data Analysis, Statistics and Probability
- Biological Physics
- Fluid Dynamics
- Optics
- History and Philosophy of Physics
- Space Physics
- General Physics
- Plasma Physics
- Medical Physics
- Atomic Physics
- Geophysics
- Atomic and Molecular Clusters
- Atmospheric and Oceanic Physics
- Computational Physics
- Instrumentation and Detectors
- Chemical Physics
- Classical Physics
- Accelerator Physics
- Physics Education

- Information Theory
- Statistics Theory
- Analysis of PDEs
- Number Theory
- History and Overview
- Combinatorics
- Probability
- Operator Algebras
- Mathematical Physics
- Representation Theory
- Complex Variables
- Group Theory
- Algebraic Geometry
- Symplectic Geometry
- Optimization and Control
- Numerical Analysis
- Logic
- Dynamical Systems
- Metric Geometry
- Geometric Topology
- Differential Geometry
- Quantum Algebra
- General Mathematics
- General Topology
- Functional Analysis
- Category Theory
- Algebraic Topology
- Classical Analysis and ODEs
- Rings and Algebras
- Spectral Theory
- Commutative Algebra
- K-Theory and Homology

- General Literature
- Information Theory
- Neural and Evolutionary Computing
- Symbolic Computation
- Emerging Technologies
- Mathematical Software
- Sound
- Learning
- Formal Languages and Automata Theory
- Information Retrieval
- Computer Vision and Pattern Recognition
- Databases
- Software Engineering
- Social and Information Networks
- Programming Languages
- Operating Systems
- Multiagent Systems
- Artificial Intelligence
- Distributed, Parallel, and Cluster Computing
- Systems and Control
- Cryptography and Security
- Human-Computer Interaction
- Discrete Mathematics
- Hardware Architecture
- Computer Science and Game Theory
- Computational Complexity
- Numerical Analysis
- Other Computer Science
- Networking and Internet Architecture
- Performance
- Computation and Language
- Computational Geometry
- Robotics
- Data Structures and Algorithms
- Graphics
- Logic in Computer Science
- Computers and Society
- Digital Libraries
- Computational Engineering, Finance, and Science
- Multimedia

- 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 $\dots$). To do so, we study the $Membership_{\mathcal{F}}$ problem: for a set of operations $\mathcal{F}$, decide whether an element belongs to the closure by $\mathcal{F}$ of a family of elements. In the boolean case, we prove that $Membership_{\mathcal{F}}$ is in P for any set of boolean operations $\mathcal{F}$. When the input vectors are over a domain larger than two elements, we prove that the generic enumeration method fails, since $Membership_{\mathcal{F}}$ is NP-hard for some $\mathcal{F}$. 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.

Quantum advantage with shallow circuits

Robin Blume-Kohout Apr 07 2017 20:30 UTCDavid Gosset Apr 06 2017 20:11 UTC

Thanks Zak, that's exactly right-- for each instance there is a set of possible solutions. Like in the Bernstein-Vazirani problem, a solution is a bit string. It can't just be a single bit since then we would have the problem you describe, Robin.

Zak Webb Apr 06 2017 17:15 UTC

...(continued)You are completely correct that in order to check whether a give output is "correct" for the input, we would require an additional log-depth classical circuit, but this is not how the problem is defined. In particular, for each input there is a set of "accepting" outputs, and we only need to guaran

Robin Blume-Kohout Apr 06 2017 15:05 UTC

...(continued)Is it okay to be a quantum supremacist? I thought I was, but maybe if it's "tainted" I should reconsider.

On a more serious note... a question for somebody who has read (or written) the paper. If the computation is performed on Poly(n) qubits, and all of them are relevant, and you are only allo

Steve Flammia Apr 04 2017 13:13 UTC

I would like to publicly thank the authors for using the term "advantage" instead of the tainted word "supremacy" that makes me cringe every time I hear it.

Also, great result!

Ashley Apr 04 2017 08:35 UTC

A provable separation between analogous quantum and classical circuit classes!

Māris Ozols Feb 21 2017 15:35 UTC

...(continued)I'm wondering if this result could have any interesting consequences for Hamiltonian complexity. The LCL problem sounds very much like a local Hamiltonian problem, with the run-time of an LCL algorithm corresponding to the range of local interactions in the Hamiltonian.

Maybe one caveat is that thi

Jānis Iraids Jan 25 2017 11:35 UTC

You are correct, that is a mistake -- it should be $\\{0,1\\}^n\rightarrow\\{0,1\\}$. Thank you for spotting it!

Christopher Chubb Jan 25 2017 02:27 UTC

In the abstract, should the domain of $f$ be $\lbrace0,1\rbrace^n$ instead of just $\lbrace0,1\rbrace$?

Zoltán Zimborás Jan 12 2017 20:38 UTC

Here is a nice description, with additional links, about the importance of this work if it turns out to be flawless (thanks a lot to Martin Schwarz for this link): [dichotomy conjecture][1].

[1]: http://processalgebra.blogspot.com/2017/01/has-feder-vardi-dichotomy-conjecture.html

- Supported by Silverpond.