[IMPL] Add quantum programs memory layout for quantum data

[Doomsk]

Important

This issue was part of unitaryHACK26. However, it is now a regular active issue that you can still contribute.
Please read the CONTRIBUTING before proceeding.

Reference

For reference, take a look at the implementations being done on the classical side at the H-hat core implementation in Rust (please note it does not sit at the main branch).

Implementation description

Quantum programs are composed of classical and quantum instructions, depending on the capabilities the quantum device and what the quantum low-level language¹ can provide (usually, the Q3L will define the constraints for the device.) On the quantum side of things, there must be a "memory" layout for the quantum data, so each quantum type present in a quantum program is properly addressed with enough resources for it.

The layout can borrow some ideas from the classical one (via Cranelift), but there are some key differences:

• No alignment on the layout is permitted (we cannot afford wasting qubits)
• Ancilla qubits may be needed for the computation of some types upon some instructions (those defined during compilation from H-hat IR into Q3L IR)

For example, the H-hat code (Heather dialect):

type @bell_t { @s:@bool, @t:@bool }

main {
  @v:@bell_t =.{ @s=@true, @t=@false }
  @sync(@v.@s, @v.@t)
  res:bool = @v.@t * bool
  @v * i32
}

may produce an OpenQASM code:

OPENQASM 2.0;
include "qelib1.inc";

// signature of the variable @v's fields, @v.@s and @v.@t as qv_qs and qv_qt, respectively
qreg qv_qs[1];
qreg qv_qt[1];
creg res[1];

x qv_qs[0];
cx qv_qs[0], qv_qt[0];

// only the field @v.@t is cast, so we only need its measurement result
measure qv_qt -> res;

The 'memory' layout of the quantum data is done by defining the size for each data. We have a struct, @bell_t with two fields (members): @s and @t both of type @bool (primitive quantum type). The number of qubits needed for @bool is 1, so the total number of qubits used by the struct @bell_t is 2 (1 from @bell_t.@s and one from @bell_t.@t).

Note

Some quantum functions may include ancilla qubits to perform operations, so the quantum program will have them computed and properly addressed when generating the Q3L.

Memory layouts examples

Memory layouts for primitive quantum types

The number of qubits each primitive quantum type must have:

• @bool: 1
• @u2: 2
• @u3: 3
• @u4: 4
• @u8: 8

Memory layouts for quantum struct types

The number of qubits will stack according to the number of qubits its members/fields have. For instance, the example above @bell_t had 2 @bool fields, so its total number of qubits will be 2.

Nested structs follow the same rule, but needs to recursively check each member; if the member is a primitive quantum type return its value, otherwise check its value.

Memory layouts for quantum enum types

For now, only 2-variant enums are allowed for quantum enum types:

type @polarization { @V, @H }

type @side { @L, @R }

and they account for only 1 qubit. The first and second named variants are defined as |0> and |1>, respectively.

Quantum memory layout workflow

Following from the reference (a part of the compilation pass that produces the MIR²), where the types are converted into type layouts and stored in the Arena<TypeLayout>, and the memory layout for all the types is complete and stored in the LayoutCache, a quantum program instance is defined whenever a quantum variable has its cycle complete (declaration, assignment, cast). Upon casting, the relevant quantum types found in that quantum variable must be used to build the quantum memory layout and the quantum type layouts, which should be stored or accessible through a quantum program instance (feel free to define a public QuantumProgram struct for it). Those quantum type layouts will be used to compose the Q3L code (as demonstrated above with OpenQASM) and proceed on the compilation pipeline.

Primitive quantum instructions may append ancilla qubits to be included when composing the Q3L code. For now, implement a simple primitive quantum instruction type that contains an extra field with ancilla counts (as u32) and use it to calculate the quantum memory size of the quantum program. The "classical size" (or classical register) will reflect which quantum attributes were cast.

Notes

• By quantum variable we mean the root quantum object declared, ex: for @v:@bell_t =.{@s=@true, @t=@false}, @v is the quantum variable; so a quantum program represents everything that will happen under @v.
• By quantum attributes we mean the members of the quantum variable, ex: @v.@s or @v.@t.
• All the formed quantum type layouts should be stored in a more permanent place to avoid redoing work when initiating other quantum variables throughout the program.

Expected behavior

Note

Please use the branch from the reference when writing code for this issue.

• For a given quantum variable upon its cast, trigger the procedure described at the workflow
• Provide a quantum memory layout for quantum types on the quantum program
• Calculate the correct number of qubits and possible ancilla qubits from the quantum instructions

Tests

• Check the quantum memory layout for all the primitive quantum types
• Check a quantum memory layout for a simple quantum struct type
• Check a quantum memory layout for a simple quantum enum type
• Check a quantum memory layout for nested quantum struct types (can contain other structs or enums)
• Check a type transformed into a TypeLayout can be properly converted into the quantum layout
• Check the logic from TypeLayout (a primitive and a struct) and a dummy quantum instruction (choose a few values, from 0 to 3) to a QuantumProgram having all the quantum memory layout mapped out, including the quantum instructions' ancillas

Footnotes

1. Quantum low-level language (Q3L) examples: OpenQASM, NetQASM, etc. ↩

2. MIR = mid intermediate representation, where the code has a machine code-oriented structure, ready to be converted into Cranelift's IR (CLIF) or into Q3L ↩

[spital]

Hi, I am interested in working on this issue, is it free to take ?

[Doomsk]

Hey @spital thanks for the interest in this issue! You can work on it for sure.

There is no need to claim the issue and other hackers may work on it as well. We will evaluate the quality of the opened PRs and decide which one we decide to merge.

[Adithyaphani]

@Doomsk I opened a PR #134 , please review and happy to make further changes if needed