Krastanov
commented
2 months ago That would be a nice check to implement. I imagine the symplecticinverse does not match the same conventions as enumerate_cliffords. E.g. there are places where an integer has to be represented as bits or where a submatrix needs to be created. In such places, if one does not follow the same conventions, the inverse will not work correctly. E.g. are integers little or big endian, are submatrices inserted in the left or right corner of a bigger matrix, are symplectic matrices represented as a big block-diagonal matrix with just 4 quardrants or a matrix made out of many small 2x2 matrices.
Fe-r-oz
Describe the bug 🐞
enumerate_clifford_slow(n, i, ;...)gives a canonical mapping from integer to symplectic groupSp(2n). This algorithm is based on generalized Gram-Schmidt orthogonalization procedure (see section B Symplection Gram-Schmidt and II. A for details of this algorithm from this paper).The same paper provides a useful correctness check in form of the
SYMPLECTICinverse(n, gn)algorithm which provides an inverse map, meaning indexing a given group element.SYMPLECTICinverse(n, gn)requiresnandgnwheregnis returned bySymplecticImproved.See the additional context for more details.I am working on the PR towards the
SymplecticImproved O(n³)algorithm following Stefan's instructions from #11. For correctness sake, I implemented theSymplecticImprovednearly as exactly as possible (1) from the paper itself since I was not satisfied with just theJuqst.jl's implementation (2). There are a few minor differences between (2)'s implementation and the pseudocode in the paper, so for safety sake, it was better to not just rely onJuqst.jlwithout testing it first.For these two approaches (1, 2) , this test should pass as it serve as a correctness check:
This test passes for both of these two approaches (1, 2):
It is noted that for these two approaches (1, 2) this works for
n > 2.Expected behavior
For all the values of
n>2that obey Symplectic cardinality, these should hold true forenumerate_clifford_slow(n, i, ;...):@test QuantumClifford.symplecticinverse(stab_to_gf2(tab(QuantumClifford.enumerate_cliffords_slow(n, i, onlycoset=false)))) == iI also had a look at
test_enumerate.jlbut I didn't find tests forenumerate_cliffords_slow. I think we should add a similar test as forenumerate_cliffords_slowafter it becomes bug-free. In the meantime, I will polish the PR and soon submit it for further discussion and link to this issue. I am sharing a conceptual MRE that I am getting locally as (2) can be referenced for existing implementation.Note: We are only interested in symplectic cardinality as the authors designed algorithms that return ith element from symplectic cardinality. That's why
onlycoset=false, see the doctest inenumeration.jlfor more details. Also, under the hood,onlycoset=falseby default forenumerate_clifford_slow(n, i, ;...)for this reason as well.Minimal Reproducible Example 👇
Error & Stacktrace or other complete output produced by the MRE ⚠️
Even for a few random cases, the above test does not hold:
Environment (please complete the following information):
- Output of
using Pkg; Pkg.status()- Output of
using Pkg; Pkg.status(; mode = PKGMODE_MANIFEST)- Output of
versioninfo()Additional context
SymplecticImproved(i, n) O(n³)note: WIP. PR soon to be submitted.
And this test passes:
Symplectic(n, i)O(n⁴) algorithmIn order to relate with
enumerate_cliffords_slowPedagogical Detail: O(n⁴) and O(n³) algorithms provided in the paper provide different canonical mapping as acknowelged in the paper. Also,
ncan be deduced fromgn. Thus,gnis only parameter needed forSYMPLECTICinverse.