Qualtran icon indicating copy to clipboard operation
Qualtran copied to clipboard

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

Open tanujkhattar opened this issue 1 year ago • 6 comments

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.

tanujkhattar avatar May 23 '23 09:05 tanujkhattar

We have this adder from #213.

fdmalone avatar May 23 '23 17:05 fdmalone

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

NoureldinYosri avatar Jun 06 '23 07:06 NoureldinYosri

Is this done?

mpharrigan avatar May 01 '24 18:05 mpharrigan

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

NoureldinYosri avatar May 02 '24 17:05 NoureldinYosri

Is this done now?

mpharrigan avatar Aug 08 '24 15:08 mpharrigan

not all of them .. some comparison bloqs use the n log n decomposition

NoureldinYosri avatar Aug 08 '24 17:08 NoureldinYosri