import native_harness
import argparse
import cmath
import copy
import hashlib
import json
import math
from pathlib import Path
import subprocess
import tempfile
from test_lean_interference import ROOT, literal, execute, h
from test_lean_qft import template
from test_lean_qft_graph import case as graph_case, body_literal
FIXTURE = ROOT / "tests/fixtures/lean_qpe_instrument"
def base(n, m, provider=7):
return dict(n=n, m=m, provider=provider, powers=[(k, provider, 2**k, True) for k in range(m)],
initial=[False]*m, preparation=[h(k) for k in range(m)], graph=graph_case(m))
def suite():
cases = [(f"n{n}-m{m}", base(n, m), True) for n in range(1, 9) for m in range(1, 9)]
original = base(2, 3)
def mutation(name, change):
item = copy.deepcopy(original)
change(item)
cases.append((name, item, False))
for parameter in ("n", "m"):
for value in (0, 9, 1000000):
mutation(f"{parameter}-{value}", lambda c, p=parameter, v=value: c.update({f"request_{p}": v}))
mutation("wrong-provider", lambda c: c.update(request_provider=8))
mutation("dirty-precision", lambda c: c["initial"].__setitem__(0, True))
mutation("missing-zero", lambda c: c["initial"].pop())
mutation("missing-h", lambda c: c["preparation"].pop())
mutation("wrong-h-axis", lambda c: c["preparation"].__setitem__(1, h(0)))
mutation("extra-scalar-phase", lambda c: c["preparation"].append(("p", [(1, [])])))
mutation("reversed-power-order", lambda c: c["powers"].reverse())
for field, value in ((0, 0), (1, 8), (2, 0), (2, 3), (3, False)):
def change(c, f=field, v=value):
row=list(c["powers"][1]);row[f]=v;c["powers"][1]=tuple(row)
mutation(f"power-field-{field}-{value}", change)
mutation("missing-power", lambda c: c["powers"].pop())
header = "Qpe.header 2 3"
changes = {
"forward-qft": "orientation := .forward",
"reverse-measurement": "measurementAxes := [4,3,2]",
"aliased-precision-axis": "precisionAxes := [0,3,4]",
"wrong-target-axis": "targetAxes := [1,0]",
"aliased-owner": "precisionOwner := 0",
"wrong-target-owner": "targetOwner := 1",
"measure-target": "targetExit := .measure",
"discard-target": "targetExit := .discard",
"unitary-effect": "effect := .unitary",
"classical-input": "classicalInputs := [.bits 1]",
"wrong-classical-width": "classicalOutputs := [.bits 2]",
"cbit-not-cbits": "classicalOutputs := [.bit]",
"drop-target-output": "outputs := []",
"extra-bits0-owner": "outputs := QftGraph.interface 2 ++ [⟨[.bits 0],[]⟩]",
"tuple-not-bits": "inputs := [⟨[.tuple 2,.bit,.bit],[0,1]⟩]",
}
for name, field in changes.items():
mutation(name, lambda c, f=field: c.update(header="{ " + header + " with " + f + " }"))
def graph_phase(c):
node=next(n for n in c["graph"]["nodes"] if n["kind"]=="gate" and n["gate"][0]=="p")
node["gate"]=("p",[(192,node["gate"][1][0][1])])
mutation("wrong-qft-phase", graph_phase)
mutation("dangling-qft-entry", lambda c: c["graph"].update(entry=999))
mutation("wrong-qft-type", lambda c: c["graph"]["nodes"][0].update(
signature="{ QftGraph.boundary 3 with inputs := [⟨[.tuple 3,.bit,.bit,.bit],[0,1,2]⟩] }"))
return cases
def plan_literal(item):
n,m=item["n"],item["m"]
nodes=[]
for node in item["graph"]["nodes"]:
nodes.append("⟨"+node.get("signature",f"QftGraph.boundary {m}")+", "+body_literal(node,m)+"⟩")
powers="["+",".join(f"⟨{k},{p},{count},{str(polarity).lower()}⟩" for k,p,count,polarity in item["powers"])+"]"
plan="⟨"+item.get("header",f"Qpe.header {n} {m}")+", "+json.dumps(item["initial"])+", "+literal(item["preparation"])+", "+powers+", ["+",".join(nodes)+f'], {item["graph"]["entry"]}⟩'
return f'({item.get("request_n",n)}, {item.get("request_m",m)}, {item.get("request_provider",item["provider"])}, {plan})'
def schema_cases():
rows=[]
qpe='⟨"qpe-instrument/1",1,[2,3,7],.qpe schemaBase⟩'
qft='⟨"qft-dyadic8/1",1,[3],.qft schemaBase.fourier schemaBase.fourierEntry⟩'
powers='⟨"controlled-power/1",1,[3,7],.power ⟨0,7,8,true⟩⟩'
for name,request,proposal in [('qpe','.qpe 2 3 7',qpe),('qft','.qft 3',qft),
('powers','.power 3 7',powers)]:
rows.append((name,request,proposal,True))
for label,update in [('unknown','rule := "unknown/1"'),
('version','rule := "'+{'qft':'qft-dyadic8','qpe':'qpe-instrument',
'powers':'controlled-power'}[name]+'/2"'),
('declaration','rule := "Qleisli.Qpe.accepted_plan"'),
('template-zero','templateVersion := 0'),
('template-next','templateVersion := 2'),
('missing-parameters','parameters := []'),
('extra-parameter','parameters := '+({'qpe':'[2,3,7,0]',
'qft':'[3,0]','powers':'[3,7,0]'}[name]))]:
rows.append((name+'-'+label,request,'{ ('+proposal+' : Schema.Proposal) with '+update+' }',False))
rows += [('qpe-wrong-precision','.qpe 2 2 7',qpe,False),
('qpe-wrong-provider','.qpe 2 3 8',qpe,False),
('qpe-qft-witness','.qpe 2 3 7','{ ('+qpe+' : Schema.Proposal) with witness := .qft schemaBase.fourier schemaBase.fourierEntry }',False),
('qft-qpe-witness','.qft 3','{ ('+qft+' : Schema.Proposal) with witness := .qpe schemaBase }',False),
('powers-qpe-witness','.power 3 7','{ ('+powers+' : Schema.Proposal) with witness := .qpe schemaBase }',False)]
for provider,accepted in [(4294967295,True),(4294967296,False)]:
rows.append(('provider-'+str(provider),f'.power 0 {provider}',
f'⟨"controlled-power/1",1,[0,{provider}],.power ⟨0,{provider},1,true⟩⟩',accepted))
for exponent,count,accepted in [(0,1,True),(12,4096,True),(13,8192,False),
(1000000,0,False),(3,0,False),(3,7,False)]:
rows.append((f'power-{exponent}-{count}',f'.power {exponent} 7',
f'⟨"controlled-power/1",1,[{exponent},7],.power ⟨0,7,{count},true⟩⟩',accepted))
for name,stage in [('axis','⟨1,7,8,true⟩'),('polarity','⟨0,7,8,false⟩'),
('provider','⟨0,8,8,true⟩')]:
rows.append(('power-'+name,'.power 3 7',
'⟨"controlled-power/1",1,[3,7],.power '+stage+'⟩',False))
return rows
def native(cases, log):
with tempfile.TemporaryDirectory(prefix="qleisli-qpe-native-") as directory:
project=Path(directory)
rows=[plan_literal(item) for _,item,_ in cases]
schemas=schema_cases()
schema_rows=[f'({request}, {proposal})' for _,request,proposal,_ in schemas]
(project/"Main.lean").write_text('''import QleisliKernel.Schema
open QleisliKernel
set_option maxRecDepth 100000
set_option maxHeartbeats 8000000
def cases : List (Nat × Nat × Nat × Qpe.Plan) := [
'''+",\n".join(rows)+''']
def schemaBase : Qpe.Plan := (show Nat × Nat × Nat × Qpe.Plan from '''+plan_literal(base(2,3))+''').2.2.2
def schemaCases : List (Schema.Request × Schema.Proposal) := [
'''+",\n".join(schema_rows)+''']
def bits (value : Nat) : Interference.Bits := fun i => value / 2^i % 2 == 1
def operation (n provider : Nat) (state : Nat × Nat) : Nat × Nat :=
((state.1+1) % 2^n, (state.2 + provider*3 + state.1*5) % 256)
def main : IO Unit := do
for (n,m,provider,plan) in cases do
let proposal : Schema.Proposal := ⟨"qpe-instrument/1",1,[n,m,provider],.qpe plan⟩
match Schema.check (.qpe n m provider) proposal with
| some (.qpe receipt) =>
let mut line := toString receipt.stats.nodes ++ "," ++ toString (ControlledPowers.maximumUses plan.powers)
for control in List.range (2^m) do
let x := (control*3+1) % 2^n
let result := ControlledPowers.run (operation n) (bits control) plan.powers (x,5)
let prepared := PathSum.runFrom plan.preparation (bits control) Uniform.zero
let output := (List.range m).foldl (fun n i => n + if prepared.bits i then 2^i else 0) 0
line := line ++ "#" ++ String.intercalate "," ([result.1,result.2,
ControlledPowers.selectedUses plan.powers (bits control),output,prepared.phase,prepared.hadamards].map toString)
IO.println line
| _ => IO.println "reject"
for (request,proposal) in schemaCases do
IO.println ("schema:" ++ toString (Schema.check request proposal).isSome)
''')
binary = native_harness.build(project, log)
run=subprocess.run([str(binary)],capture_output=True,text=True,timeout=30)
log.append(dict(command=["qpe-test"],exit=run.returncode,stderr=run.stderr,executable_sha256=hashlib.sha256(binary.read_bytes()).hexdigest()))
assert run.returncode==0,run.stderr
lines=run.stdout.splitlines();assert len(lines)==len(cases)+len(schemas)
for (name,_,_,accepted),line in zip(schemas,lines[len(cases):]):
assert line=="schema:"+str(accepted).lower(),(name,line,accepted)
comparisons=0
for (name,item,accepted),line in zip(cases,lines):
assert (line!="reject")==accepted,(name,line)
if not accepted: continue
n,m,p=item["n"],item["m"],item["provider"]
fields=line.split("#");nodes,uses=map(int,fields[0].split(","))
assert nodes==len(item["graph"]["nodes"]) and uses==2**m-1
assert len(fields)==1+2**m
for control,field in enumerate(fields[1:]):
x,phase=(control*3+1)%2**n,5
for k,target,count,polarity in item["powers"]:
if bool(control&(1<<k))==polarity:
for _ in range(count):
phase=(phase+target*3+x*5)%256;x=(x+1)%2**n
expected=(x,phase,control,control,0,m)
assert tuple(map(int,field.split(",")))==expected,(name,control,field,expected)
comparisons+=1
return dict(native_decisions=len(cases),accepted=sum(c[2] for c in cases),
controlled_path_comparisons=comparisons,preparation_paths=comparisons,
largest_target_calls=255,kernel_dense_dimension=0,
schema_decisions=len(schemas),schema_accepted=sum(row[3] for row in schemas),
schema_results=[dict(name=name,accepted=accepted) for name,_,_,accepted in schemas],
decisions=[dict(name=n,accepted=a) for n,_,a in cases])
def eye(n): return [[complex(i==j) for j in range(n)] for i in range(n)]
def multiply(a,b): return [[sum(a[i][k]*b[k][j] for k in range(len(b))) for j in range(len(b[0]))] for i in range(len(a))]
def adjoint(a): return [[a[j][i].conjugate() for j in range(len(a))] for i in range(len(a[0]))]
def max_error(a,b): return max(abs(x-y) for row,other in zip(a,b) for x,y in zip(row,other))
def expected_kraus(U,m):
d,M=len(U),2**m
powers=[eye(d)]
for _ in range(1,M):powers.append(multiply(U,powers[-1]))
return [[[sum(cmath.exp(-2j*math.pi*j*y/M)*powers[j][a][b] for j in range(M))/M
for b in range(d)] for a in range(d)] for y in range(M)]
def literal_kraus(U,m):
d,M=len(U),2**m;n=d.bit_length()-1
result=[[[0j]*d for _ in range(d)] for _ in range(M)]
inverse=[(kind,data if kind=="h" else [((-ticks)%256,axes) for ticks,axes in data])
for kind,data in reversed(template(m))]
reverse=lambda x:int(f"{x:0{m}b}"[::-1],2)
for column in range(d):
state=[0j]*(M*d);state[M*column]=1
state=execute([h(k) for k in range(m)],state,m+n)
for k in range(m):
for _ in range(2**k):
next_state=list(state)
for p in range(M):
if p&(1<<k):
for a in range(d):
next_state[p+M*a]=sum(U[a][b]*state[p+M*b] for b in range(d))
state=next_state
state=[state[reverse(p)+M*a] for a in range(d) for p in range(M)]
state=execute(inverse,state,m+n)
for y in range(M):
for a in range(d): result[y][a][column]=state[y+M*a]
return result
def with_reference(K,r=2):
d=len(K)
return [[K[a//r][b//r] if a%r==b%r else 0j for b in range(d*r)] for a in range(d*r)]
def quantum_checks():
s=1/math.sqrt(2)
H=[[s,s],[s,-s]]
def phase(ticks):return [[1,0],[0,cmath.exp(2j*math.pi*ticks/256)]]
U4=[[0j]*4 for _ in range(4)]
for x in range(4):U4[(x+1)%4][x]=cmath.exp(2j*math.pi*(7+11*x)/256)
operators=[eye(2),phase(32),phase(16),multiply(multiply(H,phase(7)),H),
[[0,cmath.exp(2j*math.pi/256)],[cmath.exp(2j*math.pi/256),0]],U4]
entries=references=0;error=0.;largest=0
for U in operators:
d=len(U)
for m in (1,2,3,4):
expected,actual=expected_kraus(U,m),literal_kraus(U,m)
largest=max(largest,2**m*d)
total=[[0j]*d for _ in range(d)]
total_trace=0j
v=[complex(i+1,(-1)**i*(i+2)) for i in range(2*d)]
scale=math.sqrt(sum(abs(x)**2 for x in v));v=[x/scale for x in v]
w=list(reversed(v))
rho=[[.6*v[i]*v[j].conjugate()+.4*w[i]*w[j].conjugate() for j in range(2*d)] for i in range(2*d)]
for A,K in zip(actual,expected):
error=max(error,max_error(A,K));entries+=d*d
gram=multiply(adjoint(A),A)
total=[[total[i][j]+gram[i][j] for j in range(d)] for i in range(d)]
Ar,Kr=with_reference(A),with_reference(K)
left=multiply(multiply(Ar,rho),adjoint(Ar))
right=multiply(multiply(Kr,rho),adjoint(Kr))
error=max(error,max_error(left,right));references+=1
total_trace+=sum(left[i][i] for i in range(2*d))
error=max(error,max_error(total,eye(d)))
error=max(error,abs(total_trace-sum(rho[i][i] for i in range(2*d))))
nonisometric=literal_kraus([[2,0],[0,2]],1)
gram0=multiply(adjoint(nonisometric[0]),nonisometric[0])
gram1=multiply(adjoint(nonisometric[1]),nonisometric[1])
total=[[gram0[i][j]+gram1[i][j] for j in range(2)] for i in range(2)]
error=max(error,max_error(total,[[2.5,0],[0,2.5]]))
assert max_error(total,eye(2))>1
complete=literal_kraus([[1,0],[0,-1]],1)
omitted=multiply(adjoint(complete[0]),complete[0])
assert max_error(omitted,eye(2))>.9
rescaled=[[[math.sqrt(2)*z for z in row] for row in K] for K in complete]
wrong0=multiply(adjoint(rescaled[0]),rescaled[0])
wrong1=multiply(adjoint(rescaled[1]),rescaled[1])
wrong=[[wrong0[i][j]+wrong1[i][j] for j in range(2)] for i in range(2)]
assert max_error(wrong,eye(2))>.9
assert error<2e-12,error
return dict(kraus_entries=entries,joint_density_branches=references,
largest_oracle_vector=largest,maximum_error=error,unitary_completeness_cases=24,
joint_trace_cases=24,completeness_counterexamples=3)
def source_check(binary,log):
K=expected_kraus([[1,0],[0,cmath.exp(1j*math.pi/4)]],2)
expected=[]
for dephased in (False,True):
distribution={}
for y in range(4):
a,b=K[y][0][0]/math.sqrt(2),K[y][1][1]/math.sqrt(2)
for r in range(2):
for t in range(2):
probability=(abs(a)**2+abs(b)**2)/4 if dephased else abs((a+(-1)**(r+t)*b)/2)**2
distribution[y+4*r+8*t]=probability
expected.append(distribution)
assert max(abs(expected[0][k]-expected[1][k]) for k in expected[0])>0.06
for name,expect in zip(("first_source","dephased"),expected):
project=FIXTURE/name;baseline=json.loads((FIXTURE/(name+"-baseline.json")).read_text())
for file,digest in baseline["source_sha256"].items():
assert hashlib.sha256((project/file).read_bytes()).hexdigest()==digest
command=[str(binary.resolve()),"run",str(project),"--format=json"]
run=subprocess.run(command,capture_output=True,text=True,timeout=30)
log.append(dict(command=command,exit=run.returncode,stdout=run.stdout,stderr=run.stderr))
assert run.returncode==0,run.stderr
actual={sum(int(bit)<<i for i,bit in enumerate(row["bits"])):row["probability"]
for row in json.loads(run.stdout)["result"]["distribution"]}
assert all(abs(actual.get(k,0)-p)<2e-12 for k,p in expect.items()),(name,actual,expect)
return dict(source_probabilities=32,off_grid_residual_coherence=True)
def main():
parser=argparse.ArgumentParser(description=__doc__)
parser.add_argument("--source-only",type=Path)
parser.add_argument("--record",type=Path)
args=parser.parse_args();log=[]
if args.source_only: report=source_check(args.source_only,log)
else:
report=native(suite(),log);report.update(quantum_checks())
report["commands"]=log
report["source_sha256"]={p:hashlib.sha256((ROOT/p).read_bytes()).hexdigest() for p in
["lean-kernel/QleisliKernel/ControlledPowers.lean","lean-kernel/QleisliKernel/Uniform.lean",
"lean-kernel/QleisliKernel/Qpe.lean","lean/Qleisli/Qpe.lean",
"lean-kernel/QleisliKernel/Schema.lean",
"lean/Qleisli/QpeComplete.lean","scripts/test_lean_qpe.py"]}
if args.record:args.record.write_text(json.dumps(report,indent=2)+"\n")
print(json.dumps({k:v for k,v in report.items() if k not in ['commands','source_sha256','decisions','schema_results']}))
if __name__=="__main__":main()