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

Idiomatic addition circuit #983

Open mpharrigan opened 2 months ago

mpharrigan commented 2 months ago

This is a proof of principle, re: #957

image

There's really no problem working with 5,000+-bit bloqs (and their decomposition) if they're written with a bit of care.

It's an incredibly simplifying assumption that we can expect to be able to do one level of decomposition without blowing our runtime/performance budget

mpharrigan commented 2 months ago

(this bloq is a proof of principle I whipped up quickly. It would need to be integrated into the existing addition bloq. It's missing the first- and last-bit carry eliminations and the final cnots)

fdmalone commented 2 months ago

What's the issue with the existing adder? In my defense this is a holdover from very early cirq_ft so I'm totally on board with improving it

mpharrigan commented 2 months ago

Tanuj said decomposing a 5000 bit Add takes 2 minutes. For me, it just crashes my machine with a recursion depth exceeded

mpharrigan commented 2 months ago

The timing information is inaccurate in my original post. I need to time the whole cell. It's 1.03s (715ms without the binst graph part)