skip to main content
research-article
Free Access

Quantum leap

Published:19 December 2018Publication History
Skip Abstract Section

Abstract

A new proof supports a 25-year-old claim of the unique power of quantum computing.

References

  1. Bernstein, E. and Vazirani, E. Quantum Complexity Theory, SIAM J. Comput. 26, 1411 (1997). Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. Shor, P.W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal of Computing 26, pp. 1484-1509 (1997). Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. Raz, R. and Tal, A. Oracle Separation of BQP and PH, Electronic Colloquium on Computational Complexity, Report No. 107 (2018).Google ScholarGoogle Scholar

Index Terms

  1. Quantum leap

        Recommendations

        Comments

        Login options

        Check if you have access through your login credentials or your institution to get full access on this article.

        Sign in

        Full Access

        • Published in

          cover image Communications of the ACM
          Communications of the ACM  Volume 62, Issue 1
          January 2019
          109 pages
          ISSN:0001-0782
          EISSN:1557-7317
          DOI:10.1145/3301004
          Issue’s Table of Contents

          Copyright © 2018 ACM

          Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

          Publisher

          Association for Computing Machinery

          New York, NY, United States

          Publication History

          • Published: 19 December 2018

          Permissions

          Request permissions about this article.

          Request Permissions

          Check for updates

          Qualifiers

          • research-article
          • Popular
          • Pre-selected
        • Article Metrics

          • Downloads (Last 12 months)84
          • Downloads (Last 6 weeks)32

          Other Metrics

        PDF Format

        View or Download as a PDF file.

        PDF

        eReader

        View online with eReader.

        eReader

        HTML Format

        View this article in HTML Format .

        View HTML Format