QuantumBFS / YaoClifford.jl

A stabilizer state backend for Yao
MIT License
5 stars 3 forks source link

Faster projective measurements #7

Open Krastanov opened 2 years ago

Krastanov commented 2 years ago

Up until 0.4.1 QuantumClifford had only a general purpose project! that assumed the projection would be on a multi-qubit Pauli string. That is unnecessary slow when measuring a single qubit. In 0.4.1 new special purpose projection functions were implemented https://github.com/Krastanov/QuantumClifford.jl/blob/v0.4.1/src/project_trace_reset.jl#L612

Before/After benchmarks for an X measurement on 100 qubits:

BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  11.882 μs …  35.537 μs  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     12.393 μs               ┊ GC (median):    0.00%
 Time  (mean ± σ):   12.533 μs ± 990.018 ns  ┊ GC (mean ± σ):  0.00% ± 0.00%

    ▄█▆▆▆█▇▆▅▂▂▁
  ▂▇████████████▇▆▅▅▄▄▃▃▃▃▂▃▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▁▂▂ ▄
  11.9 μs         Histogram: frequency by time         15.5 μs <

 Memory estimate: 14.53 KiB, allocs estimate: 411.

BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  6.472 μs …  5.871 ms  ┊ GC (min … max):  0.00% … 99.25%
 Time  (median):     6.843 μs              ┊ GC (median):     0.00%
 Time  (mean ± σ):   8.195 μs ± 81.956 μs  ┊ GC (mean ± σ):  14.05% ±  1.40%

   █▆▄▅▅▁
  ▄██████▅▄▂▂▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁ ▂
  6.47 μs        Histogram: frequency by time        11.7 μs <

 Memory estimate: 9.75 KiB, allocs estimate: 207.

This semi-related issue for a separate "circuit-like" interface might be of interest too: https://github.com/Krastanov/QuantumClifford.jl/issues/24

ChenZhao44 commented 2 years ago

Thanks for the issue! I will update it soon.