Roger:

• Implementation
• Unit test
• Documentation

Leo:

• Interface design and system testing
• Theoretical back support
• Scheduling

• delete fall back method for dispatch!

This make people make mistakes easily cause apply! has actually side-effects.

Controlled gates could be implemented in a more efficient way. We will discuss how to implement it here. #2

Cache is used for storing intermediate variables to speed up calculation. (This is python)

if (cache is favored and block is cached) and (parameters == cached parameters):
    apply(cached linear operator, psi)
else:
    if cache is favored:
        calculate sparse_matrix
        cache!(block, parameters, sparse_matrix)
        apply sparse matrix to psi
    else:
        if block has children:
            dispatch paramters to children
        else:
            apply(block, parameters, psi)

A block has its favored data format, such as 'sparse', 'function' and 'mpo', only sparse and mpo allow caching.
Caching is needed only if this matrix can be used multiple times.

e.g. a block consist of a queue of Controlled-Z gates, the sparse matrix representation is diagonal, caching the constructed sparse matrix can be super efficient for future use.

In v0.3 we will move some part out of this repo to improve CI time and precompile time. Also this will benefit other projects in the Julia ecosystem to re-use our utility. And on the other hand we will add some more features.

This issue will track what we will do next

Make Yao a meta package

• create a base package
• separate block system
• separate registers
• integrate with CUDA

We will drop v0.6 support

see #117

original with will be deleted

see #113

Hygine problem should be solved now

see #57

Derive some new packages from Yao

• move LuxurySparse as a Julia package and add to deps
• move Yao.Zoo to an extension package QuAlgorithmZoo, we will eventually implement (not in v0.3) some more algorithms described by Quantum Algorithm Zoo in this package with utilities above.

Derive new parts in Yao

• move some blocks out of Yao.Blocks to be an extension package of in a new module Contrib.Extension. This a standard extension including the following blocks:
  • Roller
  • What else?

The other extensions in Contrib should take this as an example.

Deprecation fix

• Block system
  • Primitive Blocks
  • Composite Blocks
  • I/O
• Registers
• Interfaces

The following could be in separated package in the future (to be decided)

• some part of the Block system
• LuxurySparse
• QuAlgorithmZoo

New features

QASM support

Since QASM has been wildly supported by various projects, we will also support lowering our block tree structure to QASM. This will requires two feature

• dumping to QASM from block tree
• parse QASM strings to block tree (this may not be supported in v0.3, I guess)

Time evolution support

See #41 This is currently developing by @GiggleLiu , we will discuss whether this goes inYaoStdExt with other part of the Block system or not.

Tensor network based acceleration (could be in v0.3)

Tensor network algorithms can be used to accelerate certain kind of circuit.

Parallized batched registers

See #13. This was an early request of parallelism, which is quite useful when you need to run the circuit for multiple times.

Any suggestions?

By packing contiguous memory address together, Concentrator could be more efficient. (Less permutation operations on shape).

Currently, the mechanism is:

• if input is a UnitRange, this range of address will be processed as a contiguous quantum memory address.
• if input is a Int or Vector{Int}, this range of address will be processed as an in-contiguous quantum memory address.

We suppose that if a user inputs UnitRange, then it knows which part is contiguous, therefore there is no contiguous check for UnitRange, and we directly pack an address start from the start of UnitRange and has length length(::UnitRange).

However, currently solution can not handle the following conditions:
[1, 6, 5, 4, 2, 3], where [6, 5, 4] is actually contiguous, but if the input is 4:6, it will cause an error.

• prepare demos: GHZ, QCBM
• prepare introduction of the framework
• setup some notebooks to run demos
• polish examples
• plot benchmarks
• plot circuit diagrams

Commit

Commit should use the following sytax:

Topic: commit message

You should squash similar commits together using git rebase:

1. git rebase -i HEAD~N N is the number of commits you want to squash
2. squash what commits by following the instructions from git
3. use a force push by

git push origin YOUR_BRANCH -f

Developing

You should open a new branch to add what you want and then create a Pull Request. DO NOT directly push your commits to master, you may break the CI.

• use key(obj::MatrixBlock) as the only required interface to cache server.
• remove/modify similar/hash/== for KronBlock.
• make copy shallow copy.

There are still some kind of gates need to be polished.

