A Quantum Engineering Focused Linux Distro From Scratch — Day 12

With one day left to the talks of QHack2023, I was still working on my WASM to QMASM transpiler.

I decided that I should get the partially-automated example from my thesis more automated. As I was reviewing my research I remembered that the parallelizing Fortran compiler that I took inspiration from was designed to replace methods that needed steps to be done by hand when vectorizing programs… go figure. Otherwise, the main difference between Qemu and PFC is that PFC’s idea of parallel code is vector operations and Qemu’s is constraint expressions.

In the thesis I provide an i8.mul instruction decomposed to combinational logic in terms of its binary inputs A and B.

(Spin("A5") * Spin("B5"))

(Not(Spin("A4") * Spin("B5")) + Not(Spin("A5") * Spin("B4")))

(Not(Spin("A3") * Spin("B5")) + Spin("A4") * Spin("B4") + Not(Spin("A5") *
  Spin("B3")))

(Not(Spin("A2") * Spin("B5")) + Spin("A3") * Spin("B4") + Spin("A4") * Spin("B3")
  + Not(Spin("A5") * Spin("B2")))

(Num(1) + Not(Spin("A1") * Spin("B5")) + Spin("A2") * Spin("B4") + Spin("A3") *
  Spin("B3") + Spin("A4") * Spin("B2") + Not(Spin("A5") * Spin("B1")))

(Not(Spin("A0") * Spin("B5")) + Spin("A1") * Spin("B4") + Spin("A2") * Spin("B3")
  + Spin("A3") * Spin("B2") + Spin("A4") * Spin("B1") + Not(Spin("A5") *
    Spin("B0")))

(Spin("A0") * Spin("B4") + Spin("A1") * Spin("B3") + Spin("A2") * Spin("B2") +
  Spin("A3") * Spin("B1") + Spin("A4") * Spin("B0"))

(Spin("A0") * Spin("B4") + Spin("A1") * Spin("B3") + Spin("A2") * Spin("B2") +
  Spin("A3") * Spin("B1") + Spin("A4") * Spin("B0"))

(Spin("A0") * Spin("B3") + Spin("A1") * Spin("B2") + Spin("A2") * Spin("B1") +
  Spin("A3") * Spin("B0"))

(Spin("A0") * Spin("B2") + Spin("A1") * Spin("B1") + Spin("A2") * Spin("B0"))

(Spin("A0") * Spin("B1") + Spin("A1") * Spin("B0"))

(Spin("A0") * Spin("B0"))

I realized I would need a separate module — at least — to keep track of all these decompositions. So, I created expressions.rs. In expressions.rs I started writing methods that would a) resolve PhysicalExpressions’ input variables by calls to D-Wave and / or local lookups and b) replace AbstractExpressions by fully qualified PhysicalExpressions.

The idea was that once the inputs for a PhysicalExpression became available, this next PhysicalExpression could be evaluated, either by simulation or annealing + post selection. The post selection step would be informed by the flow control chains and anti-chains built out in parallelize.rs.

Without further ado I banged out the example for i8.mul.

pub fn lower_one(expression: AbstractExpression, operands: Vec<PhysicalExpression>, node_id: usize) -> Constraint {
    match expression {
         /*
            i8.mul is given by the following circuit from ref. Wing K. Luk and Jean Vuillemin. 
            “Recursive implementation of optimal time VLSi integer multipliers”. In: 1984.

            Operands are ordered as [A0..A5..B0..B5].
          */
        AbstractExpression::Mul{ ty: Type::I8 } => {
            let mut expr: Vec<PhysicalExpression> = vec![
                PhysicalExpression::Mul {
                    operand_one: Box::new(operands[5]),
                    operand_two: Box::new(operands[11])
                },
                PhysicalExpression::Add {
                    operand_one: Box::new(PhysicalExpression::Not {
                        operand: Box::new(PhysicalExpression::Mul {
                            operand_one: Box::new(operands[4]),
                            operand_two: Box::new(operands[11])
                        })
                    }),
                    operand_two: Box::new(PhysicalExpression::Not {
                        operand: Box::new(PhysicalExpression::Mul {
                            operand_one: Box::new(operands[5]),
                            operand_two: Box::new(operands[10])
                        })
                    })
                },
               
                ...

                PhysicalExpression::Mul {
                    operand_one: Box::new(operands[0]),
                    operand_two: Box::new(operands[6])
                }
            ];
            Constraint {
                id: node_id,
                expression: Some(expr)
            }
        },
        AbstractExpression::Mul{ ty: Type::I32 } => todo!(),
        AbstractExpression::Mul{ ty: Type::I64 } => todo!(),
        AbstractExpression::Mul{ ty: Type::F32 } => todo!(),
        AbstractExpression::Mul{ ty: Type::F64 } => todo!(),
        AbstractExpression::Spin { id } => todo!(),
        AbstractExpression::Num { val } => todo!(),
        AbstractExpression::Add{ ty: Type::I32 } => todo!(),
        AbstractExpression::Add{ ty: Type::I64 } => todo!(),
        AbstractExpression::Add{ ty: Type::F32 } => todo!(),
        AbstractExpression::Add{ ty: Type::F64 } => todo!(),
        _ => Constraint::default(node_id)
    }
}

You’ll notice the actual Type::I32, Type::I64, Type::F32 and Type::F64 operations are still todos. These will be much bigger circuits and take up a lot more space.

This is where I realized I might get carpal tunnel syndrome from writing this package if I didn’t introduce a bit more automation into my workflow. I would need to do more reading to find the best combinational circuits for each of the todos, and in the meantime I decided to think about writing a simple string substitution tool to allow me to write these circuits in a bit more of an approachable syntax.

If it were to be a simple string substitution tool, it would need to have nesting structure like my struct instantiations and unlike the format I provided the combinational logic in prior. I am partial to WASM but it is over-complicated.

In Lisp, addition would simply be written (+ A B) and multiplication (* A B), etc. which would be easy to expand to the below via a substitution.

Box::new(PhysicalExpression::Add {
    operand_one: Box::new(operands[A]),
    operand_two: Box::new(operands[B])
})

Box::new(PhysicalExpression::Mul {
    operand_one: Box::new(operands[A]),
    operand_two: Box::new(operands[B])
})

On the other hand, EDIF is also based on S-Expressions and VHDL compiles to EDIF. So, a circuit library could be maintained in VHDL if I could substitute EDIF, which is appealing. I decided to call this a stretch goal.

Printed vertically for the sake of the blog, I could be typing out the following instead for i8.mul.

(
    (*
        a5
        b5
    )
    (+ 
        (! 
            (*
                a4
                b5
            )
        )
        (! 
            (*
                a5
                b4
            )
        )
    )

    ...

    (*
        a0
        b0
    )
)

This could mean maintaining a library of combinational operators in Lisp.

Oh boy.