CONFERENCE
Semināra ietvaros prezentēti šādi referāti (anotācijas angļu val.):
Laplacian versus Adjacency Matrix in Quantum Walk Search
Thomas G. Wong A quantum particle evolving by Schrödinger's equation contains, from the kinetic energy of the particle, a term in its Hamiltonian proportional to Laplace's operator. In discrete space, this is replaced by the discrete or graph Laplacian, which gives rise to a continuous-time quantum walk. Besides this natural definition, some quantum walk algorithms instead use the adjacency matrix to effect the walk. While this is equivalent to the Laplacian for regular graphs, it is different for non-regular graphs, and is thus an inequivalent quantum walk. We algorithmically explore this distinction by analyzing search on the complete bipartite graph with multiple marked vertices, using both the Laplacian and adjacency matrix. The two walks differ qualitatively and quantitatively in their required jumping rate, runtime, sampling of marked vertices, and in what constitutes a natural initial state. Thus the choice of the Laplacian or adjacency matrix to effect the walk has important algorithmic consequences. arxiv.org/abs/1512.05554
Tensor Networks in a Nutshell
Jacob Biamonte
Tensor networks are taking a central role in modern quantum physics and beyond. Their popularity in quantum physics stems from their ease of use as a graphical language to describe and pictorially reason about quantum circuits and protocols, renormalization, and numerical tensor contraction and simulation algorithms. The goal is to explain tensor networks as quickly and as painlessly as possible.
Beginning with the key definitions, the graphical tensor network language will be presented through example, including a few notational oddities that simply arise from linearity and the two-dimensional embedding. We will cover matrix product states (MPS), which gives an efficiently compact representation for certain classes of quantum states. We will also explain two tensor contractions that solve combinatorial counting problems. The first counts Boolean formulae solutions, whereas the second is Penrose's tensor contraction algorithm, returning the number of edge coloring of 3-regular planar graphs. We will conclude by presenting a very brief survey of several current research directions.
quamplexity.org/tensor-network-states/
Uncountable Classical and Quantum Complexity Classes
Maksims Dimitrijevs It is known that polynomial-time constant-space quantum Turing machines (QTMs) and logarithmic- space probabilistic Turing machines (PTMs) recognize uncountably many languages with bounded error (Say and Yakaryilmaz 2014, arXiv:1411.7647). In this paper, we investigate more restricted cases for both models to recognize uncountably many languages with bounded error. We show that double logarithmic space is enough for PTMs on unary languages in sweeping reading mode or logarithmic space for one-way head. On unary languages, for quantum models, we obtain middle logarithmic space for counter machines. For binary languages, arbitrary small non-constant space is enough for PTMs even using only counter as memory. For counter ma-chines, when restricted to polynomial time, we can obtain the same result for linear space. For constant-space QTMs, we follow the result for a restricted sweeping head, known as restarting realtime.
Affine finite automaton
Abuzer Yakaryilmaz
Recently, we introduced a quantum-like classical computation system called affine computation that can mimic the interference by using negative transition. In this talk, we give the definition of affine finite automaton (AfA) and then review some of the results given in the following three papers:
arxiv.org/abs/1602.04732
arxiv.org/abs/1602.05432
arxiv.org/abs/1602.07967
Thomas G. Wong A quantum particle evolving by Schrödinger's equation contains, from the kinetic energy of the particle, a term in its Hamiltonian proportional to Laplace's operator. In discrete space, this is replaced by the discrete or graph Laplacian, which gives rise to a continuous-time quantum walk. Besides this natural definition, some quantum walk algorithms instead use the adjacency matrix to effect the walk. While this is equivalent to the Laplacian for regular graphs, it is different for non-regular graphs, and is thus an inequivalent quantum walk. We algorithmically explore this distinction by analyzing search on the complete bipartite graph with multiple marked vertices, using both the Laplacian and adjacency matrix. The two walks differ qualitatively and quantitatively in their required jumping rate, runtime, sampling of marked vertices, and in what constitutes a natural initial state. Thus the choice of the Laplacian or adjacency matrix to effect the walk has important algorithmic consequences. arxiv.org/abs/1512.05554
Tensor Networks in a Nutshell
Jacob Biamonte
Tensor networks are taking a central role in modern quantum physics and beyond. Their popularity in quantum physics stems from their ease of use as a graphical language to describe and pictorially reason about quantum circuits and protocols, renormalization, and numerical tensor contraction and simulation algorithms. The goal is to explain tensor networks as quickly and as painlessly as possible.
Beginning with the key definitions, the graphical tensor network language will be presented through example, including a few notational oddities that simply arise from linearity and the two-dimensional embedding. We will cover matrix product states (MPS), which gives an efficiently compact representation for certain classes of quantum states. We will also explain two tensor contractions that solve combinatorial counting problems. The first counts Boolean formulae solutions, whereas the second is Penrose's tensor contraction algorithm, returning the number of edge coloring of 3-regular planar graphs. We will conclude by presenting a very brief survey of several current research directions.
quamplexity.org/tensor-network-states/
Uncountable Classical and Quantum Complexity Classes
Maksims Dimitrijevs It is known that polynomial-time constant-space quantum Turing machines (QTMs) and logarithmic- space probabilistic Turing machines (PTMs) recognize uncountably many languages with bounded error (Say and Yakaryilmaz 2014, arXiv:1411.7647). In this paper, we investigate more restricted cases for both models to recognize uncountably many languages with bounded error. We show that double logarithmic space is enough for PTMs on unary languages in sweeping reading mode or logarithmic space for one-way head. On unary languages, for quantum models, we obtain middle logarithmic space for counter machines. For binary languages, arbitrary small non-constant space is enough for PTMs even using only counter as memory. For counter ma-chines, when restricted to polynomial time, we can obtain the same result for linear space. For constant-space QTMs, we follow the result for a restricted sweeping head, known as restarting realtime.
Affine finite automaton
Abuzer Yakaryilmaz
Recently, we introduced a quantum-like classical computation system called affine computation that can mimic the interference by using negative transition. In this talk, we give the definition of affine finite automaton (AfA) and then review some of the results given in the following three papers:
arxiv.org/abs/1602.04732
arxiv.org/abs/1602.05432
arxiv.org/abs/1602.07967