# Kronecker Product In Circuits

## Introduction

Kronecker product is widely used in circuits, especially those that have parallel logical gates, to manipulate bits.

In this blog post, I would like to discuss the mathematics of Kronecker product in circuits.

## Prerequisites

### Kronecker Product Mixed-Product Property

Let $A \in \mathbb{C}^{m \times n}$, $B \in \mathbb{C}^{r \times s}$, $C \in \mathbb{C}^{n \times p}$, and $D \in \mathbb{C}^{s \times t}$, then

$$

(A \otimes B)(C \otimes D) = (AC) \otimes (BD)

$$

Note that $AC$ and $BD$ have to be valid matrix multiplications.

It is easy to prove using the Kronecker product definition.

$$

\begin{align}

&(A \otimes B)(C \otimes D) \\

&=

\begin{bmatrix}

A_{0,0}B & A_{0,1}B & \cdots & A_{0,n-1}B \\

A_{1,0}B & A_{1,1}B & \cdots & A_{1,n-1}B \\

\vdots & \vdots & \ddots & \vdots \\

A_{m-1,0}B & A_{m-1,1}B & \cdots & A_{m-1,n-1}B \\

\end{bmatrix}

\begin{bmatrix}

C_{0,0}D & C_{0,1}D & \cdots & C_{0,p-1}D \\

C_{1,0}D & C_{1,1}D & \cdots & C_{1,p-1}D \\

\vdots & \vdots & \ddots & \vdots \\

C_{n-1,0}D & C_{n-1,1}D & \cdots & C_{n-1,p-1}D \\

\end{bmatrix}

\nonumber\\

&=

\begin{bmatrix}

\big(\sum_{i=0}^{n-1}A_{0,i}C_{i,0}\big)BD & \big(\sum_{i=0}^{n-1}A_{0,i}C_{i,1}\big)BD & \cdots & \big(\sum_{i=0}^{n-1}A_{0,i}C_{i,p-1}\big)BD \\

\big(\sum_{i=0}^{n-1}A_{1,i}C_{i,0}\big)BD & \big(\sum_{i=0}^{n-1}A_{1,i}C_{i,1}\big)BD & \cdots & \big(\sum_{i=0}^{n-1}A_{1,i}C_{i,p-1}\big)BD \\

\vdots & \vdots & \ddots & \vdots \\

\big(\sum_{i=0}^{n-1}A_{m-1,i}C_{i,0}\big)BD & \big(\sum_{i=0}^{n-1}A_{m-1,i}C_{i,1}\big)BD & \cdots & \big(\sum_{i=0}^{n-1}A_{m-1,i}C_{i,p-1}\big)BD \\

\end{bmatrix}

\nonumber\\

&=

(AC) \otimes (BD) \\

\end{align}

$$

### Logical Gates Are Matrices

Logical gates could be natually represented by matrices. For example, given any one bit, we could represent it as a unique one-hot state vector of length $2^1 = 2$. More concretely, `0`

is $| 0 \rangle = [1, 0]^{\top}$, `1`

is $| 1 \rangle = [0, 1]^{\top}$. given any two bits, we could represent it as a unique one-hot state vector of length $2^2 = 4$. More concretely, `00`

is $| 00 \rangle = [1, 0, 0, 0]^{\top}$, `01`

is $| 01 \rangle = [0, 1, 0, 0]^{\top}$, `10`

is $| 10 \rangle = [0, 0, 1, 0]^{\top}$, `11`

is $| 11 \rangle = [0, 0, 0, 1]^{\top}$. So on and so forth.

A classical `AND`

gate takes into two bits and generates one bit. Its matrix representation $\text{AND} \in \mathbb{C}^{2^1 \times 2^2}$, which takes in a state vector of length 4 and generates a state vector of length 2, is

$$

\begin{align}

\text{AND} &=

\begin{bmatrix}

1 & 1 & 1 & 0 \\

0 & 0 & 0 & 1 \\

\end{bmatrix}

\end{align}

$$

The expectations of `AND`

gate are `00 -> AND -> 0`

, `01 -> AND -> 0`

, `10 -> AND -> 0`

, `11 -> AND -> 1`

. Let’s check one of them, say `01 -> AND -> 0`

, using matrix multiplication.

$$

\begin{align}

\text{AND}

| 01 \rangle

=

\begin{bmatrix}

1 & 1 & 1 & 0 \\

0 & 0 & 0 & 1 \\

\end{bmatrix}

\begin{bmatrix}

0 \\

1 \\

0 \\

0 \\

\end{bmatrix}

=

\begin{bmatrix}

1 \\

0 \\

\end{bmatrix}

=

| 0 \rangle

\end{align}

$$

The gate input is $| 01 \rangle = [0, 1, 0, 0]^{\top}$ (`10`

) and the gate output is $| 0 \rangle = [1, 0]^{\top}$ (`0`

), which matches our expectation.

## Parallel Logical Gates and Kronecker Product

### Parallel Logical Gates

If we have an input of multiple bits, we would like to take the first several consecutive bits for logical gate 1, the second several consecutive bits for logical gate 2, and so on, and we collect all the outputs as the final output. The logical gate 1, 2, etc., are parallel logical gates.

For example, we have three bits, `010`

. We would like to take the first two bits `01`

for `AND`

and the third bit for `NOT`

. The expected output would be `01`

because `01 -> AND -> 0`

and `0 -> NOT -> 1`

.

The three bits, `010`

, could also be represented by a state vector of length $2^3=8$. Normally, we would need to convert `010`

to a `uint`

, which is `2`

and then we know the state vector is $| 010 \rangle = [0, 0, 1, 0, 0, 0, 0, 0]^{\top}$. However, since `01`

