Skip to content

GUIDELINE.md

Latest commit

 

History

History
277 lines (209 loc) · 11 KB

GUIDELINE.md

File metadata and controls

277 lines (209 loc) · 11 KB
Raw

GUIDELINE.md

Working conventions for the QPrize project. Both humans and Claude instances should follow these when contributing.

Attempt Files

  • Every attempt lives in attempts/attempt_NNN[letter]_YYYY-MM-DD_HHMM.py
    • NNN = zero-padded attempt number; letter suffix (B, C, ...) = refinement of same idea
    • YYYY-MM-DD_HHMM = actual creation date and time (use date +%Y-%m-%d_%H%M)
    • Example: attempt_004_2026-03-29_1507.py
  • Every attempt file must:
    • Have a header comment explaining what changed and why (vs previous attempt)
    • Export solve(num_bits: int) -> int that synthesizes + executes + returns recovered d
    • Call play_ending_sound() when finished
    • Use timed() context managers around slow steps
    • After synthesis, save two files to attempts/results/ (create dir if needed):
      1. attempt_NNN_<bits>bit.qprog — raw Classiq circuit via qprog.save(path)
      2. attempt_NNN_<bits>bit_meta.json — human-readable summary (see format below)
  • After verifying an attempt works, append it to attempts/registry.py (never edit past entries)
  • Add a row to attempts/RESULTS.md for each synthesis run with: attempt name, bits, qubit width, circuit depth, CX count, success, and legitimacy
  • Never delete or modify old attempt files

Results table (attempts/RESULTS.md)

Append one row per synthesis run (not per attempt file). Columns:

Attempt Bits Width Depth CX Success Legitimacy
attempt_004_2026-03-29_1507 4 11 ... 716 ✅ group enum
  • Width = number of qubits (from GeneratedCircuit.data.width)
  • Depth = circuit depth (from GeneratedCircuit.data.depth)
  • CX = two-qubit gate count (from GeneratedCircuit.data.transpiled_circuit.count_ops["cx"] or equivalent)
  • Success = ✅ if solve() returned the correct d, ❌ otherwise
  • Legitimacy = shortcuts that would not work at cryptographic scale. Use these tags (comma-separate multiples):
    • d in oracle — d appears directly in circuit constants; circuit is a tautology, not ECDLP
    • group enum — oracle constants derived by enumerating all n EC group elements; O(n) work, infeasible for cryptographic n
    • lookup inverse — modular inverse via lookup table of size p; O(p) memory, infeasible for cryptographic p
    • ✅ none — no known shortcuts; would scale to cryptographic sizes

The _meta.json file must be a plain JSON object with at minimum:

{
  "attempt": "attempt_008_2026-03-29_1859",
  "bits": 4,
  "qubits": 28,
  "depth": 1050,
  "cx": 716,
  "gate_counts": {"cx": 716, "u3": 120, ...},
  "decoded_d": 6,
  "expected_d": 6,
  "success": true
}

Write this file immediately after synthesis (before execution) for qubits/depth/cx/gate_counts, then update decoded_d/success after execution. Or write once at the end with all fields.

PLAN.md

PLAN.md is the strategic document. Keep it up to date:

  • When a task is completed, move it from "TODO" to "done" or update the attempt history table
  • When a new idea is discovered (from papers, experiments, failures), add it under the appropriate priority section
  • Note qubit/CX counts and status (Simulator / Hardware / Failed) for each attempt
  • The multi-agent coordination note at the top should remain; multiple Claude instances read it

Work Log

All session activity is documented in worklog/. Each session creates one file:

  • Filename: worklog/YYYY-MM-DD_HHMM_[who].md (e.g. worklog/2026-03-29_1200_dor.md)
  • Format: bullet list of what was done, ideas explored, decisions made, failed attempts, and open questions
  • A new session should read the latest worklog file first to pick up where the previous session left off
  • Also append a one-liner summary to log.txt in the root (append-only, never edit past entries)

Template for a worklog entry:

# Session YYYY-MM-DD HH:MM — [who]

## Done
- ...

## Failed / Abandoned
- ...

## Open questions / Next steps
- ...

Code Structure

Root folder — keep organized

  • consts.py — curve parameters only, no circuit code
  • utils.py — shared utilities (timed, play_ending_sound)
  • ecc.py — classical EC arithmetic helpers (for testing/reference)
  • attempts/ — attempt files + registry
  • worklog/ — session logs
  • PLAN.md — strategic plan and attempt history
  • GUIDELINE.md — this file
  • research.md — paper notes and optimization ideas
  • test_*.py — pytest test files
  • code_review.md — latest agent code review output

Do not clutter the root with scratch files, temp outputs, or one-off scripts.

Attempt file structure

# attempt_NNN — YYYY-MM-DD HH:MM
# CHANGE: ...
# WHY: ...
# (optional: RESULT: ...)

import ...
from consts import PARAMS
from utils import timed, play_ending_sound

def solve(num_bits: int) -> int:
    ...
    play_ending_sound()
    return d

if __name__ == "__main__":
    # Quick smoke test
    result = solve(4)
    print(result)

Classiq conventions

  • The Classiq entry-point @qfunc must be named main
  • Define main inside solve() so it captures local constants via closure
  • Use @qperm for reversible helpers (no mid-circuit measurement), @qfunc for the top-level
  • Lambda capture in loops: use default argument lambda x=val: f(x) not bare lambda: f(val) where val changes in the loop
  • allocate(size, signed, fraction_digits, reg) — use fraction_digits=size for fractional QNum (values in [0,1)), use fraction_digits=0 for integer QNum
  • free(reg) is required for any register allocated inside a @qperm but not returned

