search

quantumlib / Qualtran

Qᴜᴀʟᴛʀᴀɴ is a Python library for expressing and analyzing Fault Tolerant Quantum algorithms.
https://qualtran.readthedocs.io/en/latest/
Apache License 2.0
173 stars 40 forks source link

`SelectSwapQROM` revamp and upgrades #986

Closed tanujkhattar closed 4 months ago

tanujkhattar commented 4 months ago

Fixes https://github.com/quantumlib/Qualtran/issues/108 Partially addresses https://github.com/quantumlib/Qualtran/issues/368 Fixes https://github.com/quantumlib/Qualtran/issues/78

We still need an adjoint bloq for QROMs to make the complexity for clean ancilla version match that of the paper, and I haven't implemented the optimization to save one target register from https://quantum-journal.org/papers/q-2019-12-02-208/pdf/

This PR introduces major revamp to SelectSwapQROM and some upgrades to QROM. I'll add more detailed description soon

image image

@fdmalone

mpharrigan commented 4 months ago

related #699

tanujkhattar commented 4 months ago

I've rewritten the docs on qrom base and derived classes and used the docs from base class in the notebooks for derived classes. I think we can still continue to improve the docs, but I'll go ahead and merge this for now.

fdmalone commented 2 months ago

@tanujkhattar I remember discussing this at the time, but what's the origin in the factor of 2 difference between the ceiling term when comparing Theorem 1 and 2, I think this is not related to the inverse right?

tanujkhattar commented 2 months ago

Cost for the dirty ancilla case (Theorem 1) matches the Appendix A formula (2 QROMs + 4 SwapWithZero's)

Cost for the clean ancilla case is different because we need 1) QROM + QROM.adjoint() 2) SwapWithZero + SwapWithZero.adjoint()

Our implementation assumes that the clean ancilla are freed up as part of the decomposition. In their implementation, they only count the cost of computing the table lookup; and measure the clean ancilla in X basis and keep the measurement results around as part of a deferred uncomputation strategy. Once the QROM needs to be uncomputed, these measurement results are used along with measurement based uncomputation of table lookup described in Appendix C.

Therefore, they essentially don't incur any cost for QROM.adjoint() and SwapWithZero.adjoint() -- therefore we have a 2x overhead in the total cost compared to their cost.

fdmalone commented 2 months ago

Thank you!