内容简介: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.Let $A \in \mathbb{C}^{m \times n}$, $B \in \mat
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
Note that $AC$ and $BD$ have to be valid matrix multiplications.
It is easy to prove using the Kronecker product definition.
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 classic 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
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.
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 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. Mathematically, if we know the state vector for 01
and 0
, we have
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
The NOT
gate could be represented using the matrix below
We apply the last bit 0
for NOT
, we have
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.
So running the circuits above is equivalent to, mathematically,
We happen to find that we could apply the Kronecker product mixed-product property we mentioned in the prerequisites.
This means that in order to compute the output of this parallel logical gates, we don’t have to compute the outputs separately and collect the outputs back together. Given the intact 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.
One interesting thing to note is that $X \otimes Y \cong Y \otimes X$ and $X \otimes Y = P (Y \otimes X) 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.
Permutation matrix is always invertible and its invertible is equivalent to its transpose.
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()
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。