Raziskovalni matematični seminar - Arhiv

Quantum Computers are built on the principles of Quantum Mechanics. It has been proved that many difficult problems can be solved by quantum computers. We intend to introduce quantum computing and discuss some quantum algorithms. We also intend to explore the connections between Boolean functions and quantum computing. 

The topics to be discussed are as follows: 

- Introduction to Quantum Mechanics and Quantum Information.  Quantum States, Operators and Measurements. 
- BB84: A quantum key exchange protocol. 
- Quantum Entanglement. Quantum Teleportation. 
- Quantum Circuits: Single qubit gates, multiple qubit gates, design of quantum circuits. 
- Quantum Algorithms:  Deutsch's algorithm, Deutsch's-Jozsa algorithm. 
- Grover search and Its Geometric interpretation.  
- Implementing quantum algorithms on IBM's quantum computer IBM-Q. 
- Boolean functions and quantum computing.

In this talk I want to present the connection between the so-called cluster expansion and relation between species of graphs.
Cluster expansion is a way of dismantling highly complex correlation patterns in probability distributions describing the long term behaviour of high dimensional dynamical systems. The terms of these expansions are labeled by species of graphs, like multi-rooted simple or double connected graphs. Changing the expansion parameter is related to functional relations between the generating functions of different species.
Finally, I will discuss how one can prove convergence of theses expansion, which requires to estimate them by an expansion labeled by trees.

A {\em pseudo-Boolean function}  is a real-valued function f(x)=f(x_1,x_2,\ldots,x_n) of n binary variables. It is well-known  that every pseudo-Boolean function can be uniquely represented as a multilinear polynomial in its variables.

\emph{Nonlinear binary optimization problems}, or \emph{pseudo-Boolean optimization} (PBO) \emph{problems}, of the form 
\min \{ f(x) : x \in \{0,1\}^n \},
where f(x) is a pseudo-Boolean polynomial,  have attracted the attention of numerous researchers for more than 50 years.  These problems are notoriously difficult, as they naturally encompass a broad variety of models such as maximum satisfiability, max cut, graph coloring, image restoration, and so on.

In this talk, I present recent results (obtained in collaboration with Martin Anthony, Endre Boros, Aritanan Gruber, and Elisabeth Rodriguez-Heck) regarding the size of reformulations of nonlinear PBO problems as quadratic PBO problems.

SLIDES

The talk gives a light introduction to the theory of combinatorial (impartial) games and the Sprague-Grundy theory. Then we consider a generalization of the well-known game of NIM, and show several results about such generalizations.

Joint work with Vladimir Gurvich, Nhan Bao Ho, Kazuhisa Makino, and Peter Mursic.