A New Model for Quantum Cellular Automata

Ruhi Shah, University of Waterloo

BarcodeImage["https://arxiv.org/abs/1910.00578","QR"]

What is a QCA?

Formalism

Overview of Quantum Computing

ψ=A\[LeftBracketingBar]0⟩+B\[LeftBracketingBar]1⟩

Where
((\[LeftBracketingBar]A\[RightBracketingBar])^2) : probability that the qubit is in state \[LeftBracketingBar]0⟩
  ((\[LeftBracketingBar]B\[RightBracketingBar])^2) : probability that the qubit is in state \[LeftBracketingBar]1⟩

Consider,

(Subscript[ψ, 1])=(Subscript[A, 1])\[LeftBracketingBar]0⟩+(Subscript[B, 1])\[LeftBracketingBar]1⟩ and (Subscript[ψ, 2])=(Subscript[A, 2])\[LeftBracketingBar]0⟩+(Subscript[B, 2])\[LeftBracketingBar]1⟩

With Tensor Product,

(Subscript[ψ, 1,2])= (Subscript[ψ, 1])⊗ (Subscript[ψ, 2])= (Subscript[A, 1])(Subscript[A, 2])\[LeftBracketingBar]00⟩+(Subscript[A, 1])(Subscript[B, 2])\[LeftBracketingBar]01⟩ +(Subscript[B, 1])(Subscript[A, 2])\[LeftBracketingBar]10⟩+(Subscript[B, 1])(Subscript[B, 2])\[LeftBracketingBar]11⟩

Initial State

(Subscript[ψ, 0])=(Subscript[c, 1])\[LeftBracketingBar]000⟩+(Subscript[c, 2])\[LeftBracketingBar]001⟩ +(Subscript[c, 3])\[LeftBracketingBar]010⟩+(Subscript[c, 4])\[LeftBracketingBar]011⟩ + (Subscript[c, 5])\[LeftBracketingBar]100⟩+(Subscript[c, 6])\[LeftBracketingBar]101⟩ +(Subscript[c, 7])\[LeftBracketingBar]110⟩+(Subscript[c, 8])\[LeftBracketingBar]111⟩

Evolution

u-> u((Subscript[q, 1]),(Subscript[q, 2]))->((Subscript[q, 1])',(Subscript[q, 2])')-> (Subscript[ψ, 0,1])'

u-> u((Subscript[q, 2]),(Subscript[q, 3]))->((Subscript[q, 2])',(Subscript[q, 3])')-> (Subscript[ψ, 0,2])'

u-> u((Subscript[q, 1]),(Subscript[q, 3]))->((Subscript[q, 1])',(Subscript[q, 3])')-> (Subscript[ψ, 0,3])'

U((Subscript[ψ, 0]))=(Subscript[ψ, 1])=(Subscript[ψ, 0,1])'+(Subscript[ψ, 0,2])'+(Subscript[ψ, 0,3])'

U =u((Subscript[q, 1]),(Subscript[q, 2]))+u((Subscript[q, 2]),(Subscript[q, 3]))+u((Subscript[q, 1]),(Subscript[q, 3]))

For more than 3 qubits:

U =(∑_(j=1)^N)(Subscript[u, j])(Subscript[u, j+1])

For more than one operator:

U =(∑_(j=1)^N)(Subscript[(u^1), j])(Subscript[(u^1), j+1...])(Subscript[(u^m), j])(Subscript[(u^m), j+1])

For the (p^th) state

U(U(...U((Subscript[ψ, 0]))...))=(Subscript[ψ, p])

Example

QuantumTensorAutomaton[{fourierOperator},initialState[4],2]

Visualization

(({{1, -1, 0, I, -I}}))

QuantumTensorAutomaton[{randomUnitaryOperator},initialState[4],10,"ColourPlot"-> True]

More Examples

QuantumTensorAutomaton[{randomUnitaryOperator},initialState[4],50,"ColourPlot"-> True]

QuantumTensorAutomaton[{randomUnitaryOperator},initialState[4],50,"ColourPlot"-> True]

Norms Squared

What Now?

Change initial conditions

Change operators

Connect to the real world

Change boundary conditions

Find different ways to visualize (incorporate the argument)

Modify the model

Equilibrium Time vs Computational Complexity

(Jonathan Gorard)

Conjecture:

Alice falls into a black hole. Bob sees Alice get red-shifted. He attempts to reconstruct her from the red-shifted state. The computational complexity required for Bob to reconstruct Alice is related to the time taken for Alice to fall into the black hole (in Bob’s reference frame).

Equilibrium Time

Initial Conditions and Operators

Convergence

Log plot of change in L2 Norms over time.

Resonance

QuantumTensorAutomaton[{resonantOperator1},initialState[4],800,"NormsPlot"-> True]

Computational Complexity

Complexity of reversal operator.

\[RightBracketingBar](Subscript[ψ, 0])⟩=R\[LeftBracketingBar](Subscript[ψ, e])⟩

Any R that is Hermitian.

Summing over the norms-squared of the eigenvalues.

Complexity, Initial Conditions, and Operators

The operator largely determines the equilibrium state, the equilibrium time, and the computational complexity.

Complexity vs Equilibrium Time

Non-linear relationship

(R^2) value: 0.934

Next steps...

Collect more data

Improve complexity analysis

Validate more conjectures

Thank you

r57shah@uwaterloo.ca