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.

import math
import numpy as np

class Bits(object):

    def __init__(self, bit_string):

        self.sanity_check(bit_string)
        self.bit_string = bit_string

    def sanity_check(self, bit_string):

        for char in bit_string:
            if char != "0" and char != "1":
                raise Exception("BitString construction uses a string consisting of 0 and 1!")

    def __len__(self):

        return len(self.bit_string)

    def __eq__(self, bits):

        return self.bit_string == bits.bit_string

    def __str__(self):

        return self.bit_string

    def to_uint(self):

        return int(self.bit_string, 2)

    def to_state_vec(self):
        """
        Return a one-hot state vector for bits
        """
        vec = [0] * (2 ** len(self))
        vec[self.to_uint()] = 1

        return vec

def state_vec_to_bits(state_vec):

    num_zeros = 0
    num_ones = 0
    state_vec_len = len(state_vec)
    num_bits = math.log(state_vec_len, 2)
    if not num_bits.is_integer():
        raise Exception("Invalid state vector length!")
    num_bits = int(num_bits)
    idx = None
    for i, element in enumerate(state_vec):
        if element == 0:
            num_zeros += 1
        elif element == 1:
            num_ones += 1
            idx = i
        else:
            raise Exception("State vector should only container 0 or 1!")
    if num_ones != 1 or idx is None:
        raise Exception("State vector should only have one 1!")

    bit_string = bin(idx)[2:].zfill(num_bits)

    bits = Bits(bit_string=bit_string)

    return bits

def main():

    # Gate operators
    NOT = np.array([[0,1],[1,0]])
    AND = np.array([[1,1,1,0],[0,0,0,1]])

    bit_string_a = "01"
    bit_string_b = "0"
    bit_string_c = "0"
    bit_string_d = "1"

    bits_a = Bits(bit_string=bit_string_a)
    bits_b = Bits(bit_string=bit_string_b)
    bits_c = Bits(bit_string=bit_string_c)
    bits_d = Bits(bit_string=bit_string_d)
    bits_ab = Bits(bit_string=bit_string_a + bit_string_b)
    bits_ba = Bits(bit_string=bit_string_b + bit_string_a)
    bits_cd = Bits(bit_string=bit_string_c + bit_string_d)
    bits_dc = Bits(bit_string=bit_string_d + bit_string_c)

    assert bits_a == state_vec_to_bits(state_vec=bits_a.to_state_vec())
    assert bits_b == state_vec_to_bits(state_vec=bits_b.to_state_vec())
    assert bits_c == state_vec_to_bits(state_vec=bits_c.to_state_vec())
    assert bits_d == state_vec_to_bits(state_vec=bits_d.to_state_vec())

    A = np.array(bits_a.to_state_vec())
    B = np.array(bits_b.to_state_vec())
    C = np.array(bits_c.to_state_vec())
    D = np.array(bits_d.to_state_vec())
    AB = np.array(bits_ab.to_state_vec())
    BA = np.array(bits_ba.to_state_vec())
    CD = np.array(bits_cd.to_state_vec())
    DC = np.array(bits_dc.to_state_vec())

    # Parallel operations
    # A -> AND -> C
    # B -> NOT -> D
    # We have the following equations
    # AND * A = C
    assert np.array_equal(np.dot(AND, A), C)
    # NOT * B = D
    assert np.array_equal(np.dot(NOT, B), D)
    # A \otimes B = AB
    assert np.array_equal(np.kron(A, B), AB)
    # B \otimes A = BA
    assert np.array_equal(np.kron(B, A), BA)
    # C \otimes D = CD
    assert np.array_equal(np.kron(C, D), CD)
    # D \otimes C = DC
    assert np.array_equal(np.kron(D, C), DC)
    # (AND \otimes NOT) * (A \otimes B) = (C \otimes D)
    assert np.array_equal(np.dot(np.kron(AND, NOT), np.kron(A, B)), np.kron(C, D))
    # (NOT \otimes AND) * (B \otimes A) = (D \otimes C)
    assert np.array_equal(np.dot(np.kron(NOT, AND), np.kron(B, A)), np.kron(D, C))

if __name__ == "__main__":

    main()

References

• Almost Commutative Kronecker Product
• Kronecker Product