⚡ Strong suggestion: split main into three named sub-functions

The core bottleneck is the group addition oracle, not the Hadamard or QFT layers. To keep focus there and avoid conflating unrelated parts of the circuit, split main into three clearly named helpers and have main call them in order:

@qfunc
def prepare_superposition(x1: Output[QArray[QBit]], x2: Output[QArray[QBit]]) -> None:
    """Allocate and Hadamard the two QPE registers."""
    allocate(var_len, x1)
    allocate(var_len, x2)
    hadamard_transform(x1)
    hadamard_transform(x2)

@qfunc   # (or @qperm if reversible)
def group_add_oracle(
    x1: QArray[QBit],
    x2: QArray[QBit],
    ecp: Output[...],
) -> None:
    """The group addition oracle — ecp = P0 + x1*G - x2*Q. This is the hard part."""
    ...

@qfunc
def extract_phase(x1: QArray[QBit], x2: QArray[QBit]) -> None:
    """Inverse QFT to extract the period."""
    invert(lambda: qft(x1))
    invert(lambda: qft(x2))

@qfunc
def main(x1: Output[QArray[QBit]], x2: Output[QArray[QBit]], ecp: Output[...]) -> None:
    prepare_superposition(x1, x2)
    group_add_oracle(x1, x2, ecp)
    extract_phase(x1, x2)

Why: Every attempt optimizes group_add_oracle. Keeping it isolated makes it easy to swap implementations, compare CX counts, and avoids accidentally touching the Hadamard or QFT layers when experimenting with the oracle.

Post-processing convention

The oracle is: ecp = P0 + x1*G - x2*Q

Peak condition after inverse QFT: m1*d + m2 ≡ 0 (mod n)

Standard post-processing (attempt_004+):

x1_r = round(x1_measured * n) % n   # frequency m1
x2_r = round(x2_measured * n) % n   # frequency m2
# filter: gcd(x1_r, n) == 1
d = (-x2_r * pow(x1_r, -1, n)) % n

Note: The reference Classiq notebook uses d = -x1_r * x2_r^{-1} which is only correct for their degenerate test case (d=n-1). For the competition curves (d≠n-1), use the formula above.

Git Workflow

  • Always git pull --rebase before git push
  • Multiple Claude instances may be running in parallel on different machines; git is the coordination mechanism
  • Check log.txt and recent worklog/ files after pulling to catch up on parallel work
  • Commit message format: short imperative, no "Co-Authored-By" trailers

Genuine ECDLP vs. the Scalar-Encoding Flaw

The flaw (attempts 002B, 003, 004-1600, 005)

These attempts use scalar-index encoding: EC group elements are stored as integers in Z_n (the scalar index k, where the element equals k·G). The oracle then computes:

negq_steps[i] = (n − scalar_index(2^i · Q)) % n

But scalar_index(Q) = d — the secret itself. Even deriving it "indirectly" via a brute-force point_to_index enumeration still means d is solved classically before the quantum circuit runs. The quantum step is then redundant.

The quantum circuit computes x1 − x2·d (mod n) — arithmetic in Z_n, not EC arithmetic.

The genuine approach (attempt 004-1507, 006+)

The oracle register must hold EC coordinates (x, y) ∈ F_p × F_p. Precomputed classical constants must be EC points derivable from G and Q without knowing d:

g_powers[i]      = 2^i · G     (doublings of G — uses only G)
neg_q_powers[i]  = −(2^i · Q)  (doublings of Q, negate y — uses only Q as a point)

The quantum circuit applies controlled EC point additions (slope formula mod p). d is never used anywhere in circuit construction.

Rule

The oracle must never use params.d. Allowed inputs: params.G, params.Q, params.p, params.n, params.a, params.b.

If you find yourself computing (n − d) % n, looking up d in a lookup table, or using point_to_index to convert Q to a scalar, the attempt is NOT genuine ECDLP.

What NOT to do

  • Do not hardcode d into circuit constants (circular — defeats the purpose of ECDLP)
  • Do not use params.d in the oracle; only use params.G, params.Q, params.n, params.p, params.a, params.b
  • Do not use scalar-index encoding for the oracle register (see "Genuine ECDLP" section above)
  • Do not run git push without pulling first
  • Do not edit past entries in registry.py or log.txt
  • Do not add Co-Authored-By to commit messages
  • Do not use the full venv path (e.g. /path/to/venv/bin/python); activate the venv first

Scalability requirement

The oracle must be scalable to large key sizes.

What is NOT scalable

Attempts 002–006 use "group-index encoding": the quantum register holds a scalar k meaning the point k·G. Deriving the oracle constant for Q = d·G requires enumerating all n group elements:

for k in range(n):
    point_to_index[k * G] = k  # O(n) = O(2^bits) work

For small competition sizes (n ≤ ~10^6) this is feasible, but for real cryptographic sizes (n ≈ 2^256) it is completely infeasible. This does NOT constitute a scalable quantum algorithm.

What is scalable

Classical precomputation must be polynomial in the key length — e.g., O(var_len) EC doublings to compute [G, 2G, 4G, ...] and [-Q, -2Q, -4Q, ...].

The quantum oracle itself may be designed in many ways — coordinate-based EC arithmetic, novel encodings, or recent algorithmic improvements (e.g., https://eprint.iacr.org/2025/1887.pdf) — as long as the circuit size grows polynomially with the key size.

Reference paper: https://inria.hal.science/hal-04848612v1/document (Chevignard, Fouque, Schrottenloher 2025 — qubit reduction via truncated output and Ekerå-Håstad sampling)