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
132 stars 35 forks source link

Make comparison gates use 4 * N T-gates to compare and 0 T-gates to uncompute using MBUC #235

Open tanujkhattar opened 1 year ago

tanujkhattar commented 1 year ago

We can use Craig's out of place adder to compute using 4 * N T-gates and uncompute using 0 T-gates as described in https://arxiv.org/pdf/1709.06648.pdf.

fdmalone commented 1 year ago

We have this adder from #213.

NoureldinYosri commented 1 year ago

comparison gates generally need 8N T when comparing two qubit registers, the 8N comes from MBUC since without MBUC they will take 16N.

When comparing a qubit register to a classical number this can be reduced to 6N with logarithmic depth or 4N with linear depth.

I implemented the 8N general compartor in #211 and the 4N quantum-classical comparator in #117 and I explain the differences between these decompositions and how I got the 4N decomposition (which doesn't exist in literature) in #236

mpharrigan commented 2 months ago

Is this done?

NoureldinYosri commented 2 months ago

not completly, some comparison gates use 4T others use 8T. I will send a couple of PR to address this