Quantum advantage with shallow circuits


Quantum computers are expected to be better at solving certain computational problems than classical computers. This expectation is based on (well-founded) conjectures in computational complexity theory, but rigorous comparisons between the capabilities of quantum and classical algorithms are difficult to perform. Bravyi et al. proved theoretically that whereas the number of "steps" needed by parallel quantum circuits to solve certain linear algebra problems was independent of the problem size, this number grew logarithmically with size for analogous classical circuits (see the Perspective by Montanaro). This so-called quantum advantage stems from the quantum correlations present in quantum circuits that cannot be reproduced in analogous classical circuits. Science, this issue p. 308; see also p. 289

Technical Perspective: Low-depth Arithmetic Circuits

Communications of the ACM

The computations of polynomials (over a field, which we shall throughout assume is of zero or large enough characteristic) using arithmetic operations of addition and multiplication (and possibly division) are of course as natural as the computation of Boolean functions via logical gates, and capture many natural important tasks including Fourier transforms, linear algebra, matrix computations and more generally symbolic algebraic computations arising in many settings. Arithmetic circuits are the natural computational model for understanding the computational complexity of such tasks just like Boolean circuits are for Boolean functions. The presence of algebraic structure and mathematical tools supplied by centuries of work in algebra were a source of hope that understanding arithmetic circuits will be much faster and easier than their Boolean siblings. And while we generally know more about arithmetic circuits, their power is far from understood, and in particular, the arithmetic analog VP vs. VNP of the Boolean P vs. NP problem as formulated by Valiant8 is wide open. The past few years have seen a revolution in our understanding of arithmetic circuits.

Analogy Engines in Classroom Teaching: Modeling the String Circuit Analogy

AAAI Conferences

The importance of analogy-making and analogy-based reasoning for human cognition and learning by now has widely been recognized, and analogy-based methods are slowly also being explicitly integrated into the canon of approved education and teaching techniques. Still, the actual level of knowledge about analogy as instructional means and device as of today is rather low and subject to scientific study and investigation. In this paper, we propose the fruitful use of computational analogy-engines as methodological tool in this domain of research, motivating our claim by a short case study showing how Heuristic-Driven Theory Projection can be used to model the mode of operation of an analogy taken from a science class for 8 to 9 year old children.

Unexpected Power of Low-Depth Arithmetic Circuits

Communications of the ACM

Complexity theory aims at understanding the "hardness" of certain tasks with respect to the number of "basic operations" required to perform it. In the case of arithmetic circuit complexity, the goal is to understand how hard it is to compute a formal polynomial in terms of the number of additions and multiplications required. Several earlier results have shown that it is possible to rearrange basic computational elements in surprising ways to give more efficient algorithms. The main result of this article is along a similar vein. We present a simulation of any formal polynomial computed by an arithmetic circuit by a shallow circuit of not-much larger size.

Destructive Problem Solving-a Novel Approach to Configuring

AAAI Conferences

An engineer with a circuit diagram has no need of a knowledge base with explicit rules. The ease and absolute certainty with which engineers can draw conclusions from such diagrams made and makes it very tempting to employ such graphical representations for the knowledge and for the results of the configuring process. When circuit diagrams are available, why should our computer-based configuration tools still have need of separately maintained rules? Werner E. Juengst Motivation Manufacturers of complex products have no real choice but use some form of knowledge representation for describing their product offering and determining the configuration for their products. So they employ the existing inefficient rule-based technologies in spite of the large maintenance effort and accept the huge price tag and the shortcomings. Examining more closely what manufacturers are willing to undergo today, some preconceptions of what modelbased techniques should strive for were found to be astray. Most important is that manufacturers are prepared to describe the product feature combinations they want to offer in rules of propositionalogic, i.e. completely, extensively and explicitly, whereas the preconception of researchers is to treat configuration space as unlimited, and construct the solution incrementally from a minimized knowledge base. Another observation is that many manufacturers today create and maintain, for every component (or for every partial bill-of-material) that might be put into the product, Freightliner Corporation 4747 North Channel Avenue Portland, Oregon 97217 WernerJuengst@Freightliner.com