could be thought as one system state and `0`

could be thought as an another system state, `010`

would be a merged system state of system state `01`

and system state `0`

. Mathematically, if we know the state vector for `01`

and `0`

, we could compute the merged system state `010`

using Kronecker product.

$$

\begin{align}

| 010 \rangle &= | 01 \rangle \otimes | 0 \rangle \\

&=

\begin{bmatrix}

0 \\

1 \\

0 \\

0 \\

\end{bmatrix}

\otimes

\begin{bmatrix}

1 \\

0 \\

\end{bmatrix} \\

&=

\begin{bmatrix}

0 \\

0 \\

1 \\

0 \\

0 \\

0 \\

0 \\

0 \\

\end{bmatrix}

\end{align}

$$

Where $\otimes$ is the Kronecker product. Informally, people call Kronecker product and tensor product interchangably. The state vector for `010`

calculated from the output product matches our expectation.

We apply the first two bits `01`

for `AND`

, as we have caculated above, we have

$$

\begin{align}

\text{AND}

| 01 \rangle

=

\begin{bmatrix}

1 \\

0 \\

\end{bmatrix}

=

| 0 \rangle

\end{align}

$$

The `NOT`

gate could be represented using the matrix below

$$

\begin{align}

\text{NOT} &=

\begin{bmatrix}

0 & 1 \\

1 & 0 \\

\end{bmatrix}

\end{align}

$$

We apply the last bit `0`

for `NOT`

, we have

$$

\begin{align}

\text{NOT}

| 0 \rangle

=

\begin{bmatrix}

0 & 1 \\

1 & 0 \\

\end{bmatrix}

\begin{bmatrix}

1 \\

0 \\

\end{bmatrix}

=

\begin{bmatrix}

0 \\

1 \\

\end{bmatrix}

=

| 1 \rangle

\end{align}

$$

Because of the way we set up the circuits, `AND`

and `NOT`

are parallel logical gates, the output state vector has to be merged into one state vector.

$$

\begin{align}

| 0 \rangle

\otimes

| 1 \rangle

=

\begin{bmatrix}

1 \\

0 \\

\end{bmatrix}

\otimes

\begin{bmatrix}

0 \\

1 \\

\end{bmatrix}

=

\begin{bmatrix}

0 \\

1 \\

0 \\

0 \\

\end{bmatrix}

=

| 01 \rangle

\end{align}

$$

So running the circuits above is equivalent to, mathematically,

$$

(\text{AND} |01\rangle ) \otimes (\text{NOT} |0\rangle )

$$

We happen to find that we could apply the Kronecker product mixed-product property we mentioned in the prerequisites.

$$

\begin{align}

(\text{AND} |01\rangle ) \otimes (\text{NOT} |0\rangle ) &= (\text{AND} \otimes \text{NOT}) (|01\rangle \otimes |0\rangle ) \\

&= (\text{AND} \otimes \text{NOT}) |010\rangle

\end{align}

$$

This means that in order to compute the output of this parallel logical gates, we don’t have to compute the outputs for each single logical gate separately and collect the outputs back together. Given the intact input state vector, $|010\rangle $, we could apply a merged operator of `AND`

and `NOT`

, which turns out to be $\text{AND} \otimes \text{NOT}$, and the output could be computed directly using matrix multiplication once.

### Summary

Any two parallel logical gates could be described using a single logical gate that is the Kronecker product of the two.

In general, if we have a circuit consisting of two parallel logical gates, $X$ and $Y$, the input state vector $| a \rangle$ to $X$, the input state vector $| b \rangle$ to $Y$, the output state vector $| c \rangle$ from $X$, the output state vector $| d \rangle$ from $Y$, the merged input state vector $| ab \rangle$ or $| ba \rangle$, and the merged output state vector $| cd \rangle$ or $| dc \rangle$, we have the following equations.

$$

\begin{align}

| cd \rangle &= | c \rangle \otimes | d \rangle \\

&= (X | a \rangle) \otimes (Y | b \rangle) \\

&= (X \otimes Y) (|a\rangle \otimes |b\rangle ) \\

&= (X \otimes Y) |ab\rangle \\

\end{align}

$$

$$

\begin{align}

| dc \rangle &= | d \rangle \otimes | c \rangle \\

&= (Y | b \rangle) \otimes (X | a \rangle) \\

&= (Y \otimes X) (|b\rangle \otimes |a\rangle ) \\

&= (Y \otimes X) |ba\rangle \\

\end{align}

$$

One interesting thing to note is that $X \otimes Y \cong Y \otimes X$ and $Y \otimes X = P (X \otimes Y) Q$, where $P$ and $Q$ are row and column permutation matrices respectively. We could also have $| ba \rangle = W | ab \rangle$, and $| dc \rangle = V | cd \rangle$, where $W$ and $V$ are row permutation matrices.

$$

\begin{align}

| dc \rangle &= V | cd \rangle \\

&= (Y \otimes X) |ba\rangle \\

&= P (X \otimes Y) Q W | ab \rangle \\

\end{align}

$$

Permutation matrix is always invertible and its inversion is equivalent to its transpose.

$$

\begin{align}

| cd \rangle &= V^{-1} P (X \otimes Y) Q W | ab \rangle \\

\end{align}

$$

It seems that $V^{-1} P = I$ and $Q W = I$. But I have not thought of a formal proof to this.

### Simulations

Here I implemented a simple Python script to simulate and verify the parallel logical gates and Kronecker product processes I described above.

1 | import math |

## References

Kronecker Product In Circuits

https://leimao.github.io/blog/Kronecker-Product-In-Circuits/