• Hadamard gate: since entries Hadamard gate are +-1, using general single gate apply! is not efficient.
• Efficient General Matrix: except some special matrice, mat now uses kron to generate matrices, which is slow. Efficient general mat is straight forward for mul-site gate exploiting general apply!.

Proposal on supporting QASM

QASM is a widely used format for describing a quantum circuit or a sequence of quantum operations.
Since our block tree is a higher format of quantum circuit, to interact with other libraries (e.g import old projects into Yao, export block trees to hardware, etc.) supporting QASM will give Yao this ability.

Related work

openqasm
scaffcc-python
rust-QASM
Quantum

Method

Lowering Block Tree to QASM

The block tree have already contain complete information about a quantum circuit. Simply lowering the composite blocks to a single sequence should be easy.

Parsing QASM back to Block Tree

TO BE DONE

The tag name "v0.1" is not of the appropriate SemVer form (vX.Y.Z).
cc: @Roger-luo

since we will track our optimization from now, I will open this issue for enable micro benchmarks in CI with PkgBenchmark

Benchmarks in the docs needed, and should contain:

1. a figure in png form plots Yao and ProjectQ together
2. show the versioninfo() of Julia. And the __version__ variable of ProjectQ.
3. explain some possible cause of the difference.

We leave batch dimension in the default implementation of register: Register. But its related interface and method is not defined yet. This issue is for the discussion related to the implementation of batch.

