Completing the non-Clifford capabilities [$800]

[Krastanov]

Bug bounty logistic details (click to expand)

To claim exclusive time to work on this bounty either post a comment here or message [email protected] with:

• your name
• github username
• (optional) a brief list of previous pertinent projects you have engaged in

If you want to, you can work on this project without making a claim, however claims are encouraged to give you and other contributors peace of mind. Whoever has made a claim takes precedence when solutions are considered.

You can always propose your own funded project, if you would like to contribute something of value that is not yet covered by an official bounty.

The project is claimed by @Fe-r-oz until Sep 10th 2024.

Project: Completing the non-Clifford capabilities [$800]

This library already has some nascent capabilities to represent non-Clifford states as a weighted sum of tableaux states. Such a representation is useful in settings where there is a small number of non-Clifford gates in a mostly Clifford circuit. The cost is still exponential in the number of non-Clifford gates, but manageable. We have simple state representation and gate application already done, expect is nearly implemented in this PR, and project! still needs to be implemented. To obtain this bounty, the aforementioned features need to be completed, well tested, and well documented.

Required skills: Understanding of the Stabilizer formalism and decompositions of arbitrary states in terms of Pauli channels

Reviewer: Stefan Krastanov

Duration: 2 months

Publication: In the next 2 years we plan to release a paper in a selective journal about this software. Contributing to this issue would deserve a co-authorship status on such a paper (if the contributor so desires)

Payout procedure:

The Funding for these bounties comes from the National Science Foundation and from the NSF Center for Quantum Networks. The payouts are managed by the NumFOCUS foundation and processed in bulk once every two months. If you live in a country in which NumFOCUS can make payments, you can participate in this bounty program.

Click here for more details about the bug bounty program.

[Fe-r-oz]

I checked out Ted's paper some time ago, which seems very exciting. Your initial work on non-Clifford is also quite cool about generalized stabilizer.

Therefore, I will be delighted to work on this as that will teach me more about non-Clifford functionalities.

Also, there is a question I wanted to ask you: is non-Clifford the same as non-stabilizer/non-stabilizerness? In some papers, they use the term non-stabilizerness (when they refer to magic, they call it a non-stabilizerness)

[Krastanov]

Sounds good! Happy to reserve this bounty for you for the next two months.

Yes, the terms you mentioned are frequently used interchangeably.

[Fe-r-oz]

Overall progress on Non-Clifford functionalities are divided into the following parts: 1) implementing the basic TODOs, 2) fixing bug in expect, 3) implement project 4) providing user rich experience by having implemented most APIs from #260
to push them asap after this issue 5) Overall documentation 6) scaffolding for future non-cliff functionality/APIs.

1. noncliff: improvements to apply! and dictvaltype #346
2. noncliff: fixes expect #348
3. noncliff: fix JET errors #362
4. [non-Clifford] In-place Pauli measurements (projectrand!) for GeneralizedStabilizer with expanded test suite #427
5. noncliff: improve error handling in apply!(sm, pcT) #374
6. noncliff: introducing inverse sparsity Λ(χ) and Λ(ϕᵢⱼ) #376
7. noncliff: improve performance of _allthreesumtozero #377
8. noncliff: enhanced error message for inapplicable Project! of GeneralizedStabilizer #416
9. noncliff: Documentation for overview of Generalized Stabilizer Representation #409
10. noncliff: scaffolding for projectrand! for GeneralizedStabilizer #420
11. Inconsistencies in projection tests for Stabilizer/MixedDestabilizer states using multi-qubit random_stabilizers and multi random_paulis #418
12. Opened an issue about md ⊗ S"X" in StackOverflowError in tensor products involving some AbstractStabilizer types #339. #PR Type promotion between MixedDestabilizer, Stabilizer and others, also used in ⊗ #354
13. To fully utilize non-clifford functionality, there are important API that are necessary to work with sm which are in PR improvements to GeneralizedStabilizer API #260. Atm, I have also completed 5 of them. So, they can the easily added to provide rich non-clifford functionality as soon as possible. Thus, PR implement sm⊗sm, tHadamard*sm, pcT⊗P"X" , pcT*tId1 , P"-Y"*sm and copy(sm) from #260  #345 implements sm⊗sm, tHadamard*sm, pcT⊗P"X" , pcT*tId1 , P"-Y"*sm and copy(sm). Outputs of these tasks: implement sm⊗sm, tHadamard*sm, pcT⊗P"X" , pcT*tId1 , P"-Y"*sm and copy(sm) from #260 #316 (comment)
14. To realize embed for sm, Adding embed for AbstractStabilizer and Tableau #342 that provided embedding for Tableau and Stabilizer
15. Also, we need for base.zero operators for MixedDeStabilizer , Destabilizer, MixedStabilizer, they will be helpful for later use. Even size(md)[1], or size(md)[2] gives error atm. I have fixed them, but didn't push the PR yet.

