info
Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
QCSIM -- A Language for Quantum Circuit Simulation in Forth
183 views
Skip to first unread message
Krishna Myneni
Nov 3, 2019, 10:06:59 AM11/3/19
to
I have developed the following DSL specification for doing simulations of
a few-qubit (n < 6) quantum circuits in a Forth environment. Much of this
has already been implemented and some of it has been tested. Some work
still needs to be done (implementation of Kronecker outer products and
measurement of quantum states, but it is straightforward, if tedious).
Examples for simulating simple quantum circuits are given below (Warning:
the formatting may become mangled by Google groups):
1) Simple one-qubit quantum circuit. Input state is qubit 0.
q0 |0> ---[H]---
Compute output state and probabilities for 0 and 1.
1 qstate out \ make an uninitialized 1-qubit state called 'out'
H |0> g*q q. \ print output state for input state |0>
H |0> g*q out q-> \ compute and store output state
out 0 prob . \ print probability of measuring 0 for qstate out
out 1 prob . \ print probability of measuring 1 for qstate out
2) Two-qubit quantum circuit with only single qubit gates
q1 |0> ---[H]---
q0 |0> ---[X]---
2 qstate out
H |0> g*q X |0> g*q qxq out q-> \ compute output state for circuit
out all-prob \ display probabilities for measuring all bit strings
out measure c.
3) Two-qubit quantum circuit with entangled qubits.
:
q1 |0> ---[H]-----*-----
: |
q0 |0> ---[X]----[CX]---
:
1
2 qstate out
H |0> g*q X |0> g*q \ quantum state at 1: -- q1' q0'
qxq \ outer product of two 1-qubit states
\ to give 2-qubit state -- q
U2CX swap g*q out q-> \ output quantum state in 'out'
out all-prob
GLOSSARY for the Quantum Circuit Simulation language
Special stack notation:
c unsigned single cell value interpreted as a series of n classical
bits (where n must be specified).
q pointer to an n-qubit quantum state vector (qstate), either in the
dynamic buffer (transient persistence) or to the state vector data in the
child of QSTATE (reserved storage).
g pointer to a unitary n-qubit gate , either in the the dynamic buffer
(transient persistence) or to the child of UNITARY (reserved storage).
\ Helper words, typically not needed for direct use
2^ ( n -- m ) m = 2^n
Q-SIZE ( 2^n -- u ) return size (bytes) for n-qubit state
G-SIZE ( 2^n -- u ) return size (bytes) for n-qubit gate
Q-HDR! ( 2^n a -- q ) store header in n-qubit state struct
G-HDR! ( 2^n a -- g ) store header in n-qubit gate struct
ALLOC_QBUF ( u -- a ) get transient memory for u bytes
ALLOC_Q ( 2^n -- q ) get transient memory for n-qubit state
ALLOC_G ( 2^n -- g ) get transient memory for n-qubit gate
\ Defining words for quantum states and gates
QSTATE ( n "name" -- ) create named n-qubit state
QUBITS ( z1 ... z2^n n "name" -- ) created initialized state
UNITARY ( n "name" -- ) create named n-qubit unitary gate
GATE ( z11 ... z1n z21 ... znn n "name" -- ) initialized gate
\ Operations on classical bits, quantum states, and gates
CBITS ( c 2^n -- caddr u ) return bit string for c
QDIM ( q -- 2^n ) return dimension of qubit state
GDIM ( g -- 2^n ) return dimension of gate
C. ( c -- ) print binary representation of c
Q. ( q -- ) print a qubit state
G. ( g -- ) print gate matrix
Q-> ( q1 q2 -- ) copy qubit state q1 to q2
G-> ( g1 g2 -- ) copy gate g1 to g2
G*Q ( g q1 -- q2 ) Apply gate g to qubit state q1
G*G ( g1 g2 -- g3 ) g3 = gate for g2 followed by g1
QxQ ( q1 q2 -- q3 ) q3 = kronecker product of q1 and q2
GxG ( g1 g2 -- g3 ) g3 = kronecker product of g1 and g2
G-DAG ( g1 -- g2 ) g2 = adjoint of g1 (g1 "dagger")
\ Measurements
PROB ( q c -- r ) return probability for measuring c
ALL-PROB ( q -- ) show all bit string probabilities for q
MEASURE ( q -- c ) execute circuit and measure outputs
There are predefined single and two-qubit quantum states, e.g.
|0> |1> |00> |01> |10> |11>
and predefined single and two-qubit gates:
I1 X Y Z S H
I2 U2CX U2CXR U2CZ U2SW
(U2CX is the two-qubit CNOT gate). Multi-qubit states for n > 1 may be
built from single qubit states using the Kronecker product, and similarly
for n > 1 gates.
I expect to post an initial version of qcsim.4th in a few days.
Krishna Myneni
a few-qubit (n < 6) quantum circuits in a Forth environment. Much of this
has already been implemented and some of it has been tested. Some work
still needs to be done (implementation of Kronecker outer products and
measurement of quantum states, but it is straightforward, if tedious).
Examples for simulating simple quantum circuits are given below (Warning:
the formatting may become mangled by Google groups):
1) Simple one-qubit quantum circuit. Input state is qubit 0.
q0 |0> ---[H]---
Compute output state and probabilities for 0 and 1.
1 qstate out \ make an uninitialized 1-qubit state called 'out'
H |0> g*q q. \ print output state for input state |0>
H |0> g*q out q-> \ compute and store output state
out 0 prob . \ print probability of measuring 0 for qstate out
out 1 prob . \ print probability of measuring 1 for qstate out
2) Two-qubit quantum circuit with only single qubit gates
q1 |0> ---[H]---
q0 |0> ---[X]---
2 qstate out
H |0> g*q X |0> g*q qxq out q-> \ compute output state for circuit
out all-prob \ display probabilities for measuring all bit strings
out measure c.
3) Two-qubit quantum circuit with entangled qubits.
:
q1 |0> ---[H]-----*-----
: |
q0 |0> ---[X]----[CX]---
:
1
2 qstate out
H |0> g*q X |0> g*q \ quantum state at 1: -- q1' q0'
qxq \ outer product of two 1-qubit states
\ to give 2-qubit state -- q
U2CX swap g*q out q-> \ output quantum state in 'out'
out all-prob
GLOSSARY for the Quantum Circuit Simulation language
Special stack notation:
c unsigned single cell value interpreted as a series of n classical
bits (where n must be specified).
q pointer to an n-qubit quantum state vector (qstate), either in the
dynamic buffer (transient persistence) or to the state vector data in the
child of QSTATE (reserved storage).
g pointer to a unitary n-qubit gate , either in the the dynamic buffer
(transient persistence) or to the child of UNITARY (reserved storage).
\ Helper words, typically not needed for direct use
2^ ( n -- m ) m = 2^n
Q-SIZE ( 2^n -- u ) return size (bytes) for n-qubit state
G-SIZE ( 2^n -- u ) return size (bytes) for n-qubit gate
Q-HDR! ( 2^n a -- q ) store header in n-qubit state struct
G-HDR! ( 2^n a -- g ) store header in n-qubit gate struct
ALLOC_QBUF ( u -- a ) get transient memory for u bytes
ALLOC_Q ( 2^n -- q ) get transient memory for n-qubit state
ALLOC_G ( 2^n -- g ) get transient memory for n-qubit gate
\ Defining words for quantum states and gates
QSTATE ( n "name" -- ) create named n-qubit state
QUBITS ( z1 ... z2^n n "name" -- ) created initialized state
UNITARY ( n "name" -- ) create named n-qubit unitary gate
GATE ( z11 ... z1n z21 ... znn n "name" -- ) initialized gate
\ Operations on classical bits, quantum states, and gates
CBITS ( c 2^n -- caddr u ) return bit string for c
QDIM ( q -- 2^n ) return dimension of qubit state
GDIM ( g -- 2^n ) return dimension of gate
C. ( c -- ) print binary representation of c
Q. ( q -- ) print a qubit state
G. ( g -- ) print gate matrix
Q-> ( q1 q2 -- ) copy qubit state q1 to q2
G-> ( g1 g2 -- ) copy gate g1 to g2
G*Q ( g q1 -- q2 ) Apply gate g to qubit state q1
G*G ( g1 g2 -- g3 ) g3 = gate for g2 followed by g1
QxQ ( q1 q2 -- q3 ) q3 = kronecker product of q1 and q2
GxG ( g1 g2 -- g3 ) g3 = kronecker product of g1 and g2
G-DAG ( g1 -- g2 ) g2 = adjoint of g1 (g1 "dagger")
\ Measurements
PROB ( q c -- r ) return probability for measuring c
ALL-PROB ( q -- ) show all bit string probabilities for q
MEASURE ( q -- c ) execute circuit and measure outputs
There are predefined single and two-qubit quantum states, e.g.
|0> |1> |00> |01> |10> |11>
and predefined single and two-qubit gates:
I1 X Y Z S H
I2 U2CX U2CXR U2CZ U2SW
(U2CX is the two-qubit CNOT gate). Multi-qubit states for n > 1 may be
built from single qubit states using the Kronecker product, and similarly
for n > 1 gates.
I expect to post an initial version of qcsim.4th in a few days.
Krishna Myneni
Krishna Myneni
Nov 3, 2019, 10:28:16 AM11/3/19
to
On Sun, 03 Nov 2019 15:06:57 +0000, Krishna Myneni wrote:
>
> 1) Simple one-qubit quantum circuit. Input state is qubit 0.
>
> q0 |0> ---[H]---
>
> Compute output state and probabilities for 0 and 1.
...
>
> 1) Simple one-qubit quantum circuit. Input state is qubit 0.
>
> q0 |0> ---[H]---
>
> Compute output state and probabilities for 0 and 1.
> out 0 prob . \ print probability of measuring 0 ...
> out 1 prob . \ print probability of measuring 1 ...
That should be
out 0 prob F. \ print probability of measuring 0
out 1 prob F. \ print probability of measuring 1
KM
Krishna Myneni
Nov 3, 2019, 3:44:26 PM11/3/19
to
On Sun, 03 Nov 2019 15:06:57 +0000, Krishna Myneni wrote:
> I have developed the following DSL specification for doing simulations
> of a few-qubit (n < 6) quantum circuits in a Forth environment.
...
> of a few-qubit (n < 6) quantum circuits in a Forth environment.
> I expect to post an initial version of qcsim.4th in a few days.
>
Apparently there are a couple of projects with the name QCSIM, to perform
>
quantum circuit simulations. I will rename the Forth code to avoid
confusion. One QCsim project on github provides appears to have language
bindings to the openQASM code for python, C, and C++. The Forth quantum
circuit simulator is written entirely in Forth, and its purpose, at this
point, is pedagogical: introduce quantum circuits in the form of code.
KM
Krishna Myneni
Nov 6, 2019, 9:53:13 PM11/6/19
to
On Sun, 03 Nov 2019 15:06:57 +0000, Krishna Myneni wrote:
> I have developed the following DSL specification for doing simulations
> of a few-qubit (n < 6) quantum circuits in a Forth environment.
...
> of a few-qubit (n < 6) quantum circuits in a Forth environment.
> Multi-qubit states for n > 1 may be built from single qubit states
> using the Kronecker product, and similarly for n > 1 gates.
...
> using the Kronecker product, and similarly for n > 1 gates.
The Kronecker outer product for complex matrices }}ZKRON is now
implemented in the module zmatrix.4th [1]. The program qcsim.4th works on
2-qubit circuits and is close to being usable for 2 < n < 6 qubit circuit
simulations with quite a few 1 and 2-qubit gates available, enough, for
example, to simulate a 3-qubit QFT (quantum Fourier transform) circuit.
KM
1. https://github.com/mynenik/kForth-32/blob/master/forth-src/fsl/extras/
zmatrix.4th
Krishna Myneni
Nov 7, 2019, 9:50:22 PM11/7/19
to
On Sun, 03 Nov 2019 15:06:57 +0000, Krishna Myneni wrote:
> I have developed the following DSL specification for doing simulations
> of a few-qubit (n < 6) quantum circuits in a Forth environment.
A running preliminary version of qcsim.4th may be found at the link
> of a few-qubit (n < 6) quantum circuits in a Forth environment.
below. The examples, 1--3, at the bottom of the source file will work
properly. There is a little infrastructure to add for building up n-qubit
gates, and generating arbitrary input states to a quantum circuit, and
performing measurements on the output qubits -- these are listed under
"Not yet implemented" below the glossary. I think the interface is
finally converging, after having tried and abandoned several approaches.
The present interface uses a mix of textbook QM notation and abstracted
functions ( dim, %*%, %x%, -> ) borrowed from the R language.
Example 3 shows how to define a word which will execute the corresponding
quantum circuit on an arbitrary input quantum state for 2-qubits. Only
basis states are shown in the example, however superposition states, both
entangled and factorable, can equally well be input to the circuit. I
need to implement a few missing functions before general superposition
states can be created easily by the user, using the supplied notation.
Please use the latest zmatrix.4th library module (also linked below) -- I
found and fixed a bug in }}ZTRANSPOSE today.
Krishna Myneni
https://github.com/mynenik/kForth-32/blob/master/forth-src/qm/qcsim.4th
https://github.com/mynenik/kForth-32/blob/master/forth-src/fsl/extras/
zmatrix.4th
Krishna Myneni
Nov 8, 2019, 7:36:27 PM11/8/19
to
On Fri, 08 Nov 2019 02:50:20 +0000, Krishna Myneni wrote:
> ... There is a little infrastructure to add for building up
> n-qubit gates, ...
https://github.com/mynenik/kForth-32/blob/master/forth-src/qm/qcsim.4th
https://github.com/mynenik/kForth-32/blob/master/forth-src/fsl/extras/
zmatrix.4th
Words to generate conditional 2-qubit gates and swap gates within an n-
qubit circuit have been added along with a few other changes. The code is
now becoming useful for n > 2 quantum circuits. Example 4 shows the Forth
code for making a composite gate for a 3-qubit QFT circuit. I won't
reproduce the circuit diagram here (it will be mangled by proportional
spacing), but the qcsim.4th language allows it to be written as
2 gate U2CS01 0 1 S 2 U_c U2CS01 -> \ Controlled-phase gate
3 gate U3QFT \ 3-qubit gate for full circuit
H I1 %x%
U2CS01 swap %*% \ 2-qubit gate at 1 for q1,q2
I1 %x% \ transform to 3-qubit gate
0 2 T 3 U_c swap %*%
I1 H %x% I1 %x% swap %*% \ 3-qubit gate at 2
I1 U2CS01 %x% swap %*%
I2 H %x% swap %*%
0 2 3 U_sw swap %*%
U3QFT ->
It looks sort of like an assembly language description of the circuit.
The final result is the gate U3QFT which is an 8x8 complex matrix
describing the transformation of a 2^3 complex vector (the 3 qubit input
state) to create an output state. This matrix may be output to the
console by
U3QFT q.
You may want to ask yourself why an 8-column vector is needed to
represent the state of 3 qubits -- why not 2*n = 6, or just n=3 elements
to define the input state? The answer to this question is fundamental to
understanding entanglement.
Please see the link above to view the ascii picture of the circuit, to
understand the connection between the code above and the circuit. There
is also an Exercise at the end of the file, depicting another 3-qubit
circuit. The exercise is to compose a gate, similar to the one above,
corresponding to the picture. There is not just one unique way to code
the circuit.
Krishna Myneni
> ... There is a little infrastructure to add for building up
> n-qubit gates, ...
https://github.com/mynenik/kForth-32/blob/master/forth-src/qm/qcsim.4th
https://github.com/mynenik/kForth-32/blob/master/forth-src/fsl/extras/
zmatrix.4th
qubit circuit have been added along with a few other changes. The code is
now becoming useful for n > 2 quantum circuits. Example 4 shows the Forth
code for making a composite gate for a 3-qubit QFT circuit. I won't
reproduce the circuit diagram here (it will be mangled by proportional
spacing), but the qcsim.4th language allows it to be written as
2 gate U2CS01 0 1 S 2 U_c U2CS01 -> \ Controlled-phase gate
3 gate U3QFT \ 3-qubit gate for full circuit
H I1 %x%
U2CS01 swap %*% \ 2-qubit gate at 1 for q1,q2
I1 %x% \ transform to 3-qubit gate
0 2 T 3 U_c swap %*%
I1 H %x% I1 %x% swap %*% \ 3-qubit gate at 2
I1 U2CS01 %x% swap %*%
I2 H %x% swap %*%
0 2 3 U_sw swap %*%
U3QFT ->
It looks sort of like an assembly language description of the circuit.
The final result is the gate U3QFT which is an 8x8 complex matrix
describing the transformation of a 2^3 complex vector (the 3 qubit input
state) to create an output state. This matrix may be output to the
console by
U3QFT q.
You may want to ask yourself why an 8-column vector is needed to
represent the state of 3 qubits -- why not 2*n = 6, or just n=3 elements
to define the input state? The answer to this question is fundamental to
understanding entanglement.
Please see the link above to view the ascii picture of the circuit, to
understand the connection between the code above and the circuit. There
is also an Exercise at the end of the file, depicting another 3-qubit
circuit. The exercise is to compose a gate, similar to the one above,
corresponding to the picture. There is not just one unique way to code
the circuit.
Krishna Myneni
Krishna Myneni
Nov 8, 2019, 7:39:21 PM11/8/19
to
On Sat, 09 Nov 2019 00:36:25 +0000, Krishna Myneni wrote:
...
...
> There is also an Exercise at the end of the file, depicting another
> 3-qubit circuit. The exercise is to compose a gate ...
Incidentally, the Exercise example is from Ref. 1 of qcsim.4th:
1. Quantum computation and Quantum Information, M. A. Nielsen
and I. L. Chuang, Cambridge University Press, 2000.
KM
Krishna Myneni
Nov 20, 2019, 12:05:48 AM11/20/19
to
On Sun, 03 Nov 2019 15:06:57 +0000, Krishna Myneni wrote:
> I have developed the following DSL specification for doing simulations
> of a few-qubit (n < 6) quantum circuits in a Forth environment. ...
Some interesting specs below from the Supplementary Information to
Google's Nature paper. Google has their own classical computing
simulation of a quantum circuit. Not too surprisingly, their program is
named "qsim", and they also have another program called "qsimh".
The qsim program can run a 38-qubit wide quantum circuit simulation with
a depth of hundreds of gates within a couple of hours on one of their
Google Cloud nodes (n1-ultramem-160) with the following specs:
4 CPUs with 20 cores/CPU
3844 GB RAM
single precision fp arithmetic
AVX/FMA vectorization instructions
OpenMP multi-threading
Since a 38-qubit quantum state requires a representation involving 2^38
complex numbers, the state vector itself must take up over 2 TB of memory
(at single precision). The matrix representations for the gate operations
must be highly compressed, i.e. not expanded into the full dimensions --
it will be interesting to look at the algorithms if their code is open
source.
My Forth program, qcsim.4th, uses straightforward full matrix
representation for the gates, which is very inefficient both
computationally and for storage at low gate depth. There must be a clever
trick to representing the gates at lower dimension even as the number of
qubits being entangled increases. In any event, the purpose of qcsim.4th
is pedagogical, and with adequate allocation of memory will probably run
satisfactorily for n=8 qubits, although I haven't tested it beyond n=5.
qcsim.4th appears to be working correctly, based on a self-consistency
check of the fidelity benchmark defined in the paper. Since the program
performs a double-precision calculation of a quantum circuit with no gate
or readout errors, the fidelity of the output state should be very close
to one after averaging over a number of random circuits, but not exactly
one, for small n, per their definition. I can detect this difference in
my calculations. Some other tests can be performed on the output
probability distributions.
Krishna Myneni
Alex McDonald
Dec 6, 2019, 8:56:10 AM12/6/19
to
On 03-Nov-19 15:06, Krishna Myneni wrote:
> I have developed the following DSL specification for doing simulations of
> a few-qubit (n < 6) quantum circuits in a Forth environment. Much of this
> has already been implemented and some of it has been tested. Some work
> still needs to be done (implementation of Kronecker outer products and
> measurement of quantum states, but it is straightforward, if tedious).
>
> Examples for simulating simple quantum circuits are given below (Warning:
> the formatting may become mangled by Google groups):
>
<snip>
> I have developed the following DSL specification for doing simulations of
> a few-qubit (n < 6) quantum circuits in a Forth environment. Much of this
> has already been implemented and some of it has been tested. Some work
> still needs to be done (implementation of Kronecker outer products and
> measurement of quantum states, but it is straightforward, if tedious).
>
> Examples for simulating simple quantum circuits are given below (Warning:
> the formatting may become mangled by Google groups):
>
>
> I expect to post an initial version of qcsim.4th in a few days.
>
> Krishna Myneni
>
https://aws.amazon.com/braket/ that (to quote)
is a fully managed service that helps you get started with quantum
computing by providing a development environment to explore and design
quantum algorithms, test them on simulated quantum computers, and run
them on your choice of different quantum hardware technologies.
--
Alex
Krishna Myneni
Dec 6, 2019, 9:17:35 PM12/6/19
to
the Quantum Computing "business" also. It seems to be something of a
badge for a deep-pocket businesses to show that they have the resources
to do it -- I imagine it's not cheap to set up actual quantum computers,
much less to run them on an on-demand basis!
My interest in writing qcsim.4th was to better understand Google's recent
result. And I've accomplished that to my satisfaction. If I want to
explore quantum algorithms and simulate them on a conventional computer,
I would probably develop qcsim.4th further to make it more efficient for
handling a larger number of qubits. Right now, I don't feel a need to do
that.
The qcsim.4th program, as it stands now, can be used to set up a fairly
large number of one and two-qubit gate operations for a small number of
qubits (for n=5 the computation time isn't bad). It demonstrates that
random circuits can give highly non-uniform probability distributions for
the output bitstrings, one of the key features to understand how Google
is able to infer the fidelity of their 53-qubit wide, 20 gate-cycle deep
computation.
Krishna
0 new messages