-
Notifications
You must be signed in to change notification settings - Fork 49
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
enumerate_cliffords_slow(n, i, ;...)
does not follow the same ordering convention as the original paper
#343
Comments
That would be a nice check to implement. I imagine the |
enumerate_cliffords_slow(n, i, ;...)
enumerate_cliffords_slow(n, i, ;...)
does not follow the same convention as the original paper
enumerate_cliffords_slow(n, i, ;...)
does not follow the same convention as the original paperenumerate_cliffords_slow(n, i, ;...)
does not follow the same ordering convention as the original paper
Thank you. Your insight is really helpful. I will be more careful and ponder about this. I did noticed that The Pedagogical details/ Additional Context The following is not done/implemented in the paper per se but authors talk about circuit compilation: I have yet to check whether after this, does I think the overgoal is circuit compilation that you point out in Also, in #13, this paper also have one algorithm (Algorithm |
Short answer: No, it would not work. I may not have raised a good question, but I felt compelled to provide an answer. This question seems irrelavant to the present discussion. Additional Context If I am not mistaken, by 4 quadrants, you refer to the 4 submatrices of the Aaronsom/Gottesman tableau. These is done by two functions by
Thus, only the complete pesudocode in the paper and 'some' part of P.S. This comment is not directly helpful to the discussion which is related to symplectic matrices. This is because I am checking the outcomes of some steps required for proceeding into circuit compilation. |
To do the correctness check you need to implement |
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)
requiresn
andgn
wheregn
is 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 theSymplecticImproved
nearly 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.jl
without 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>2
that 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)))) == i
I also had a look at
test_enumerate.jl
but I didn't find tests forenumerate_cliffords_slow
. I think we should add a similar test as forenumerate_cliffords_slow
after 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.jl
for more details. Also, under the hood,onlycoset=false
by 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()
QuantumClifford v0.9.9
- Output of
using Pkg; Pkg.status(; mode = PKGMODE_MANIFEST)
QuantumClifford v0.9.9
- 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_slow
Pedagogical Detail:
O(n⁴) and O(n³) algorithms provided in the paper provide different canonical mapping as acknowelged in the paper. Also,
n
can be deduced fromgn
. Thus,gn
is only parameter needed forSYMPLECTICinverse
.The text was updated successfully, but these errors were encountered: