Transcript ppt - vlsicad server (Prof. Markov`s group)

Improving Gate-Level Simulation of
Quantum Circuits
George F. Viamontes,
Igor L. Markov, and John P. Hayes
{gviamont,imarkov,jhayes}@umich.edu
Advanced Computer Architecture Laboratory
University of Michigan, EECS
DARPA
Problem
• Simulation of quantum computing on a
classical computer
– Requires exponentially growing time and
memory resources
• Goal: Improve classical simulation
• Our Solution: Quantum Information
Decision Diagrams (QuIDDs)
Outline
•
•
•
•
•
•
Background
QuIDD Structure
QuIDD Operations
Simulation Results
Complexity Analysis Results
Ongoing Work
Quantum Data
• Classical bit
– Two possible states: 0 or 1
– Measurement is straightforward
• Qubit (properties follow from Q. M.)
– Quantum state
– Can be in states 0 or 1, but also
in a superposition of 0 and 1
– n qubits represents 2 n
different values simultaneously
– Measurement is probabilistic and destructive
Implementations
• Liquid and solid state nuclear magnetic
resonance (NMR) – nuclear spins
• Ion traps – electron energy levels
• Electrons floating on liquid helium –
electron spins
• Optical technologies – photon polarizations
• Focus of this work:
common mathematical description
Qubit Notation
• Qubits expressed in Dirac notation
  0   1
• Vector representation:  
 
 
•
 and  are complex numbers called
probability amplitudes s.t. |  |2  |  |2  1
Data Manipulation
• Qubits are manipulated by operators
– Analogous to logic gates
• Operators are unitary matrices
• Matrix-vector multiplication describes
operator functionality

U
'
U   '
Operations on Multiple Qubits
• Tensor product of operators/qubits
1 / 2

1 / 2
1 / 2  1 / 2

 1 / 2  1 / 2

H
'

H
'
1 / 2

1 / 2  1 / 2

 1 / 2  1 / 2

1 / 2
1/ 2
1/ 2
1/ 2
1/ 2
1/ 2
1/ 2
1/ 2
1/ 2
H  H 
1/ 2 
 1 / 2
 1 / 2

1/ 2 
  ' '
Previous Work
• Traditional array-based representations
are insensitive to the values stored
• Qubit-wise multiplication
– 1-qubit operator and n-qubit state vector
– State vector requires exponential memory
• BDD techniques
– Multi-valued logic for q. circuit synthesis [1]
– Shor’s algorithm simulator (SHORNUF) [8]
Redundancy in
Quantum Computing
• Matrix/vector representation of quantum
gates/state vectors contains block patterns
• The tensor product propagates block
patterns in vectors and matrices
Example of
Propagated Block Patterns
1 / 2

1 / 2
1 / 2  1 / 2

 1 / 2  1 / 2
1/ 2 

1/ 2 
1/ 2
1/ 2 
1 / 2 1 / 2
1 / 2  1 / 2 1 / 2  1 / 2

 
1 / 2 1 / 2  1 / 2  1 / 2


1 / 2  1 / 2  1 / 2 1 / 2 
Outline
•
•
•
•
•
•
Background
QuIDD Structure
QuIDD Operations
Simulation Results
Complexity Analysis Results
Ongoing Work
Data Structure
that Exploits Redundancy
• Binary Decision Diagrams (BDDs) exploit repeated
sub-structure
• BDDs have been used to simulate classical logic
circuits efficiently [6,2]
f
• Example: f = a AND b
a
Assign value of 1 to variable x
b
Assign value of 0 to variable x
1
0
BDDs in Linear Algebra
• Algebraic Decision Diagrams (ADDs)
treat variable nodes as matrix indices
[2], also MTBDDs
• ADDs encode all matrix elements aij
– Input variables capture bits of i and j
– Terminals represent the value of aij
• CUDD implements linear algebra for
ADDs (without decompression)
Quantum Information
Decision Diagrams (QuIDDs)
• QuIDDs: an application of ADDs
to quantum computing
• QuIDD matrices : row (i), column (j) vars
• QuIDD vectors: column vars only
• Matrix-vector multiplication
cij   aijb j
i 1 j 1
performed in terms of QuIDDs
QuIDD Vectors
f
C0
C1
1
0
0
0 + 0i
1
1 + 0i

 0 00
 0 01
 
 0 10
 11
1 
 11
Terminal value array
QuIDD Matrices
f
00
R0
C0
R1
R1

00
01
10
11
C1
C1
1
10
11
1/ 2
1/ 2 
1 / 2 1 / 2
1 / 2  1 / 2 1 / 2  1 / 2


1 / 2 1 / 2  1 / 2  1 / 2


1 / 2  1 / 2  1 / 2 1 / 2 
0
0
01
1 / 2  0i
1 1/ 2  0i
QuIDDs and ADDs
• All dimensions are 2n
• Row and column variables are interleaved
R0  C0  R1  C1    Rn  Cn  T
• Terminals are integers which map
into an array of complex numbers
Outline
•
•
•
•
•
•
Background
QuIDD Structure
QuIDD Operations
Simulation Results
Complexity Analysis Results
Conclusions
QuIDD Operations
• Based on the Apply algorithm [4,5]
– Construct new QuIDDs by traversing
two QuIDD operands based on variable ordering
– Perform “op” when terminals reached (op is *, +, etc.)
– General Form: f op g where f and g are QuIDDs, and x
and y are variables in f and g, respectively:
xi  yi
xi  yi
xi  yi
xi
yi
xi
f xi op g yi
f x op g y
i
i
xi op g yi
xi op g y
i
f xi op yi
f x op yi
i
Tensor Product
• Given A B
– Every element of a matrix A
is multiplied by the entire matrix B
• QuIDD Implementation: Use Apply
– Operands are A and B
– Variables of operand B are shifted
– “op” is defined to be multiplication
Other Operations
• Matrix multiplication
– Modified ADD matrix multiply algorithm [2]
– Support for terminal array
– Support for row/column variable ordering
• Matrix addition
– Call to Apply with “op” set to addition
• Qubit measurement
– DFS traversal or measurement operators
Outline
•
•
•
•
•
•
Background
QuIDD Structure
QuIDD Operations
Simulation Results
Complexity Analysis Results
Ongoing Work
Grover’s Algorithm
|0>
H
H
H
|0>
H
H
H
.
.
.
|1>
Oracle
.
.
.
Conditional
Phase Shift
.
.
.
H
H
- Search for items in an unstructured database of N items
- Contains n = log N qubits and has runtime O N
 
Number of Iterations
• Use formulation from Boyer et al. [3]
• Exponential runtime
(even on an actual quantum computer)
• Actual Quantum Computer Performance:
~ O(1.41n) time and O(n) memory
Simulation Results for
Grover’s Algorithm
• Linear memory growth
(numbers of nodes shown)
Results: Oracle 1
Linear Growth
using QuIDDPro
Oracle 1: Runtime (s)
No. Qubits (n)
Octave
MATLAB
Blitz++
QuIDDPro
10
80.6
6.64
0.15
0.33
11
2.65e2
22.5
0.48
0.54
12
8.36e2
74.2
1.49
0.83
13
2.75e3
2.55e2
4.70
1.30
14
1.03e4
1.06e3
14.6
2.01
15
4.82e4
6.76e3
44.7
3.09
16
> 24 hrs
> 24 hrs
1.35e2
4.79
17
> 24 hrs
> 24 hrs
4.09e2
7.36
18
> 24 hrs
> 24 hrs
1.23e3
11.3
19
> 24 hrs
> 24 hrs
3.67e3
17.1
20
> 24 hrs
> 24 hrs
1.09e4
26.2
Oracle 1: Peak Memory Usage (MB)
No. Qubits (n)
Octave
MATLAB
Blitz++
QuIDDPro
10
2.64e-2
1.05e-2
3.52e-2
9.38e-2
11
5.47e-2
2.07e-2
8.20e-2
0.121
12
0.105
4.12e-2
0.176
0.137
13
0.213
8.22e-2
0.309
0.137
14
0.426
0.164
0.559
0.137
15
0.837
0.328
1.06
0.137
16
1.74
0.656
2.06
0.145
17
3.34
1.31
4.06
0.172
18
4.59
2.62
8.06
0.172
19
13.4
5.24
16.1
0.172
20
27.8
10.5
32.1
0.172
Linear Growth
using QuIDDPro
Validation of Results
• SANITY CHECK: Make sure that QuIDDPro
achieves highest probability of measuring the
item(s) to be searched using the number of
iterations predicted by Boyer et al. [3]
Consistency with Theory
Grover Results Summary
• Asymptotic performance
– QuIDDPro: ~ O(1.44n) time and O(n) memory
– Actual Quantum Computer
• ~ O(1.41n) time and O(n) memory
• Outperforms other simulation techniques
– MATLAB: (2n) time and (2n) memory
– Blitz++: (4n) time and (2n) memory
What about errors?
• Do the errors and mixed states that are
encountered in practical quantum
circuits cause QuIDDs to explode and
lose significant performance?
NIST Benchmarks
• NIST offers a multitude of quantum circuit
descriptions containing errors/decoherence
and mixed states
• NIST also offers a density matrix C++
simulator called QCSim
• How does QuIDDPro compare to QCSim
on these circuits?
QCSim vs. QuIDDPro
• dsteaneZ: 13-qubit circuit with initial mixed
state that implements the Steane code to
correct phase flip errors
– QCSim: 287.1 seconds, 512.1MB
– QuIDDPro: 0.639 seconds, 0.516 MB
QCSim vs. QuIDDPro (2)
• dsteaneX: 12-qubit circuit with initial mixed
state that implements the Steane code to
correct bit flip errors
– QCSim: 53.2 seconds, 128.1MB
– QuIDDPro: 0.33 seconds, 0.539 MB
Outline
•
•
•
•
•
•
Background
QuIDD Structure
QuIDD Operations
Simulation Results
Complexity Analysis Results
Ongoing Work
Recall the Tensor Product
Key Formula
n
i i 1
• Given QuIDDs {Q } , the tensor product
n
QuIDD i 1 Qi contains
| In(Q1 ) | i 2 | In(Qi ) || Term( ) |
n
 | Term(in1 Qi ) | nodes
i 1
j 1
Persistent Sets
• A set  is persistent if and only if the set
of n pair-wise products of its elements is
constant (i.e. the pair-wise product n times)
• Consider the tensor product of two matrices
whose elements form a persistent set
– The number of unique elements in the resulting
matrix will be a constant with respect to the
number of unique elements in the operands
Relevance to QuIDDs
• Tensor products with n QuIDDs whose
terminals form a persistent set produce
QuIDDs whose sets of terminals do not
increase with n
Main Results
• Given a persistent set  and a constant C,
consider n QuIDDs with at most C nodes
each and terminal values from . The
tensor product of those QuIDDs has O(n)
nodes and can be computed in O(n) time.
• Matrix multiplication with QuIDDs A and B
as operands requires O(( AB) 2time
) and
produces a result with O(( AB) 2 ) nodes [2]
Applied to Grover’s Algorithm
• Since O(1.41n) Grover iterations are required,
and thus O(1.41n) matrix multiplications, does
Grover’s algorithm induce exponential memory
complexity when using QuIDDs?
• Answer: NO!
– The internal nodes of the state vector/density matrix
QuIDD is the same at the end of each Grover
iteration
– Runtime and memory requirements are therefore
polynomial in the size of the oracle QuIDD
Outline
•
•
•
•
•
•
Background
QuIDD Structure
QuIDD Operations
Simulation Results
Complexity Analysis Results
Ongoing Work
Ongoing Work
• Explore error/decoherence models
• Simulate Shor’s algorithm
– QFT and its inverse are exponential in size as
QuIDDs
– Other operators are linear in size as QuIDDs
– QFT and its inverse are an asymptotic
bottleneck
• Limitations of quantum computing
Relevant Work
G. Viamontes, I. Markov, J. Hayes, “Improving Gate-Level
Simulation of Quantum circuits,” Los Alamos Quantum Physics
Archive, Sept. 2003 (quant-ph/0309060)
G. Viamontes, M. Rajagopalan, I. Markov, J. Hayes, “GateLevel Simulation of Quantum Circuits,” Asia South Pacific
Design Automation Conference, pp. 295-301, January 2003
G. Viamontes, M. Rajagopalan, I. Markov, J. Hayes, ‘GateLevel Simulation of Quantum Circuits,” 6th Intl. Conf. on
Quantum Communication, Measurement, and Computing, pp.
311-314, July 2002
References
[1] A. N. Al-Rabadi et al., “Multiple-Valued Quantum Logic,” 11th
Intl. Workshop on Post Binary ULSI, Boston, MA, May 2002.
[2] R. I. Bahar et al., “Algebraic Decision Diagrams and their
Applications”, In Proc. IEEE/ACM ICCAD, pp. 188-191, 1993.
[3] M. Boyer et al., “Tight Bounds on Quantum Searching”, Fourth
Workshop on Physics and Computation, Boston, Nov 1996.
[4] R. Bryant, “Graph-Based Algorithms for Boolean Function
Manipulation”, IEEE Trans. On Computers, vol. C-35, pp. 677691, Aug 1986.
[5] E. Clarke et al., “Multi-Terminal Binary Decision Diagrams and
Hybrid Decision Diagrams”, In T. Sasao and M. Fujita, eds,
Representations of Discrete Functions, pp. 93-108, Kluwer,
1996.
References
[6] C.Y. Lee, “Representation of Switching Circuits by Binary
Decision Diagrams,” Bell System Technical Jour., 38:985-999,
1959.
[7] D. Gottesman, “The Heisenberg Representation of Quantum
Computers,” Plenary Speech at the 1998 Intl. Conf. on Group
Theoretic Methods in Physics, http://xxx.lanl.gov/abs/quantph/9807006
[8] D. Greve, “QDD: A Quantum Computer Emulation Library,”
http://home.plutonium.net/~dagreve/qdd.html