[Krastanov]

@Fe-r-oz , what is the status of your work on this bounty? I see you have done a lot of quality of life improvements and additions to tests (certainly useful!). Among the actual main components of the work, I see you have finished expect (probably the most important completed part of the work).

It seems projectrand! is the main component left -- without it, the smaller "quality of life" improvements are not as useful. And it seems projectrand! has been the main "difficult" or "substantial" component. Could you focus on it so that we can wrap up the bounty? The work left after this is done would be much easier and more straightforward in comparison.

[Krastanov]

Note that this was reserved in July to be done by September. While you have been doing great work, I am not very comfortable keeping a bounty reserved while you are working on other bounties. I am not in any way suggesting this should be re-opened as a bounty and I am certainly appreciative of the many projects you have undertaken. I just want to make sure that it is easy for others to engage with this particular bounty if you have grown less interested in it (given your awesome contributions in many other areas)

[Fe-r-oz]

Thank you for the feedback. Currently, only projectrand! remains to be completed. I’ve updated the tests in line with your comments in PR #355 today, confirming that result1 or result2 yield a zero matrix in stabilizer state projections using GeneralizedStabilizer for single-qubit Pauli operators, which suggests that the approach is on the right track. The tests have also been updated to use random_stabilizer/pauli for this specific case.

Additionally, smaller work includes informative error message for the project! function today, drawing from your insights in #355. This updated message is reflected in PR #416 and incorporates both your suggestions from #355 and relevant details about pauli measurement from the associated paper with general documentation in #409. I hope we can integrate these improvements as well.

I plan to implement projectrand! by November 10th, 2024, by utilizing the density matrix update χ′, which is calculated using χ′=expect(p,genstab) and the corresponding probability defined by prob=(real(χ′)+1)/2. I hope to provide a valuable foundation via projectrand! for testing the consistency of multi-qubit, non-stabilizer operations by this date to facilitate future developments.

[Fe-r-oz]

Hi Stefan, I wanted to provide you with an update on the bounty.

Edit: Thank you very much for your feedback. I am currently working on #427, which aims to deliver a proper implementation of the Pauli measurement algorithm as outlined in Algorithm 2. It should be ready for review soon.

In #355, we demonstrate that multi-qubit non-stabilizer circuits, incorporating non-Clifford gates at randomized positions, can be probabilistically projected through repeated trials. These findings align with Ted's concluding observation that "no magic state will be simulatable through every stabilizer circuit" particularly given the assumption that BQP is larger than BPP. Ted also raised an unresolved question: "What conditions are both necessary and sufficient for determining the set of quantum states (magic states) that can be simulated through stabilizer circuits?"

In addition, as an example, attached is the .txt file showing the results of applying a randomized 3-qubit non-Clifford gate to a stabilizer circuit for multi-qubit projection. The results demonstrate that the post-measurement complex density matrices match the expected outcomes (printed as TRUE), supporting Ted's comment that we can simulate some 'magic' states using the stabilizer-defined basis. However, not all 'magic' states are simulatable in this way (printed as FALSE), as noted by Ted. These specific results have been reproduced via reproducible 2 from #355 (comment). PFA: 3_qubit_ncgate_results.txt.

Tests for a probabilistic non-stabilizer simulator have been added, evaluating up to 10 qubits with random non-Clifford gates at randomized positions. This message serves as a brief summary of the findings.

I look forward to hearing your thoughts. Thank you!

Future prospects: The paper Unbiased Simulation of Near-Clifford Quantum Circuits echoes similar insights as mentioned in Ted's one of concluding paragaph. Given that the dynamics of a general quantum system fall within the complexity class BQP, a scalable method for simulating universal quantum circuits on a classical computer is highly unlikely. This paper addresses the simulation of stabilizer circuits with non-stabilizer errors by representing these errors as quasiprobability distributions over stabilizer operations. The authors present a new method for simulating arbitrary quantum circuits that combines the efficiency of stabilizer propagation with Monte Carlo sampling via stabilizer channel decomposition.

Edit, Edit:

The mermaid diagram illustrates the limitations of the Generalized Stabilizer, as highlighted by Ted.

graph TD
    A[Limitations of the Generalized Stabilizer]
    A --> B[""No magic state will be simulatable through every stabilizer circuit""]
    A --> C[""What set of quantum states can be simulated efficiently through every stabilizer circuit? What conditions are both necessary and sufficient is unresolved""]

Loading

[Fe-r-oz]

Thank you for your feedback during the previous review.

Last week, I implemented the Pauli measurement algorithm for projectrand! in PR #427. I look forward to your review. Thanks!