@GiggleLiu To avoid this kind of bug (#125 ) happen again and to keep a frequent update of various new algorithms, I think we can move the examples (maybe just some of them, or just all of them) to QuAlgorithmZoo.jl and keep update that repo with new algorithms and demos in notebooks like QAOA and HHL and etc.

check their repo, it looks nice:

https://github.com/JuliaDiffEq
https://github.com/qojulia

They separated examples (or other instances) to different repo, then you can update and fix them more frequently without worrying about it is not in CI.

There are some breaking changes from v0.7, we should drop the old version and start supporting the first long time support Julia release in v0.2.

We should wait for this PR:

JuliaCI/PkgBenchmark.jl#68

The benchmark should include:

• micro benchmark for each block
• benchmark for each method for each register

Context is useful for operations like focus

Proposal

use @with to provide context environment for operations on a register. e.g

reg1 = register(bit"0000")

# in place context
@with reg1 focus=[1, 2] begin
     chain(2, kron(1=>X), repeat(Y))
end

prototype

@with reg1 [configs] begin
    # blocks
end

function pip |> cannot indicates side effects of blocks, and with is too complex. We should remove these two first in v0.2. And add something better when we are able to.

This issue is for listing what shoud be support in the first version.

A list of gates for performance benchmark

1. simple gates: Gs

   • X(5)
   • H(5)
   • Rx(5)
   • U2(5, 6)

2. control gates, for g in Gs

   • C(3) g
   • C(1) C(2) NC(3) X(5)

3. multiple gates

   • X(1) X(2) X(3) X(4)
   • H(1) H(2) H(3) H(4)
   • X(3) Y(4) Z(5) [C(1) Z(6)]
   • X(3) Rx(4) Y(5)

4. Grover Block

   • 2|psi><psi|-1

5. TimeEvolution

   • Exp(-iHt)

Data Representations

• X, Y on single qubit/multiple qubits -> PermuteMultiply
• Z on single qubit/multiple qubits -> Diagonal
• H on single qubit -> SparseMatrixCSC
• single and multiple Control on gate G -> typeof(G), push performance for CNOT, CZ gates.
• TimeEvolution, use expmv.

 N == nqubits(r) || throw(QubitMismatchError("register Size $(nactive(r)) mismatch with block size $N"))

This cause focused registers not working when there is a PutBlock.

My Julia version is Julia0.6.4. I tried to run the QCBM.ipynb example directly. And the following codes invokes an method error.

optim = Adam(lr=0.1)
his = train!(circuit, pg, optim, niter=50, learning_rate=0.1)
plot(1:50, his, xlabel="iteration", ylabel="loss")

The error message is

MethodError: Cannot convert an object of type IterTools.Chain{NTuple{186,Float64}} to an object of type Int64
This may have arisen from a call to the constructor Int64(...),
since type constructors fall back to convert methods.
Stacktrace:
[1] update!(::IterTools.Chain{NTuple{186,Float64}}, ::Array{Float64,1}, ::Adam) at ./In[28]:16
[2] #train!#16(::Float64, ::Int64, ::Function, ::Yao.Blocks.ChainBlock{6,Complex{Float64}}, ::Array{Float64,1}, ::Adam) at ./In[29]:15
[3] (::#kw##train!)(::Array{Any,1}, ::#train!, ::Yao.Blocks.ChainBlock{6,Complex{Float64}}, ::Array{Float64,1}, ::Adam) at ./:0

It would be great help if this is fixed. Great works!

branch math, src/Core/ folder.

Task list

1. add kron methods for a new kind of Sparse Matrix: PermuteMultiply
   https://github.com/JuliaLang/julia/blob/master/stdlib/SparseArrays/src/sparsematrix.jl

2. add construction of more gates

   • arbitrary single/multiple qubit dense gate.
   • controled gates.
     see projectq for reference
     https://github.com/ProjectQ-Framework/ProjectQ/tree/develop/projectq/backends/_sim

3. add benchmarks for gate construction using new method and kron method, see time elapse and memory allocation.

Tools for new comers

• vs code + julia plugin + vim plugin
• jupyer notebook: Pkg.add("IJulia")

Choose a piece of code from current proejct,

• It can be run indepedantly, and its functionallity is clear.
• well structured documentation containing
  • math equation
  • example
• reflect multiple dispatch and type tree
• reflect functional progamming, especially currying that will be frequently used in our programm.

Using Bars-and-Stripes 3x3 depth = 10 circuit,

Register is something contains a quantum states. Since a quantum state of N qubits is actually a rank-N tensor. All quantum registers supports the interface of julia arrays.

To preserve memory contiguous, we use the last dimension as our batch dimension. An naive implementation could be

struct Register{M, B, T, N} <: AbstractRegister{M, B, T, N}
    data::Array{T, N}
end

where M is the number of qubits, and B is the number of batches.

Register this package in METADATA.jl (and also rename it before registration). Candidates will be listed in this issue.

For inference, we need

• Grover Block
• Dagger operation

For QAOA, we need

• TimeEvolution gate

What did I miss?

julia> using Yao
[ Info: Precompiling Yao [5872b779-8223-5990-8dd0-5abbb0748c8c]
WARNING: could not import Base.ctranspose into LuxurySparse
WARNING: could not import LinearAlgebra.ctranspose! into LuxurySparse
ERROR: LoadError: LoadError: LoadError: UndefVarError: RowVector not defined
Stacktrace:
[1] top-level scope at none:0
[2] include at .\boot.jl:317 [inlined]
[3] include_relative(::Module, ::String) at .\loading.jl:1038
[4] include at .\sysimg.jl:29 [inlined]
[5] include(::String) at C:\Users\309726.julia\packages\Yao\ZJlWg\src\LuxurySparse\LuxurySparse.jl:1
[6] top-level scope at none:0
[7] include at .\boot.jl:317 [inlined]
[8] include_relative(::Module, ::String) at .\loading.jl:1038
[9] include at .\sysimg.jl:29 [inlined]
[10] include(::String) at C:\Users\309726.julia\packages\Yao\ZJlWg\src\Yao.jl:8
[11] top-level scope at none:0
[12] include at .\boot.jl:317 [inlined]
[13] include_relative(::Module, ::String) at .\loading.jl:1038
[14] include(::Module, ::String) at .\sysimg.jl:29
[15] top-level scope at none:2
[16] eval at .\boot.jl:319 [inlined]
[17] eval(::Expr) at .\client.jl:389
[18] top-level scope at .\none:3
in expression starting at C:\Users\309726.julia\packages\Yao\ZJlWg\src\LuxurySparse\linalg.jl:29
in expression starting at C:\Users\309726.julia\packages\Yao\ZJlWg\src\LuxurySparse\LuxurySparse.jl:25
in expression starting at C:\Users\309726.julia\packages\Yao\ZJlWg\src\Yao.jl:37
ERROR: Failed to precompile Yao [5872b779-8223-5990-8dd0-5abbb0748c8c] to C:\Users\309726.julia\compiled\v1.0\Yao\TDiQQ.ji.
Stacktrace:
[1] error(::String) at .\error.jl:33
[2] macro expansion at .\logging.jl:313 [inlined]
[3] compilecache(::Base.PkgId, ::String) at .\loading.jl:1184
[4] macro expansion at .\logging.jl:311 [inlined]
[5] _require(::Base.PkgId) at .\loading.jl:941
[6] require(::Base.PkgId) at .\loading.jl:852
[7] macro expansion at .\logging.jl:311 [inlined]
[8] require(::Module, ::Symbol) at .\loading.jl:834

• roll(position::Vector{Int}, gates::Vector{Gate}), roller with gates on specific positions.
• MatBlock{N, T}(matrix::Matrix), used in phase estimation.
• FuncBlock{N, T}(func::Function), to fit the MatBlock.
• IBlock{N, T}, the gate of doing nothing.
• apply!(reg, block::ControlBlock{MatBlock}), apply register on controlled large block directly.

use on and on! to represent operations without side effect on regsiters and in place operations on a register. A demo will looks like

# in place
chain(4, kron(1=>X), kron(3=>Y)) |> on!(register(bit"0000"))

# without side-effect
chain(4, kron(1=>X), kron(3=>Y)) |> on(register(bit"0000"))

We will use the matrix product order in chain rather than the gate order in a circuit diagram. (which is reversed), e.g

chain(4, kron(1=>X), kron(3=>Y)) |> on!(register(bit"0000"))
# equals to
kron(4, 3=>Y) |> on!(register(bit"0000"))
kron(4, 1=>X) |> on!(register(bit"0000"))

Available inputs

Blocks

on!(register) can take a block

kron(4, 1=>X) |> on!(register)

lazy constructors

lazy constructors for blocks that requires an integer (number of active qubits). This is because
the information about active qubits is contained in registers, we should be able get it directly from a register.

kron(1=>X) |> on!(register)

Basic Block use a general method to evaluate a quantum circuit. It is not efficient but it will work.

See:

https://github.com/QuantumBFS/QuCircuit.jl/blob/block/blueprint/circuit_protocal.md

Batched registers can be parallelized on the last dimension (batch dimension).

For CPU arrays, there is two options:

• use SharedArray to parallel it among process, which will allow us to process between nodes on a Julia sever
• use thread in stdlib, this may have less overhead, but it won't run on multiple CPU nodes

Block

• A block is a function unit, like Arbituary rotation, Entangler, FFT, Grover search et. al.
• A block contains a list of blocks/gates, thus forming a tree that terminates on gates (leaves).
• A block does not have qubit indices to specify which qubits apply. However, a gate has, its indices are relative to its parent block. Block operation space is specified using the focus system described bellow.

Focus

A wave function is a tensor of order-3, psi(f, r, b).

• f: focused dimensions
• r: remaining dimensions
• b: batch dimension.

All blocks must be applied on the first (focused) dimension. Here, benchmark is needed to optimize the memory structure based.

Focus is a special "gate", users use it to change focused qubits to perform operations, like Focus(4, 0, 1) will change operation basis to lines (4, 0, 1) by index unraveling and permuting, i.e. for a 5-bit system, we will have psi((4, 0, 1), (2, 3), b). After this "gate", all blocks must be size 3, until another focus "gate" applied. Uses can use Focus() to restore the state to default all focus mode.

For un-blocked gates, we don't require the alignment of focused bits and gate operation space.

refactor ConstantGate.jl to a safer implementation with @eval macro. use gensym for constant bindings.

Basic gates are basic elements in a quantum circuit, the following definitions is from PHYS4071

However, we will implement a more general phase gates with a theta as its parameter, S and T gates will be a specific instance of such phase gate.

Single Qubit

• Pauli Gates: X, Y, Z
• Phase Gates: S, T (pi/8 gate)
• Rotation Gates: Rx, Ry, Rz

Two Qubits

Control Gates

• Controlled NOT: CNOT
• Controlled Gate

Blocks

Blocks are conbination of multiple gates on multiple qubits.

• QFT Block
• Rotation Block
• Time Evolution

• bounds check
• use UnitRange for multi-qubits blocks

The tag name "0.1.2" is not of the appropriate SemVer form (vX.Y.Z).
cc: @Roger-luo

To expose the batch loop outside the whole circuit abstraction, we should let batch_view return a subtype of AbstractRegister, which will be SubRegister, it is similar to SubArray. it has similar behavior with Register{M, 1}

struct SubRegister
    state_view::SubArray
    lines::Vector{Int}
end