This is a package we found useful while developing Yao.jl, it stays inside Yao.jl for more than half a year, it takes an important role in making Yao a high performance quantum simulator, and we decided to move it to an extern package recently to let more people use it easily.
We provide several useful tools when you need deal with eigen vectors in linear space marked with bits, e.g on a quantum computer with qubits model, we use |00\cdots 00\rangle, \dots |11\cdots 11\rangle to represent the eigen vectors in its hilbert space.
Moreover, other people work on spins, bits etc. may find this useful as well. e.g to represent a set of spins one can use this representation and have to do some similar manipulations on it as well.
We provide high performance, elegant bit manipulation tools in BitBasis, which includes:
- linear space basis iterator: itercontrol, reorder
- high performance mask based methods
- bit manipulation functions (start with
b) like breflect, btruncate, swapbits etc.
- bit string literals, supports most of the methods above, while supporting some sugars as well, e.g it will automatically do the indexing conversion when you use it for matrix/vector indexing
This package is currently in beta, for feature request and bug reports please feel free to open issue for us!
9 Likes
On a related note, I made a similar repository (unregistered) called PrimitiveBits.jl. It’s a demo prototype for the bits types used in my spin algebra packages DirectSum.jl and Grassmann.jl.
On a related note, I also implemented something related for small bitmapped graphs (poc: https://github.com/chethega/BitmapGraphs).
I have a feeling that a good low-level package for statically sized (ie bitstype) bitstrings/bitsets/bitarrays is missing. Most things are trivial, but there are a handful of features that take a little thought and it would be nice to have a single package that does everything right:
- fast iteration over set bits (using blsr+tzcnt instructions)
- fast permutation and extraction (using pext instruction where available)
- proper mutation (needs to do pointer arithmetic to mutate the backing
NTuple, replicate part of MArray)
- proper boundscheck elision and hoisting
- proper scaling beyond 640 bit (
ntuple is only fast up to 10 elements)
- possibly proper downscaling to smaller integer sizes than 64 bit
- fast reverse iteration (using lzcnt and shift)
- fast lexicographic and reverse lexicographic comparison operators
- proper testing that everything vectorizes correctly (somebody needs to read the generated assembly)
None of these are extremely complicated, but it would be nice to consolidate that work. Then downstream users (like the quantum or grassman or graphs people) could just include or fork the low-level base and bolt on their domain-specific preferred api.
4 Likes
Agree with that, maybe we could start a repo and work on things above?
Some of the functions in the BitBasis is checked with generated asm. Some are not (e.g the iterator, is too complicated).
But I do agree, this is something people will use and create over and over again. (I’ve been written similar things in different situation for many times as well)
Although I agree it would be useful to make a package that does all that (and I wouldnt mind participating the creation), personally I would not actually use that package in any of my existing code.
I am very happy with creating the exact custom code needed for my bits types separately for each specific application I code. I experimented with the idea mentioned using my PrimitiveBits package, but I came to the conclusion that I dont want to use a package like that for my purposes, although I’d like to help make one.
If an excellent solution is derived, i will consider switching to it. Until then, i would only consider it an intellectual exercise.