TY - GEN
T1 - Characterizing the performance effect of trials and rotations in applications that use Quantum Phase Estimation
AU - Patil, Shruti
AU - Javadiabhari, Ali
AU - Chiang, Chen Fu
AU - Heckey, Jeff
AU - Martonosi, Margaret Rose
AU - Chong, Frederic T.
N1 - Publisher Copyright:
© 2014 IEEE.
PY - 2014/12/11
Y1 - 2014/12/11
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84946035033&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84946035033&partnerID=8YFLogxK
U2 - 10.1109/IISWC.2014.6983057
DO - 10.1109/IISWC.2014.6983057
M3 - Conference contribution
AN - SCOPUS:84946035033
T3 - IISWC 2014 - IEEE International Symposium on Workload Characterization
SP - 181
EP - 190
BT - IISWC 2014 - IEEE International Symposium on Workload Characterization
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2014 IEEE International Symposium on Workload Characterization, IISWC 2014
Y2 - 26 October 2014 through 28 October 2014
ER -