[hep-th] seminar i u sredu 29. juna

[Branislav Cvetkovic]

Postovane kolege,

nas gost Vitalij Vancurin sa Univerziteta u Minesoti je planirao da 
odrzi dva seminara. Prvi
seminar ce se odrzati, kao sto sam vec ranije najavio u petak 1. jula,
a drugi je trebalo da bude u petak 8. jula. Medjutim, zbog predavacevog 
puta u Ukrajinu,
doslo je do pomeranja, tako da ce Vitalij Vancurov odrzati seminar pod 
naslovom "Dual Field
Theories of Quantum Computation" na Institutu za fiziku u sredu 29. juna 
u 11h. Apstrakt vam
prosledjujem u nastavku.

Pozdrav Branislav



Abstract: Given two quantum states of N q-bits we are interested to
find the shortest quantum circuit consisting of only one- and two-
q-bit gates that would transfer one state into another. We call it the
quantum maze problem (for the reasons that I will described in the
talk) which is relevant to both: quantum gravity and quantum
computing. We argue that in a large N limit the quantum maze problem
is equivalent to the problem of finding a semiclassical trajectory of
some lattice field theory (the dual theory) on an N+1 dimensional
space-time with geometrically flat, but topologically compact spatial
slices. The spatial fundamental domain is an N dimensional
hyper-rhombohedron, and the temporal direction describes transitions
from an arbitrary initial state to an arbitrary target state. We first
consider a complex Klein-Gordon field theory and argue that it can
only be used to study the shortest quantum circuits which do not
involve generators composed of tensor products of multiple Pauli Z
matrices. Since such situation is not generic we call it the
Z-problem. On the dual field theory side the Z-problem corresponds to
massless excitations of the phase (Goldstone modes) that we attempt to
fix using Higgs mechanism. The simplest dual theory which does not
suffer from the massless excitation (or from the Z-problem) is the
Abelian-Higgs model which we argue can be used for finding the
shortest quantum circuits. Since every trajectory of the field theory
is mapped directly to a quantum circuit, the shortest quantum circuits
are identified with semiclassical trajectories. We also discuss the
complexity of an actual algorithm that uses a dual theory prospective
for solving the quantum maze problem and compare it with a geometric
approach. We argue that it might be possible to solve the problem in
sub-exponential time in 2^N, but for that we must consider the
Klein-Gordon theory on curved spatial geometry and/or more complicated
(than N-torus) topology.

-- 
Institute of Physics Belgrade
Pregrevica 118, 11080 Belgrade, Serbia
http://www.ipb.ac.rs/