Characterizing the performance effect of trials and rotations in applications that use Quantum Phase Estimation

Shruti Patil, Ali Javadiabhari, Chen Fu Chiang, Jeff Heckey, Margaret Rose Martonosi, Frederic T. Chong

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

Abstract

Quantum Phase Estimation (QPE) is one of the key techniques used in quantum computation to design quantum algorithms which can be exponentially faster than classical algorithms. Intuitively, QPE allows quantum algorithms to find the hidden structure in certain kinds of problems. In particular, Shor's well-known algorithm for factoring the product of two primes uses QPE. Simulation algorithms, such as Ground State Estimation (GSE) for quantum chemistry, also use QPE. Unfortunately, QPE can be computationally expensive, either requiring many trials of the computation (repetitions) or many small rotation operations on quantum bits. Selecting an efficient QPE approach requires detailed characterizations of the tradeoffs and overheads of these options. In this paper, we explore three different algorithms that trade off trials versus rotations. We perform a detailed characterization of their behavior on two important quantum algorithms (Shor's and GSE). We also develop an analytical model that characterizes the behavior of a range of algorithms in this tradeoff space.

Original languageEnglish (US)
Title of host publicationIISWC 2014 - IEEE International Symposium on Workload Characterization
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages181-190
Number of pages10
ISBN (Electronic)9781479964536
DOIs
StatePublished - Dec 11 2014
Event2014 IEEE International Symposium on Workload Characterization, IISWC 2014 - Raleigh, United States
Duration: Oct 26 2014Oct 28 2014

Publication series

NameIISWC 2014 - IEEE International Symposium on Workload Characterization

Other

Other2014 IEEE International Symposium on Workload Characterization, IISWC 2014
CountryUnited States
CityRaleigh
Period10/26/1410/28/14

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Hardware and Architecture
  • Software
  • Electrical and Electronic Engineering
  • Control and Systems Engineering

Fingerprint Dive into the research topics of 'Characterizing the performance effect of trials and rotations in applications that use Quantum Phase Estimation'. Together they form a unique fingerprint.

  • Cite this

    Patil, S., Javadiabhari, A., Chiang, C. F., Heckey, J., Martonosi, M. R., & Chong, F. T. (2014). Characterizing the performance effect of trials and rotations in applications that use Quantum Phase Estimation. In IISWC 2014 - IEEE International Symposium on Workload Characterization (pp. 181-190). [6983057] (IISWC 2014 - IEEE International Symposium on Workload Characterization). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/IISWC.2014.6983057