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
175 stars 44 forks source link

resource_counting.query_costs counts controlled T and controlled And as rotations #1271

Open NoureldinYosri opened 2 months ago

NoureldinYosri commented 2 months ago
In [6]: b = Add(QUInt(4)).controlled()

In [7]: query_costs(b, [QECGatesCost()])
Out[7]: 
{Controlled(subbloq=ArbitraryClifford(n=2), ctrl_spec=CtrlSpec(qdtypes=(QBit(),), cvs=(array(1),))): {QECGatesCost(): GateCounts(t=0, toffoli=0, cswap=0, and_bloq=0, clifford=0, rotation=0, measurement=0)},
 Controlled(subbloq=TGate(is_adjoint=False), ctrl_spec=CtrlSpec(qdtypes=(QBit(),), cvs=(array(1),))): {QECGatesCost(): GateCounts(t=0, toffoli=0, cswap=0, and_bloq=0, clifford=0, rotation=1, measurement=0)},
 Controlled(subbloq=And(cv1=1, cv2=1, uncompute=False), ctrl_spec=CtrlSpec(qdtypes=(QBit(),), cvs=(array(1),))): {QECGatesCost(): GateCounts(t=0, toffoli=0, cswap=0, and_bloq=0, clifford=0, rotation=4, measurement=0)},
 Controlled(subbloq=And(cv1=1, cv2=1, uncompute=True), ctrl_spec=CtrlSpec(qdtypes=(QBit(),), cvs=(array(1),))): {QECGatesCost(): GateCounts(t=0, toffoli=0, cswap=0, and_bloq=0, clifford=0, rotation=0, measurement=0)},
 Toffoli(): {QECGatesCost(): GateCounts(t=0, toffoli=1, cswap=0, and_bloq=0, clifford=0, rotation=0, measurement=0)},
 Controlled(subbloq=Add(a_dtype=QUInt(bitsize=4), b_dtype=QUInt(bitsize=4)), ctrl_spec=CtrlSpec(qdtypes=(QBit(),), cvs=(array(1),))): {QECGatesCost(): GateCounts(t=0, toffoli=15, cswap=0, and_bloq=0, clifford=0, rotation=12, measurement=0)}}

update: desired output should be no rotations for this gate ... instead a complexity based on and_bloq and/or toffoli

mpharrigan commented 2 months ago

can you describe the observed and desired behavior

NoureldinYosri commented 2 months ago

updated

mpharrigan commented 2 months ago

Got it. Add().controlled() uses the default fallback of Controlled(Add()), from which we cannot determine the resource counts. Following #1311 this will break from not being able to determine the costs for Controlled(ArbitraryClifford)) from And's call graph. With #873 , And is supposed to be a leaf bloq. Xref #1273 #1304 , And().controlled() probably shouldn't be allowed; and ergo Controlled(Add()) won't support decomposition.

Add.controlled() should return CAdd

mpharrigan commented 2 months ago

patching in #1305, the error message becomes

ValueError: Cannot control non-thru bloqs. Found Register(name='target', dtype=QBit(), _shape=(), side=<Side.LEFT: 1>) in And†
tanujkhattar commented 2 months ago

Echoing my concerns from https://github.com/quantumlib/Qualtran/issues/1304#issuecomment-2303222941

And().controlled() should be allowed IMO. In general; not being able to call bloq.controlled() for any bloq that has non-THRU registers would be a big restriction when expressing algorithms. Some bloqs where (a) RIGHT registers show up, (b) using bloq.controlled() is often desired are - QROAMClean (we often want controlled data lookups), (b) state preparation bloqs, (c) MultiControlX which is used in ReflectionUsingPrepare and uses a ladder of And gates, (d) other arithmetic bloqs like multiplication, sorting etc. which use RIGHT registers currently.

Whether we force users to implement a custom controlled bloq or we support Controlled(bloq) if bloq has non-THRU registers can be discussed; but a user not being able to do bloq.controlled() for a bloq that has non-THRU registers is very extreme IMO.

mpharrigan commented 2 months ago

And().controlled() makes sense because we can return MultiAnd. I've come around to Controlled(MultiAnd) making sense -- its decomposition is controlled versions of all the subbloqs (although this is not the most efficient construction; it's at least accurate). If we assume And becomes a leaf/atomic bloq, Controlled(And) works, but coincidentally. The tensor stuff works for atomic/leaf bloqs and returns |0> for inactive control; which matches expectations for Controlled(And) -> MultiAnd; but not in general

mpharrigan commented 2 months ago

apart from the concerns about controlling an And gate returns additional junk registers

mpharrigan commented 1 month ago

At present, this returns an error message; although the specific error message may change depending on #1304 and #1346

This is preferable to returning incorrect counts.

The real solution in this case is to override get_ctrl_system to return CAdd