Algebraic graph theory methods in quantum information theory and extremal combinatorics, and connections to semidefinite programming

• Grant number: 15/16339-2
• Support Opportunities: Scholarships in Brazil - Post-Doctoral
• Start date: May 01, 2016
• End date: February 28, 2017
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Computational Mathematics
• Principal Investigator: Yoshiharu Kohayakawa
• Grantee: Gabriel de Morais Coutinho
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
• Associated research grant: 13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science, AP.TEM

Abstract

The main goal of this project is to attack certain combinatorial problems using algebraic graph theory tools. Four main types of problems will be studied. The first consists on problems related to the transition matrix of continuous time quantum walks in graphs. The candidate recently completed his PhD on this topic. The second type is related to maximal sets of equiangular lines on $d$-dimensional Hilbert spaces and corresponding combinatorial structures. The third type contains problems associated to quantum homomorphisms and related quantum versions of certain graph parameters, such as the quantum chromatic number. The last type consists on problems of Erdos-Ko-Rado type of statement, as it has been shown that spectral methods can be used to study intersecting families of a plethora of mathematical structures.Common to all problems mentioned above is the connection to algebraic graph theory and its methods. Nevertheless, other combinatorial techiniques such as semidefinite programming will come into play, specially on the three last classes of problems mentioned above.

Scientific publications

(4)

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

COUTINHO, GABRIEL; GODSIL, CHRIS; GUO, KRYSTAL; ZHAN, HANMENG. A New Perspective on the Average Mixing Matrix. ELECTRONIC JOURNAL OF COMBINATORICS, v. 25, n. 4, OCT 19 2018. (15/16339-2)

COUTINHO, GABRIEL; PORTUGAL, RENATO. Discretization of continuous-time quantum walks via the staggered model with Hamiltonians. NATURAL COMPUTING, v. 18, n. 2, 1, SI, p. 403-409, JUN 2019. (15/16339-2, 13/03447-6)

COUTINHO, GABRIEL; GODSIL, CHRIS. PERFECT STATE TRANSFER IS POLY-TIME. QUANTUM INFORMATION & COMPUTATION, v. 17, n. 5-6, p. 495-502, MAY 1 2017. (15/16339-2, 13/03447-6)

COUTINHO, GABRIEL; PORTUGAL, RENATO. Discretization of continuous-time quantum walks via the staggered model with Hamiltonians. NATURAL COMPUTING, v. 18, n. 2, p. 7-pg., 2019-06-01. (13/03447-6, 15/16339-2)