CQ Quantum Compiler

A compiler for CQ, a hybrid classical-quantum programming language. CQ programs contain classical computations (int, float, cbit) that control quantum operations (qbit). The compiler evaluates away classical parts at compile time via partial evaluation, then synthesizes the remaining quantum operations into elementary hardware gates.

Compilation Pipeline

CQ source  ->  Parse  ->  Type Check  ->  Partial Evaluate  ->  Flatten  ->  Synthesize
                                            (remove classical)   (unique    (elementary
                                                                  names)     gate set)

Output: A flat quantum program using only the elementary gate set {X, SX, CX, RZ, measure}.

Quick Start

make install    # Set up virtual environment and install

# Full compilation pipeline
.venv/bin/python -m CQ.cq_cli synth CQ/initialize.cq --static 'a=[0.5,0.3,0.1,0.1]'
.venv/bin/python -m CQ.cq_cli synth CQ/qft2.cq --static 'd=3'

# Individual stages
.venv/bin/python -m CQ.cq_cli check CQ/initialize.cq          # Type-check only
.venv/bin/python -m CQ.cq_cli pe CQ/qft2.cq --static 'd=3'   # Partial evaluation
.venv/bin/qc '1 + 2 * cos(pi)'                                 # Expression evaluator

# Run all tests
make test

CLI Commands

Command	Description
qc EXPR	Evaluate a CQ expression
cq_cli check FILE	Type-check a CQ program
cq_cli exec FILE	Type-check and display reconstructed source
cq_cli pe FILE --static 'VAR=VAL'	Partial evaluation with static inputs
cq_cli synth FILE --static 'VAR=VAL'	Full pipeline: PE + flatten + synthesis

Project Structure

CQ/
  lark/expression.lark     # Expression grammar (PEMDAS precedence)
  lark/CQ.lark             # Full CQ language grammar
  helpers.py               # AST helpers, evaluation primitives
  interpreter.py           # Expression evaluator + constant elimination
  type_checker.py          # Type checker (multi-procedure, procedure calls)
  show.py                  # AST pretty-printer
  partial_eval.py          # Partial evaluator (classical computation removal)
  flatten.py               # Scope flattening (unique variable naming)
  vars.py                  # Liveness analysis (read/write variable sets)
  synthesis.py             # Gate synthesis to elementary gates
  cq_cli.py                # CLI entry point
  initialize.cq            # 2-qubit initialization test program
  qft.cq / qft2.cq        # Quantum Fourier Transform test programs
tests/                     # Unit tests
weeks/                     # Weekly course materials and READMEs

Weekly Breakdown

Each week's folder contains a README with concepts covered and instructions for running that week's code.

• Week 2 - Expression parser and interpreter (Lark, PEMDAS, eval_exp)
• Week 3 - CQ grammar and type checker (statements, declarations, quantum ops)
• Week 4 - Variables, constant elimination, procedure call type checking
• Week 5 - Partial evaluation (classical computation removal)
• Week 6 - Gate synthesis (elementary gate decomposition)

The CQ Language

CQ is a C-like imperative language with four types:

• Classical: int, float, cbit
• Quantum: qbit

Quantum operations include gates (H, Rx, Ry, Rz, P, not), controlled gates (gate target if ctrl), swaps (lval <> lval), and measurements (measure qbit -> cbit).

Example program:

initialize_2qubit(float a[4], qbit q[2])
{
    float th1 = 2*arccos(sqrt(a[0]*a[0] + a[2]*a[2]));
    float th2 = 2*arctan2(a[3],a[1]);
    float th3 = 2*arctan2(a[2],a[0]);

    Ry(th1) q[0];
    Ry(th2) q[1] if q[0];
    not q[0];
    Ry(th3) q[1] if q[0];
    not q[0];
}

Running Tests

make test
# or directly:
.venv/bin/python -m unittest discover -s tests -v