Resume
I
am a Royal Society University
Research Fellow and a Reader
in Physics
of Information with the Department
of Computer Science at UCL. At present, I am also a Visiting
Chair Professor with the Institute
of Natural Sciences at Shanghai Jiao Tong University (my page at
SJTU is here),
as a recipient of a 1000 Talents Program grant. I started at UCL the
Computer
Science Quantum Information Interest Group,
which is now part of the larger Intelligent
Systems Group. Our activities are related to the UCL
Institute for Quantum Science and Technology.
I
was a Newton International Fellow with the Department
of Physics & Astronomy at UCL. I was a PostDoctoral Research
Fellow of the Institute for Quantum
Computing and the Department
of Combinatorics & Optimization at the University
of Waterloo, mentored by Michele
Mosca, and a PostDoctoral Research Assistant in the Department
of Computer Science and the Department
of Mathematics at the University
of York. I obtained my PhD from Bristol
University, in the then newly created Quantum
Computation and Information Group. My advisor was Richard
Jozsa, whose advisor was Roger
Penrose. I was a visiting student at UC
Berkeley (and MSRI),
and previously I studied
Chemistry
at the University of
Siena
and
Philosophy (Logic) at the University
of Florence. My long term scientific visits include CRI,
CWI, MIT,
Nankai, NUS
and RISCLinz. I have been a
Visiting Fellow of the Isaac
Newton Institute for Mathematical Sciences, Cambridge, during
three thematic programmes.
I
am a member of the steering committee of the Conference
on the
Theory of Quantum Computation, Communication and Cryptography (TQC)
and a member
of the Computer Science Evaluation Group at the Natural Sciences and
Engineering Research Council of Canada (NSERC) (see below for a list
of professional services). I serve in the editorial board of
Philosophical
Transactions of the Royal Society A. I am a recipient of the 2015
Talented Young Italians Awards: Research & Innovation given
by the Italian Chamber of Commerce and Industry for the UK. My
other links at UCL are CoMPLEX
Research Group, UCL
Institute of Origins, and London
Center for Nanotechnology. Here
is a page about the Quantum
Computing, Information, and Algebras of Operators (QCIAO)
collaboration. My
research papers can be found in arXiv,
MathSciNet,
MPRA, PubMed,
and IRIS.
Publications
J.
Lockhart, S. Severini, Combinatorial
entanglement, May 2016. arXiv:1605.03564
[quantph]
A.
Dawar, S. Severini, O. Zapata, Descriptive
complexity of graph spectra, March 2016. arXiv:1603.07030
[cs.LO]. WoLLIC
2016.
23rd Workshop on Logic, Language, Information and Computation.
August 16th19th, 2016. Puebla, Mexico.
<2016
P.
Gnacinski, M. Rosicka, R. Ramanathan, K. Horodecki, M. Horodecki,
P. Horodecki, S. Severini, Linear
game noncontextuality and Bell inequalities  a graphtheoretic
approach, arXiv:1511.05415
[quantph]. 2016 New J. Phys. 18 045020.
E.
R. Hancock, L. Rossi, S. Severini, A, Torsello, R. C. Wilson, O.
Zapata, QuantumInspired Graph Matching, Workshop
on Quantum Machine Learning (as part of NIPS 2015), October 2015
A.
Jurisic, A. Munemasa, S. Severini (Eds.), Algebraic
Combinatorics: Spectral Graph Theory, ErdosKoRado Theorems and
Quantum Information Theory, Special issue to celebrate the work
of Chris Godsil, Journal of Algebraic Combinatorics, Volume 43,
Number 4, June 2016.
Z.
Chen, Z. Ma, T. Gao, S. Severini, A
combinatorial criterion for kseparability of
multipartite Dicke states, November 2015. arXiv:1511.00103
[quantph]
C.
R. S. Banerji, M. Panamarova, R. B. White , S. Severini, P. S.
Zammit, PAX3 and PAX7 but not DUX4 target gene expression
characterise FSHD skeletal muscle, submitted.
C.
R. S. Banerji, Network theoretic tools in the analysis of complex
diseases, PhD thesis, June 2015.
F.
Caravelli, T. Mansour, Sindoni, S. Severini, On
moments of the integrated exponential Brownian motion, September
2015. arXiv:1509.05980
[condmat.statmech]
R.
Duan, S. Severini, A. Winter, On zeroerror
communication via quantum channels in the presence of noiseless
feedback, February 2015. arXiv:1502.02987v1
[quantph] (long talk at AQIS2015).
A.
E. Teschendorff, C. R. S. Banerji , S. Severini , R. Kuehn , P.
Sollich, Increased
signaling entropy in cancer requires the scalefree property of
protein interaction networks, arXiv:1504.00120
[qbio.MN], Sci. Rep. 5, Article number 9646, 2015.
C.
R. S. Banerji, S. Severini, C. Caldas, A. E. Teschendorff,
Intratumour
signalling entropy determines clinical outcome in breast and lung
cancer, PLoS Comput Biol 11(3): e1004115 (2015).
 L.
Hogben, K. Palmowski, D. E. Robertson, S. Severini, Orthogonal
representations, projective ranks, and fractional minimum positive
semidefinite rank: connections and new directions, January 2015.
arXiv:1502.00016
[math.CO]
 C.
R. S. Banerji, P. Knopp, L. A. Moyle, S. Severini, R. W. Orrell, A.
E. Teschendorff, P. S. Zammitt, βcatenin
is central to DUX4driven network rewiring in Facioscapulohumeral
muscular dystrophy, J. R. Soc. Interface, 26 Nov 2014.

Interactome
Sparsification and Rewiring
(InSpiRe)
is
a differential network algorithm based on information theoretic
principles that can detect
shifts
in active pathway regimes, identifying proteins from the human
interactome displaying a wide class of rewiring events between two
phenotypes. This protein set is constructed into a subnetwork,
which is sparsified to describe pathways altered between phenotypes.
Download
R script

V.
I. Paulsen, S. Severini, D. Stahlke, I. G. Todorov, A. Winter,
Estimating
quantum chromatic numbers, Journal of Functional Analysis 270
(2016), pp. 21882222. arXiv:1407.6918
[math.OA]

B.H.
Wang, H.R. Xu, S. Campbell, S. Severini, Characterization
and properties of weakly optimal entanglement witnesses, QIC
15:13&14 (2015), 11091121. arXiv:1407.0870
[quantph]

T.
Cubitt, L. Mancinska, D. Roberson, S. Severini, D. Stahlke, and A.
Winter, Bounds
on entanglement assisted sourcechannel coding via the Lovasz theta
number and its variants, IEEE
Trans. Inf. Theory. 60:11,
73307340 (2014). arXiv:1310.7120
[quantph]

B.H.
Wang, H.R. Xu, S. Severini, Universal
methods for extending any entanglement witness from the bipartite to
the multipartite case,
Phys. Rev. A 90, 022312 (2014),
arXiv:1405.2021
[quantph]

A.
Chailloux, L. Mančinska, G. Scarpa, S. Severini,
Graphtheoretical Bounds on
the Entangled Value of Nonlocal Games, arXiv:1404.3640
[quantph], LIPIcs, Vol. 27 (TQC2014).

J.Y.
Wu, M. Rossi, H. Kampermann, S. Severini, L.C. Kwek, C.
Macchiavello, D. Bruß, Randomized
graph states and their entanglement properties, Phys. Rev. A 89,
052335 (2014), Editor's choice, arXiv:1403.3828
[quantph]

Rethinking
GIP: Graph
Isomorphism Game on crowdcrafting.org;
Graph
Isomorphism: Quantum Ideas

W.
Vinci, S. Boixo, K. Markstrom, A. Roy, F. Spedalieri, P. Warburton,
S. Severini, Hearing
the Shape of the Ising Model with a Programmable
SuperconductingFlux Annealer, Sci. Rep. 4, Article Number:
5703, 2014. arXiv:1307.1114
[quantph]

H.
Buhrman, P. T. S. van der Gulik, S. Severini, D. Speijer, A
mathematical model of kinetoplastid mitochondrial gene scrambling
advantage, arXiv:1307.1163
[qbio.PE]

S.
Kirkland, S. Severini, alphaKuramoto
partitions: graph partitions from the frustrated Kuramoto model
generalise equitable partitions, Appl. Anal. Discr. Math. (9),
2015. arXiv:1306.4299
[math.CO]
 C.
Godsil, D. Roberson, R. Samal, S. Severini, Sabidussi
versus Hedetniemi for three variations of the chromatic number,
Combinatorica, January 2015. arXiv:1305.5545
[math.CO]. Talk by Robert Samal at CanaDAM 2013: Hedetniemi
conjecture for strict vector chromatic number

N.
de Beaudrap, V. Giovannetti, S. Severini, R. Wilson, Interpreting
the von Neumann entropy of graphs Laplacians, and coentropic graphs,
accepted for publication in Contemp. Math. arXiv:1304.7946
[math.CO]

Z.H.
Ma, C. Yao, Z.H. Chen, S. Severini, A. Serafini,
A universal memoryassisted
entropic uncertainty relation, Sci.
China
Phys.
Mech. Astron..57:8
(2014), 1703. arXiv:1302.1011
[quantph]

T.
Feng, S. Severini, Quantum
channels from association schemes, January 2013. arXiv:1301.1166
[quantph]

S.
Severini , F. Brandao (Eds.), 8th
Conference on the Theory of Quantum Computation, Communication and
Cryptography (TQC 2013), Revised Selected Papers, LIPIcsLeibniz
International Proceedings in Informatics, Vol. 22, 2013.
 C.
R. S. Banerji, T. Mansour, S. Severini, A
notion of graph likelihood and an infinite monkey theorem, J.
Phys. A: Math. Theor.
47
035101.
arXiv:1304.3600
[cs.DM]. See also Weisstein,
Eric W. "Graph Likelihood." From MathWorldA
Wolfram Web Resource.
http://mathworld.wolfram.com/GraphLikelihood.html.
The drawing in the paper (by A. Koroto) is featured on the cover
of J.
Phys. A: Math. Theor.

A.
Cabello, S. Severini, A. Winter, (Non)Contextuality
of Physical Theories as an Axiom, arXiv:1010.2163v1
[quantph]. See also F.
Moldoveanu, “Color
Me Surprised: Quantum Mechanics and Graph Theory are a Match Made in
Heaven”,
FQXi Community, 4 May 2011. And the following version:

A.
Cabello, S. Severini, A. Winter, Graphtheoretic
approach to quantum correlations, Phys. Rev. Lett. 112 (2014)
040401. arXiv:1401.7081
[quantph]
Two related papers that I like:

T.
Fritz, A.B. Sainz, R. Augusiak, J. Bohr Brask, R. Chaves, A.
Leverrier & A. Acín, Local
orthogonality as a multipartite principle for quantum correlations,
Nature Communications 4, Article number: 2263.

M.
Howard, J. Wallman, V. Veitch & J. Emerson, Contextuality
supplies the `magic' for quantum computation, Nature 510,
351355 (19 June 2014).
 D.
Burgarth, V. Giovannetti, L. Hogben, S. Severini, M. Young, Logic
circuits from zero forcing, Nat. Comput., July 2014 DOI
10.1007/s1104701494385. arXiv:1106.4403v1
[cs.DM]

C.
R. S. Banerji, D. MirandaSaavedra, S. Severini, M. Widschwendter,
T. Enver, J. X. Zhou, and A. E. Teschendorff,
Cellular
network entropy as the energy potential in Waddington's
differentiation landscape, Sci.
Rep. 3, Article number: 3039, 2013.

L.
C. Kwek, S. Severini, H. Su (Editors), The
Korepin Festschrift: from Statistical Mechanics to Quantum
Information Science: A Collection of Articles Written in Honor of
the 60th Birthday of Vladimir Korepin, World Scientific, 2013.
[Amazon]
See also L.C. Kwek, S. Severini, H.B. Su (guest Eds.), The
Korepin Festschrift: From Statistical Mechanics to Quantum
Information Science  A Collection of Articles Written in Honor of
the 60th Birthday of Vladimir Korepin, Int. J. Mod Phys B Vol.
26, No. 27&28 (2012). Preface

C.
Banerji, S. Severini, A. E. Teschendorff, Network
Transfer Entropy and Metric Space for Causality Inference, Phys.
Rev. E 87, 052814 (2013). arXiv:1303.0231
[condmat.disnn]

V.
Nicosia, T. Machida, R. Wilson, E. Hancock, N. Konno, V. Latora, S.
Severini, Coevolution
of networks and quantum dynamics: a generalization of the
BarabásiAlbert model of preferential attachment, J.
Stat. Mech. (2013)
P08016.
arXiv:1302.0887
[physics.socph]

A.
Cabello, M. GeoffreyParker, G. Scarpa, S. Severini, Exclusive
disjunction structures and graph representatives of local
complementation orbits, J.
Math. Phys. 54,
072202 (2013).
arXiv:1211.4250v1
[quantph]

V.
Giovannetti, S. Severini, The Kirchhoff's
MatrixTree Theorem revisited: counting spanning trees with the
quantum relative entropy, Advances in Network Complexity, A.
Mowshowitz M. Dehmer, and F.
EmmertStreib
(Eds.),
WileyVCH, 2013. arXiv:1102.2398v1
[quantph]

D.
Burgarth, D. D'Alessandro, L. Hogben, S. Severini, M. Young, Zero
forcing, linear and quantum controllability for systems evolving on
networks, IEEE
Trans.
Automat.
Contr., Vol. 99 (2013).
arXiv:1111.1475v1
[quantph]

T.
H. Hall, S. Severini, Locality
for quantum systems on graphs depends on the number field, J.
Phys. A: Math. Theor. 46
295301 (2013). arXiv:1204.3681v1
[quantph]

K.
T. Arasu, S. Severini, E. Velten, Block
weighing matrices, Cryptogr.
Commun.,
5 (2013), 201207.

L.
Mancinska, G. Scarpa, S. Severini, Generalized
KochenSpecker sets relate Quantum Coloring to EntanglementAssisted
Channel Capacity, IEEE
Trans. Inf. Theory, vol.
59:6
(2013), 18.

S.
Janson, S. Severini, An
example of graph limits of growing sequences of random graphs,
Journal of Combinatorics, Volume 4, Number 1, 67–80, 2013.
arXiv:1206.4586v1
[math.CO]

Z.H.
Chen, O. Guehne, Z.H. Ma, S. Severini, Estimating
entanglement monotones with a generalization of the Wootters
formula, Phys. Rev. Lett. 109, 200503 (2012). arXiv:1207.2889v1
[quantph] arXiv:1207.1111v1
[quantph]. Extended abstract in “AQIS2012,
Asian Quantum Information Science Conference, 2326 August, Suzhou,
China”.

Z.H.
Chen, Z.H. Ma, S. Han, S.M. Fei, S. Severini, Improved
bounds on negativity of superpositions, QIC, Vol. 12, No. 11&12
(2012) 0983–0988.

Z.H.
Chen, Z.H. Ma, J.L. Chen, S. Severini, Improved
lower bounds on generalizedmultipartiteentanglement concurrence,
Phys.
Rev. A 85, 062320 (2012). arXiv:1205.3057v1
[quantph]

H.
Buhrman, P. T. S. van der Gulik, S. Severini, D. Speijer, A
mathematical model of kinetoplastid mitochondrial gene scrambling
advantage, February 2012. arXiv:1307.1163
[qbio.PE]

C.
Godsil, S. Kirkland, S. Severini, J. Smith, Numbertheoretic
nature of communication in quantum spin systems, Phys. Rev.
Lett. 109, 050502 (2012). arXiv:1201.4822v1
[quantph] Here is a talk by S. Kirkland on this: State
Transfer in Quantum Spin Networks and the Matrix Exponential,
April 2013.

R.
Duan, S. Severini, A. Winter, On
zeroerror communication via quantum channels in the presence of
noiseless feedback, August 2011. [QIP2012]

J.
West, L. Lacasa, S. Severini, A. E. Teschendorff, Approximate
entropy of network parameters, Phys. Rev. E 85, 046111 (2012).
arXiv:1201.0045v1
[condmat.disnn]

J.
West, G. Bianconi, S. Severini, A. E. Teschendorff, Differential
network entropy reveals cancer system hallmarks, Sci. Rep. 2 :
802, 2012. See
also this version here: arXiv:1202.3015v1
[qbio.MN]. This is a talk by James West on the topic: Entropy
in the cancer cell, MoN11: Eleventh Mathematics of Networks
meeting – University of Warwick.

G.
Scarpa, S. Severini, On
KochenSpecker sets and the rank1 quantum chromatic number,
IEEE Trans. Inf. Theory, vol. 99 (2012). arXiv:1106.0712v1
[quantph] Extended abstract in “15^{th}
Workshop
in Quantum Information Processing, QIP2012,
1216 December, 2011, Montreal, Canada”. [Price for the Best
Artistic Poster] Poster

R.
Duan, S. Severini, A. Winter,
Zeroerror
communication via quantum channels and a quantum Lovasz theta
function,
IEEE
Trans. Inf. Theory, vol. PP:99 (2012). This is the extended journal
version of the following conference paper: Zeroerror communication
via quantum channels and a quantum Lovasz theta function, 2011 IEEE
International Symposium on Information Theory (IEEE ISIT 2011).
Available at IEEEXplore
[Talks]

S.
P. Jordan, T. Mansour, S. Severini, On
the degeneracy of SU(3)_k topological phases, Russ. J. Math.
Phys, Volume
19, Number 1,
(2012) 2126. arXiv:1009.0114v1
[math.CO]

K.
Anand, G. Bianconi, S. Severini, The Shannon
and the Von Neumann entropy of random networks with heterogeneous
expected degrees, Phys. Rev. E 83, 036109 (2011).
arXiv:1011.1565v2
[condmat.disnn]

K.
Zhao, A. Halu, S. Severini, G. Bianconi, Entropy
rate of nonequilibrium growing networks, Phys. Rev. E 84,
066113 (2011). arXiv:1109.0940v1
[condmat.disnn]

W.
van Dam, V. M. Kendon, S. Severini (Editors), Theory
of Quantum Computation, Communication, and Cryptography, 5th
Conference, TQC 2010, Leeds, UK, April 2010, Revised Selected
Papers, Lecture Notes in Computer Science 6519, Springer.

G.
Gutin, M. Mansour, S. Severini, A
characterization of horizontal visibility graphs and combinatorics
on words, Physica
A: Statistical Mechanics and its Applications, Volume 390, Issue 12,
15 June 2011, Pages 24212428.
arXiv:1010.1850v1
[physics.dataan]

S.
Kirkland, S. Severini, Spin
systems dynamics and faults detection in threshold networks,
Phys. Rev. A 83, 012310 (2011). arXiv:1009.3394v1
[quantph]

W.
Du, X. Li, Y. Li, S. Severini, A
note on the von Neumann entropy of random graphs, Linear Algebra
Appl., 443: 1112 (2010), 17221725.

A.
E. Teschendorff, S. Severini, Increased
entropy of signal transduction in the cancer metastasis phenotype,
BMC Systems Biology 2010, 4:104. arXiv:1007.0876v1
[qbio.MN] Qualified as 'Highly accessed'; Featured.

R.
Duan, S. Severini, A. Winter,
Zeroerror
communication via quantum channels, noncommutative graphs and a
quantum Lovasz theta function, February
2010. arXiv:1002.2514v1
[quantph]

S.
Severini,
The
3dimensional cube is the only periodic, connected cubic graph with
perfect state transfer,
2010
J. Phys.: Conf. Ser. 254 012012 (invited paper in “Quantum
Groups, Quantum Foundations, and Quantum Information: a Festschrift
for Tony Sudbery”).
arXiv:1001.0674v1
[quantph]

A.
Casaccino, S. Mancini, S. Severini, Entanglement
manipulation via dynamics in multiple quantum spin systems,
Quantum. Inf. Process. June 07, 2010. arXiv:0912.5499v1
[quantph]

A.
Hamma, F. Markopoulou, F. Caravelli, S. Lloyd, S. Severini, K.
Markstrom, A quantum BoseHubbard
model with evolving graph as toy model for emergent spacetime,
Phys. Rev. D 81, 104032 (2010). arXiv:0911.5075v2
[grqc]

C.
Godsil, S. Severini, Control
by quantum dynamics on graphs,
Phys. Rev. A 81, 052316 (2010). arXiv:0910.5397v1
[quantph]

A.
Cosentino, S. Severini,
Weight
of quadratic forms and graph states,
Phys.
Rev. A 80, 052309 (2009).
arXiv:0906.2488v1
[quantph]

F.
Markopoulou, S. Severini,
A
note on observables for counting trails and paths in graphs,
JMMA, Vol. 8, No. 3, 2009. arXiv:0906.0043v1
[math.CO]

A.
Casaccino, S. Lloyd, S. Mancini, S. Severini,
Quantum
state transfer through a qubit network with energy shifts and
fluctuations,
Int. J. Quantum Info 7:8, 14171427 (2009). arXiv:0904.4510v1
[quantph]

T.C.
Wei, S. Severini,
Matrix
permanent and entanglement of permutation symmetric states,
J.
Math. Phys. 51, 092203 (2010).
arXiv:0905.0012v1
[quantph]

S.
Vazquez, S. Severini,
Perturbation
theory in a pure exchange nonequilibrium economy,
Phys. Rev. E 81, 036102 (2010). arXiv:0904.1402v1
[qfin.TR]

A.
Hamma, D. Lidar, S. Severini,
Entanglement
and area law with a fractal boundary in a topologically ordered
phase,
Phys. Rev. A 81, 010102(R) (2010). arXiv:0903.4444v1
[quantph]
[featured in PRB Kaleidoscope Images]

D.
Djokovic, S. Severini, F. Szöllösi,
Rational
Orthogonal versus
Real
Orthogonal,
ELA, Vol. 18, pp. 649673, October 2009. arXiv:0903.2853v1
[math.CO]

S.
Bose, A. Casaccino, S. Mancini, S. Severini, Communication
in XYZ AlltoAll Quantum Networks with a Missing Link, Int. J.
Quantum Info., 2009, v.7, no. 3. arXiv:0808.0748v2
[quantph]

A.
Hamma, T. Mansour, S. Severini, Diffusion
on an Ising Chain with Kinks, Phys. Lett. A.,
Volume
373, Issue 31 (2009), Pages 26222628. arXiv:0806.4812v1
[math.CO]

S.
Klavzar, S. Severini, Tensor
2sums and entanglement,
J.
Phys. A: Math. Theor. 43 212001 Fast Track Comm. arXiv:0909.1039v2
[math.CO]

S.
Flammia, S. Severini, Weighing
matrices and optical quantum computing, J. Phys A: Math. Theor.
42 065302 (2009). arXiv:0808.2057v1
[quantph]

A.
Hamma, F. Markopoulou, I. PremontSchwarz, S. Severini,
LiebRobinson
bounds and the speed of light from topological order, Phys. Rev.
Lett. 102, 017204 (2009). arxiv:0808.2495v1
[quantph]

F.
Passerini, S. Severini, The
von Neumann entropy of networks,
December
2008. arXiv:0812.2597v1
[condmat.disnn].
See also Quantifying
complexity in networks: the von Neumann entropy,
in John Symons and Jorge Louçã (Eds.): Social
structures in communication networks, Int.
J. Agent Tech. Sys., Vol. 1, Issue 4. A version with title
“Quantifying Disorder in Networks: The von Neumann Entropy”
has been published in the book “Developments in Intelligent
Agent Technologies and MultiAgent Systems: Concepts and
Applications” (G. Trajkovski Ed.), IGI Global, 2011.

D.
Cheung , D. Maslov, S. Severini, Translation
Techniques Between Quantum Circuit Architectures, Nov 2012.

S.
Severini, Graphs of unitary matrices, Ars Comb., XC, January 2009.
arXiv:math/0303084v3
[math.CO]

A.
Bernasconi, C. Godsil, S. Severini, Quantum
Networks on Cubelike Graphs, Phys. Rev. A 78,052320 (2008).
arXiv:0808.0510v1
[quantph]

T.
Mansour, S. Severini, Counting
paths in Bratteli diagrams for SU(2)_k, EPL 86 33001.
arXiv:0806.4809v1
[math.CO]

M.
Arzano, A. Hamma, S. Severini, Hidden
entanglement at the Planck scale: loss of unitarity and the
information paradox, Mod. Phys. Lett. A25:437445, 2010.
arXiv:0806.2145v1
[hepth].
See also "A black hole's secret files: hiding information at
the Planck scale", Essay for “The Gravity Research
Foundation”, 2008.

A.
Casaccino, E. Galvao, S. Severini, Extrema
of discrete Wigner functions and applications, Phys. Rev. A 78,
022310 (2008). arXiv:0805.3466v1
[quantph]

S.
Severini, Nondiscriminatory
Propagation on Trees, J. Phys A: Math. Theor. 41 482002 (2008),
Fast Track Comm. arXiv:0805.0181v1
[math.CO]

T.
Konopka, F. Markopoulou, S. Severini, Quantum
Graphity: a model of emergent locality, Phys. Rev. D. 77, 104029
(2008). arXiv:0801.0861v1
[hepth].
See also the Cover Story of New
Scientist magazine, 3 May, 2008. M. Marshall, "Knowing
the mind of God: Seven theories of everything",
New
Scientist
(4
March 2010). K. Smith, Big
Bang theory challenged by big chill, 20 August, 2012.

M.
Batty, A. Casaccino, A. Duncan, S. Rees, S. Severini, An
application of the DeutschJozsa algorithm to formal languages and
the word problem for groups, LNCS 5106, Springer, 2008.
arXiv:0801.2801v1
[quantph]

D.
Emms, S. Severini, R. Wilson, E. Hancock, Coined
quantum walks lift the cospectrality of graphs and trees,
Pattern
Recognition, Vol 42, Issue 9 (2008), 19882002. [PDF]
 R.
Hildebrand, S. Mancini, S. Severini, Combinatorial
laplacians and positivity under partial transpose, Math. Struct.
in Comp. Science (2008), vol. 18, pp. 205–219.
arXiv:cs.CC/0607036

M.
Schork, T. Mansour, S. Severini, Noncrossing
normal ordering for functions of boson operators, Internat. J.
Theoret. Phys., Vol. 47, No 3 (2008), 832849.
arXiv:quantph/0607074

M.
Schork, T. Mansour, Commutation
Relations, Normal Ordering, and Stirling Numbers, Chapman and
Hall/CRC, 2015, is a very nice book.

Q.H.
Hou, T. Mansour, S. Severini, Partial
transpose of permutation matrices, Integers, The Electronic
Journal of Combinatorial Number Theory, Vol. 8:1, (2008).
arXiv:0709.3547v1
[math.CO]

S.
Severini, F. Szöllösi, A
further look into combinatorial orthogonality, ELA, Vol. 17
(2008) pp. 376388. arXiv:0709.3651v1
[math.CO]

M.
Schork, T. Mansour, S. Severini, A
generalization of the boson normal ordering, Phys. Letters A,
364 (2007). arXiv:quantph/0608081v2

S.
Braunstein, S. Ghosh, S. Severini, Estimation
of pure qubits on circles, J. Phys. A: Math. Theor. 40 (2007)
18091834. arXiv:quantph/0412101v1
[IOP
Select  Best papers of 2006]

L.
Clarisse, S. Ghosh, A. Sudbery, S. Severini, The
disentangling power of unitaries, Physics Letters A, 365 (2007).
arXiv:quantph/0611075v2

S.
Mancini, S. Severini, The
Quantum Separability Problem for Gaussian States, Electron.
Notes Theor. Comput. Sci., 169, Elsevier Sci. B. V., Amsterdam,
2007. arXiv:cs/0603047v2
[cs.CC]

N.
Grayson , T. Keef, S. Severini, R. Twarock, SelfAssembly
of Viral Capsids via a Hamiltonian Paths Approach: The Case of
Bacteriophage MS2, Foundations of Nanoscience (FNANO) 2007. poster

T.
Mansour, S. Severini, Enumeration
of (k,2)noncrossing partitions, Discrete Math. 308:20 (2008)
45704577. arXiv:0808.1157v1
[math.CO]

N.
Saxena, S. Severini, I. Shparlinski, Parameters
of circulant integral graphs and periodic quantum dynamics, Int.
J. Quantum Info 5, 417430 (2007). arXiv:quantph/0703236v1

M.
Schork, T. Mansour, S. Severini, Wick’s
theorem for qdeformed boson operators, J. Phys. A: Math. Theor.
40 (2007) 83938401. arXiv:quantph/0703086v1

P.
J. Cameron, A. Montanaro, M. Newman, S. Severini, A. Winter, On
the quantum chromatic number of a graph, The Electronic Journal
of Combinatorics, R81 of Volume 14(1), 2007.
arXiv:quantph/0608016v3

T.
Mansour, S. Severini, Grid
polygons from permutations and their enumeration by the kernel
method, Proceedings of The 19th International Conference on
Formal Power Series and Algebraic Combinatorics (FPSAC2007), July
26, 2007. Nankai University, Tianjin, China. arXiv:math/0603225v1
[math.CO]

G.
Gutin, A. Rafiey, S. Severini, A. Yeo, Hamilton
Cycles in Digraphs of Unitary Matrices, Discrete Appl. Math. 173
(2006), no. 13, 6778. arXiv:math/0409228v2
[math.CO]

S.
Severini, Universal
quantum computation with unlabeled qubits, J. Phys. A: Math.
Theor. 39 (2006) 85078515. arXiv:quantph/0601078v3

D.
Emms, S. Severini, R. Wilson, E. Hancock, A
matrix representation of graphs and its spectrum as a graph
invariant, The Electronic Journal of Combinatorics, R34, Volume
13(1), 2006. arXiv:quantph/0505026v2
[See also K. J. Guo, Quantum
Walks on Strongly Regular Graphs, Master Dissertation,
University of Waterloo, 2010.]

S.
Severini, On the
structure of the adjacency matrix of the line digraph of a regular
digraph, Discrete Appl. Math. 154 (2006), no 12, 16631665.
arXiv:quantph/0210055v3

S.
Braunstein, S. Ghosh, S. Severini, The
laplacian of a graph as a density matrix: a basic combinatorial
approach to separability of mixed states, Ann. Comb., 10:3
(2006), 291317. arXiv:quantph/0406165v2

S.
Severini, Twocolorable
graph states with maximal Schmidt measure, Physics Letters A,
356 (2006). arXiv:quantph/0511147v1

T.
J. Osborne, S. Severini, Quantum
Algorithms and Covering Spaces, Quantum Computers and Computing,
6:1 (2006), 122. arXiv:quantph/0403127v3

S.
Braunstein, S. Ghosh, T. Mansour, S. Severini, R. Wilson, Some
families of density matrices for which separability is easily
tested, Phys. Rev. A, 73:1, 012320 (2006).
arXiv:quantph/0508020v3

K.
B. Reid, R. Lundgren, S. Severini, D. Stewart, Quadrangularity
and Strong Quadrangularity in Tournaments, Australas. J. Combin.
34 (2006), 247260. arXiv:math/0409474v1
[math.CO]

C.
Bebeacua, T. Mansour, A. Postnikov, S. Severini, On the Xrays of
permutations, ENDM, Vol. 20, 2005. arXiv:math/0506334v1
[math.CO] [Featured
in
Jeux
et Mathématiques]

L.
Clarisse, S. Ghosh, S. Severini, A. Sudbery, Entangling
power of permutations, Phys. Rev. A 72, 012314 (2005).
arXiv:quantph/0502040v2

G.
Gutin, N. Jones, A. Rafiey, S. Severini, A. Yeo, Mediated
Digraphs and Quantum Nonlocality, Discrete Appl. Math. 150
(2005), no. 13, 4150. arXiv:math/0411653v2
[math.CO]

S.
Severini, On
the digraph of a unitary matrix, SIAM J. Matrix Anal. Appl.
(SIMAX), 25:1 (2003), 295300. arXiv:math/0205187v2
[math.CO]
Meetings
Zero
forcing and its applications, Jan 30Feb 3, American Institute
of Mathematics, San Jose, CA (Coorganizer with Shaun Fallat and
Michael Young)
LMS
Research School Combinatorics and Operators in Quantum Information
Theory, Queen’s University, Belfast, 59 September 2016.
(Coorganizer with Ivan Todorov)
 13th
Central European Quantum Information Processing Workshop, 1619
June 2016, Valtice, Czech Republic. (Invited speaker)

Logical
Structures in Computation, Simons Institute, Berkeley, CA, Aug
17Dec 16, 2016. (Long term invited participant)

International
Summer School on Complex Networks, Bertinoro, Italy, July 1115
2016. (Invited lecturer)

A
workshop on Contextuality as a Resource in Quantum Computation,
2022 June 2016, London, UK. (Coorganizer with Samson Abramsky,
Nadish de Silva, Rui Soares Barbosa)

21st
Century: Leah Clements, 'Beside',
Chisenhale
Gallery Tuesday, 8
December 2015. (Invited panellist)

Zeroerror
information, Operators, and Graphs Barcelona, 2527 November
2015. (Organizer with Andreas Winter and Giannicola Scarpa)
Workshop
on Quantum Correlations, Contextuality and All That... Again,
Natal,
November 913, 2015. (Invited participant)
 Doctoral
Workshop on Mathematical and Engineering Methods in Computer Science
(MEMICS), Telč, Czech Republic, October 2325, 2015. (Invited
lecturer)

International
Symposium on Complex Systems, Grenoble, 1417 September 2015.
(PC member)

30º
Colóquio Brasileiro de Matemática, Matemática
da Teoria Quântica, IMPA, Rio de Janeiro, 2631 July 2015.
(Invited speaker)

Network
Geometry Workshop, QMUL, 16 July 2015, London. (Invited speaker)
15th
Asian Quantum Information Science Conference, August 2430,
2015, Korea Institute for Advanced Study (KIAS), Seoul, Korea.
(Subreviewer; Long contributed talk by Runyao Duan)
 The
10th Conference on the Theory
of Quantum Computation, Communication and Cryptography (TQC15),
Université libre de Bruxelles, 20–22 May 2015.
(Steering committee member)

12th
Central European Quantum Information Processing Workshop (CEQIP15),
1821 June 2015, Telč, Czech Republic. (PC member)

Citizen
Science 2015 (CitSci2015), San Jose, California, 1112 February
2015. (PC member)

Workshop
on Quantum Metrology, Interaction, and Casual Structure,
Tsinghua University, Beijing, China, 15 December 2014. (Invited
speaker)

Postquantum
research: addressing future challenges and directions, INI,
Cambridge, UK, 1819 September 2014. (Invited speaker) Video

Symposium
on Integrability and Exact Solvability as Avatars of Symmetry,
Centre
de recherches mathématiques (CRM), Montreal, QC, 2529 August
2014. (Invited speaker)

Interdisciplinary
Symposium on Complex Systems: Florence, Italy, 1518 September
2014. (PC member)

International
School on Complex Systems, Bertinoro, Italy, July 1418, 2014.
(Invited lecturer)

New
Frontiers of Quantum Information, Ascoli Piceno, Italy, July
711, 2014. (Invited speaker)

Algebraic
Combinatorics: Spectral Graph Theory, ErdosKoRado Theorems and
Quantum Information Theory, A Conference to celebrate the work
of Chris Godsil, Fields Institute, Toronto, ON, June 2327, 2014.
(Invited speaker)

11th
Central European Quantum Information Processing Workshop,
Znojmo, Czech Republic, 58 June 2014. (Invited speaker; PC member)

The
9th Conference on the
Theory of Quantum Computation, Communication and Cryptography,
will be held at the Ngee
Ann Kongsi Auditorium, University Town, National University of
Singapore from 2123 May 2014. (Steering
committee member)

Quantum
Information Paris (QuPa),
Institut H. Poincare, Paris, France, 27 March 2014. (Invited
speaker)

Capacity
of Communication, Queen's University, Belfast, UK, 715 March
2014. (Invited speaker)

The
3^{rd}
Citizen
Cyberscience Summit,
London, UK, 2022 February, 2014. (Invited speaker)
 Workshop
on Quantum Correlations, Contextuality and All That, Natal,
December 913, 2013. (Invited speaker)

Heilbronn
Quantum Algorithms Meeting, Newton
Institute for Mathematical Science, Cambridge, 2728 November 2013.
(Invited speaker).

Video
of the talk: Graph
Isomorphism: quantum ideas

UCLParis
Quantum Connection, UCL, 45 November, 2013; including Peter
Shor's public lecture. (Coorganizer)

Interdisciplinary
Symposium on Complex Systems, Prague, Czech Republic, 1013
September 2013. (PC member)

Topological
Quantum Matter, Higgs Centre for Theoretical Physics, University
of Edinburgh, 23 September 2013. (Invited participant)

Mathematical
Challenges in Quantum Information, Newton Institute for
Mathematical Sciences, Cambridge, AugustDecember 2013 (Visiting
Fellow)

Quantum
Information and Foundations of Quantum Mechanics, University of
British Columbia, Vancouver, BC, 25 July 2013. (Invited speaker)

18th
Conference of the International Linear Algebra Society (ILAS),
Providence, Rhode Island, USA on June 37, 2013. Advances in
Combinatorial Matrix Theory and its Applications (Invited speaker)

IQC
Workshop on Quantum Computation and Complex Networks, Institute
for Quantum Computing, Waterloo, Ontario, 2426 May, 2013.
(Coorganizer)

The
8^{th}
Conference
on Theory of Quantum Computation, Communication and Cryptography,
TQC2013,
Guelph, Ontario, 2123 May, 2013. (PC Chair).

The
Oxford Future of Science Conference, Rigour
and Openess in 21^{st}
Century
Science,
1112 April 2013, Oxford. (Invited speaker)

Science
Hackday in London, Centre for Creative Collaboration, 16 March
2013. (Invited speaker)

UKRussia
Frontiers of Science, Kazan, Russia, 1115 March 2013. (Invited
delegate) [Local
website] [kpfu.ru]
[itartass]

Second
International Workshop on Adiabatic Quantum Computation,
Institute of Physics, London, UK, 68 March 2013. (Coorganizer)

Positive
Semidefinite Zeroforcing and Applications, Banff
International Research
Station
for
Mathematical Innovation and Discovery, Banff, Alberta, Canada, 2330
September, 2012. (Organizer)

Timevarying
Complex Network Analysis, University of Cambridge, 19th
September 2012. (Invited participant)

Quantum
Africa 2, 37 September, KwaZuluNatal, South Africa.
(Invited
keynote speaker)

International
Workshop on Quantum Computing and Quantum Information Processing,
August 31September 2, 2012, Beijing, China. (Invited speaker)

Quantum
Physics of Information, Summer School & Workshop, Shanghai
JiaoTong University, 2228 August 2012. (Lecturer; Program
committee) [2728, Satellite
workshop of AQIS2012]
[organized by David Cai, Runyao Duan, Andreas Winter, and me]

2012
Shanghai Conference in Algebraic Combinatorics, Shanghai
JiaoTong University, 1722 August 2012. (Contribute speaker)

2012
SIAM Conference on Applied Linear Algebra, June 18th22nd,
Valencia, Spain. (Invited speaker)

The
2012 South African School and Workshop on Theoretical Aspects of
Quantum Information and Quantum Computing, African Institute for
Mathematical Sciences, AIMS, Cape Town, South Africa. (Lecturer)

First
Cambridge Networks Day, The Sainsbury Laboratory, Cambridge, 18
May. (Invited Speaker)

Kavli
Royal Society International Scientific Centre – Function
Prediction in Complex Networks, 2829 May 2012. (Invited
participant/speaker)

Quantum
Technologies Programme 2012, Cumberland Lodge, Windsor, UK, 24
April, 2012. (Speaker)

BAMC
2012, British Applied Mathematics Colloquium 2012, 2729 March
2012. Minisymposium “Quantum Information”. (Invited
speaker)

Operator
structures in quantum information theory, Banff
International Research
Station
for
Mathematical Innovation and Discovery, Banff, Alberta, Canada, 26
February 2 March, 2012. (Invited participant)

Interdisciplinary
Symposium on Complex Systems, September 1925, 2012, Kos Island,
Greece. (Programme committee) Alan
Turing Year

Joint
Mathematics Meetings, AMS
Special Session on Matrices and Graphs, and AMS
Special Session on Mathematical Theory of Control of Quantum
Systems, John B. Hynes Veterans Memorial Convention Center,
Boston Marriott Hotel, and Boston Sheraton Hotel, Boston, MA,
January 47, 2012. (Invited speaker)

Newton
International Fellowship Day, The Royal Society, 25 October 2011.
(Invited speaker / Q&A panelist)

UCL
Town Meeting – Quantum Information and Quantum Technology,
November 9, 2011. (Programme comittee)

2011
Workshop on Algebraic Combinatorics, 1518 September 2011,
Shanghai JiaoTong University. (Invited speaker)

Quantum
Information Workshop, Benasque, Centro
de Ciencias de Benasque Pedro Pascual, July
2011. (Participant)

Quantum
Information: Codes, Geometry and Random Structures, Centre de
recherches mathematiques (CRM), Montreal, 2426/10, 2011. (Invited
speaker)

14^{th}
Workshop
in Quantum Information Processing, QIP2011,
1014 January, 2011, Singapore. Presentation Pdf
(Contributed talk)

Algebraic
Graph Theory Workshop, Banff
International Research
Station
for
Mathematical Innovation and Discovery, Banff, Alberta, Canada, 2429
April, 2011. (Invited Speaker)

Annual
International Academic Conference on Quantum and Molecular
Computing, QMC 2011,
Singapore, 1516 August 2011. (Technical Committee)

EuroComb'11,
Budapest, August 29September 2, 2011, Rényi Institute.
(Referee)

7th
Slovenian International Conference on Graph Theory, Bled,
Slovenia, June 1924, 2011. Minisymposium: Information Theory of
Graphs (Invited speaker)

5th
AsianPacific Conference on Quantum Information Science, in
conjunction with the Festschrift in honour of Vladimir Korepin,
Singapore, 2528 May 2011. (Programme Committee)

3rd
biennial Canadian Discrete and Algorithmic Mathematics Conference
(CanaDAM) May 31June 3, 2011, University of Victoria, BC, Canada.
(Invited speaker)

Interdisciplinary
Symposium on Complex Systems, 9th International Conference of
Numerical Analysis and Applied Mathematics (ICNAAM), Halkidiki,
Greece, September 1925, 2011. (Programme Committee)

The
6th
Conference
on Theory of Quantum Computation, Communication and Cryptography,
TQC2011, Madrid,
2426 May 2011. (Programme Committee)

The
5th Conference on Theory of Quantum Computation, Communication and
Cryptography, TQC2010,
University of Leeds, 1315 April, 2010. (Cochair of the Programme
Committee together with Wim van Dam)

The
3th Conference on Theory of Quantum Computation, Communication and
Cryptography, TQC2008,
The University of Tokyo, January 301 February, 2008. (Contributed
talk)

International
Program on Quantum Information (IPQI),
Institute of Physics, Bhubaneswar, Orissa, India, Jan 4th30th,
2010. (Invited lecturer)

Collaborative
Research Group for Mathematics of Quantum Information, Pacific
Institute for Mathematics Sciences (PIMS), Vancouver, BC, 20102012.
(Affiliate)

The
19th International Linear Algebra Society Conference, ILAS
2010, Pisa, 2125 June, 2010. Minisymposium: Linear Algebra and
Quantum Information Processing. (Programme Committee)

DocSpot:
Monsters From The Id, The Barbican, London, 26 May 2010. (Q&A
panelist)

AMS
2010 Fall
Southeastern Section Meeting, Richmond, VA, November 67, 2010.
Special
Session on Minimum Rank Problems. (Invited Speaker)

VideoClocks
Workshop, NABA, The New Academy of
Fine Arts, Milan (24 hours workshop), December 2009. (Lecturer with
Giuseppe Ragazzini)

CombPhys
II: "Quantum and Combinatorics" (Zakopane, Poland,
2009). (Invited speaker)

Italian
Quantum Information Science Conference, 2009,
58
November 2009, Scuola Normale Superiore, Pisa, Italy. (Contributed
talk)

Italian
Quantum Information Science Conference, 2008,
2429 October 2008, Palazzo Ducale, Camerino, Italy. (Contributed
talk)

CMS/CSHPM
Summer Meeting 2009. Memorial University of
Newfoundland, St. John's, Newfoundland,
June
6  8, 2009. (Invited speaker: Scientific Session on Algebraic
Combinatorics)

Quantum
Information and Graph Theory: emerging connections, Perimeter
Institute for Theoretical Physics, April
28  May 2, 2008. (Organizing Committee)

Joint
International Meeting of the AMS and Shanghai Math Society,
December
1721, 2008, Shanghai,
Peoples Republic of China. (Invited speaker: Special
Session on Combinatorics and Discrete Dynamical Systems)

Emergent
Gravity, August 2529, 2008, Massachusetts Institute of
Technology / Center for Theoretical Physics.

2007
International Conference on Combinatorial Physics, 2427
November, Krakow, Poland. (Invited speaker)

The
19th International Conference on Formal Power Series and Algebraic
Combinatorics (FPSAC2007), July 26, 2007, Nankai University,
Tianjin, China. (Contributed talk)

QCQC2007,
Centre for Theoretical
Studies, IIT Kharagpur,
India, December
1113, 2007. (Invited speaker)

ERATO
conference on Quantum Information Science 2005, August 2630,
2005  National Museum of Emerging Science and Innovation "Nihon
Kagaku Miraikan", JST, Tokyo, Japan. (Contributed talk)

KIASKAIST
Workshop on Quantum Information Science, Seoul, 2224 August
2005. (Invited speaker)

20th
British Combinatorial Conference
University
of Durham, 1115 July 2005. (Contributed talk)

Rutgers
Experimental Mathematics Seminar, 16 June, 2005, Rutgers
University, Department of Mathematics and
the Center for Discrete Mathematics and Theoretical Computer Science
(DIMACS).
(Invited
speaker; host: Doron
Zeilberger)

The
third conference on permutation patterns (PP2005), May 29–June
3, 2005, University of Haifa, Israel. (Invited speaker)

1st
AsiaPacific Conference on Quantum Information Science, Tainan,
Taiwan, December 1013, 2004. (Invited speaker)

Fifth
Haifa Workshop on Interdisciplinary Applications of Graph
theory, Combinatorics, and Algorithms
(Honoring
Michael O. Rabin), May 1619, 2005, CRI, Haifa, Israel. (Contributed
talk)

The
Third Haifa Workshop on Interdisciplinary Applications of Graph,
Combinatorics, and Algorithms (Honoring Peter Hammer), May
2729, 2003, 2003, CRI, Haifa, Israel. (Contributed talk)

Eurocomb'03,
Prague, Czech Republic, 812 September, 2003. (Contributed talk)
Professional
service
 Referee:

Journals:
IEEE
Transactions in Information Theory, Information
Processing Letters, Physical
Review Letters, Physical
Review A, Physical
Review E, Physical
review D, Quantum
Information and Computation, Journal
of Physics A: Mathematical and Theoretical, New
Journal of Physics, Physics
Letters A, Physics
Letter B, Physica
A, Physica
D, Journal
of Mathematical Physics, Europhysics
Letters, Chinese
Physics Letters, International
Journal of Theoretical Physics, International
Journal of Quantum Information, Annalen
der Physik, Journal of Geometry and Physics, Modern Physics
Letters B, Proceedings of the National Academy of Science India
Section A: Physical Sciences.

Acta
Mathematica Sinica, Journal
of Difference Equations and Applications, Discrete
Mathematics, Computers
& Mathematics with Applications, Discrete
and Applied Mathematics, Electronic
Journal of Combinatorics, European
Journal of Combinatorics, The
Australasian Journal of Combinatorics, Applicable
Analysis and Discrete Mathematics, Automatica,
Applied
Mathematics Letters, SIAM
Journal on Discrete Mathematics (SIDMA), Turkish
Journal of Mathematics, Proceedings
of the Edinburgh Mathematical Society.

Journal
of Statistical Mechanics, Journal
of Machine Learning Research, Central
European Journal of Mathematics, Linear
Algebra and its Applications, Pure
Mathematics and Applications, Journal
of Integer Sequences, Nature
Communications, Complex
Adaptive Systems Modeling, Entropy,
Networks,
Scientific Reports,
Mathematical
Programming (Series A), Natural
Computing, Nonlinearity,
PLoS ONE, Nature.

Conferences:
International
Colloquium on Automata, Languages and Programming (ICALP), Quantum
Information Processing (QIP), Formal Power Series and Algebraic
Combinatorics Conference (FPSAC), The Asian Conference on Quantum
Information Science (AQIS), European Conference on Combinatorics,
Graph Theory and Applications (EuroComb), IEEE Conference on
Decision and Control.
 Editorial
work:
Associate
Editor: Journal of Complex Networks (Oxford University Press),
Associate Editor: International Journal of Computer Mathematics
(Taylor & Francis), Editorial Advisory Board Member: Special
Matrices (Versita / De Gruyter), Review Editor: Frontiers in
Interdisciplinary Physics and Frontiers in Mathematical Physics
(Frontiers Media S. A.), Editor: Springer Lecture Notes in Computer
Science (1 proceedings), Editor: World Scientific (1 multiauthor
book), Editor: LIPIcs  Leibniz International Proceedings in
Informatics (1 proceeding), Guest Editor: International Journal of
Modern Physics B (1 issue), Guest Editor: Journal of Algebraic
Combinatorics (1 issue).

Grants:
Engineering
and Physical Research Council (EPSRC), Member of the Royal Society
International
Exchanges Committee (20142016), US National Security Agency 
American Mathematical Society Grants Scheme, European Commission 
Directorate General for Communications Networks, Content and
Technology Future & Emerging Technologies, the Research Council
of Norway, the Austrian Science Fund, Netherlands Organisation for
Scientific Research, Member of the Computer Science Evaluation Group
at the Natural Sciences and Engineering Research Council of Canada
(20142017), Mitacs, National Natural Science Foundation of China.
Quantum
information and graphs (Oct2011)
 Quantum
information and graphs: In
2008, at the Perimeter
Institute for Theoretical Physics, we organized a conference
titled Quantum
Information and Graph Theory: emerging connections. Below is an
incomplete list of references on this topic (Oct 2011): Graph
states: R.
Raussendorf, D.E. Browne, H.J. Briegel, Measurementbased quantum
computation with cluster states, Phys. Rev. A 68, 022312 (2003).
arXiv:quantph/0301052v2;
M.
Hein, W. Dür, J. Eisert, R. Raussendorf, M. Van den Nest, H.J.
Briegel, Entanglement in Graph States and its Applications,
Proceedings of the International School of Physics "Enrico
Fermi" on "Quantum Computers, Algorithms and Chaos",
Varenna, Italy, July, 2005. arXiv:quantph/0602096v1.
State
transfer on spin systems: M.
Christandl, N. Datta, T. C. Dorlas, A. Ekert, A. Kay, A. J. Landahl,
Perfect
Transfer of Arbitrary States in Quantum Spin Networks, Phys. Rev. A
71, 032312 (2005). arXiv:quantph/0411020v2;
C.
Godsil, State Transfer on Graphs, 2011. arXiv:1102.4898v2
[math.CO]. Quantum
expanders: A.
BenAroya, A. TaShma, Quantum
expanders and the quantum entropy difference problem, 2007.
arXiv:quantph/0702129v3;
A.
W. Harrow, R. A. Low, Efficient Quantum Tensor Product Expanders and
kdesigns, Proceedings of RANDOM 2009, LNCS, 5687:548561, 2009.
arXiv:0811.2597v3
[quantph]. Quantum
walks: D.
Aharonov, A. Ambainis, J. Kempe, U. Vazirani, Quantum
walks on graphs, Proceedings of ACM Symposium on Theory of
Computation (STOC'01), July 2001, p. 5059; A. Ambainis, Quantum
walks and their algorithmic applications, International Journal
of Quantum Information, 1:507518, 2003. arXiv:quantph/0403120v3;
M. Mohseni, P. Rebentrost, S. Lloyd, A. AspuruGuzik.
Environmentassisted
quantum walks in photosynthetic energy transfer, Journal of
Chemical Physics 129, 174106 (2008). arXiv:0805.2741v2
[quantph]; A. M. Childs, Universal
computation by quantum walk, Phys. Rev. Lett. 102, 180501
(2009). arXiv:0806.1972v1
[quantph]. Quantum
graphs: T.
Kottos and U. Smilansky, Quantum
Chaos on Graphs, Phys. Rev. Lett. 79, 4794797, (1997); U.
Smilansky, Quantum chaos on discrete graphs, 2007. arXiv:0704.3525v1
[mathph]. Graphs
of unitary matrices: L.
Deaett, The
minimum semidefinite rank of a trianglefree graph, Linear
Algebra and its Applications 434
(2011), 19451955; T. J. Osborne, Approximate Locality for Quantum
Systems on Graphs, Phys. Rev. Lett. 101, 140503 (2008).
arXiv:quantph/0611231v2.
Complexity
metrics: R.
Jozsa, On the simulation of quantum circuits, 2006.
arXiv:quantph/0603163v1;
I. L. Markov, Y. Shi, Simulating quantum computation by contracting
tensor networks, SIAM Journal on Computing, 38(3):963981, 2008.
arXiv:quantph/0511069v7;
D. Aharonov, Z. Landau, J. Makowsky, The quantum FFT can be
classically simulated, 2006, arXiv:quantph/0611156v2.
Isomorphism
(via encoding): K.
Audenaert, C. D. Godsil, G. F. Royle, T.
Rudolph,
Symmetric squares of graphs, J. Comb. Theory, Ser. B 97(1): 7490
(2007). arXiv:math/0507251v1
[math.CO]; J. K. Gamble, M. Friesen, D. Zhou, R. Joynt, S. N.
Coppersmith, Twoparticle quantum walks applied to the graph
isomorphism problem.
Phys. Rev. A, 81(5):052313, 2010. arXiv:1002.3003v1
[quantph]. Network
coding: M.
Hayashi, K. Iwama, H. Nishimura, R. Raymond, and S. Yamashita.
Quantum network coding. In STACS 2007, volume 4393 of Lecture Notes
in Computer Science, pages 610–621, 2007.
arXiv:quantph/0601088v2;
D.
Leung, J. Oppenheim, and A.Winter. Quantum network communication —
the butterfly and beyond. IEEE Transactions on Information Theory,
56(7):3478–3490, 2010. arXiv:quantph/0608223v5.
Complex
networks: S.
Perseguers, M. Lewenstein, A. Acín, J. I. Cirac,
Quantum
complex networks, Nature Physics 6, 539  543 (2010).
arXiv:0907.3283v1
[quantph]. Graphs
as channels; T. S. Cubitt, D. Leung, W. Matthews, A. Winter,
Improving zeroerror classical communication with entanglement,
Phys. Rev. Lett., 104(23):230503, 2010. arXiv:0911.5300v2
[quantph]; D.
Leung, L. Mancinska, W. Matthews, M. Ozols, A. Roy,
Entanglement
can increase asymptotic rates of zeroerror classical communication
over classical channels, 2010. arXiv:1009.1195v2
[quantph]. Quantum
colouring: C.
Godsil, M. W. Newman, Coloring an Orthogonality Graph, SIAM J.
Discrete Math. 22(2): 683692 (2008). arXiv:math/0509151v1
[math.CO]; J.
Fukawa, Hi. Imai, F. Le Gall, Quantum
Coloring Games via Symmetric SAT Games.
Presented as a long talk at the 11th Asian Quantum Information
Science Conference (AQIS 2011). Background
independent models of quantum gravity based on timedependent
graphs: A.
Hamma, F. Markopoulou, Background independent condensed matter
models for quantum gravity, New J. Phys. 13:095006, 2011.
arXiv:1011.5754v1
[grqc]; F.
Caravelli, F. Markopoulou, Properties of quantum graphity at low
temperature, Phys. Rev. D 84 024002, 2011. arXiv:1008.1340v3
[grqc]
Useful
references
 R.
Penrose, On
the nature of quantum geometry, in Magic
Without Magic,
ed. J. Klauder, Freeman, San Francisco, 1972, pp. 333354. N.
Linial, Z. Luria, An
upper bound on the number of high dimensional permutations,
arXiv:1106.0649v1
[math.CO] A. Ashikhmin, A. Robert Calderbank, W. Kewlin,
Multidimensional
Second Order ReedMuller Codes as Grassmannian Packings, ISIT
2006, Seattle, USA, July 9 14, 2006. P. Diaconis and J. Salzman,
Projection
pursuit for discrete data. IMS Collections Probability and
Statistics: Essays in Honor of David A. Freedman, Vol. 2 (2008)
265–288. arXiv:0805.3043v1
[math.ST]. B. J. Frey and D. Dueck, Clustering
by Passing Messages Between Data Points, Science
315, 972–976, February 2007. citeseerx.
Software.
D.
Jakobson, S. D.Miller, I. Rivin, Z. Rudnick,
Eigenvalue
spacings for regular graphs, IMA vol. 109 (Emerging applications of
number theory, Minneapolis, MN 1996). arXiv:hepth/0310002v1.
S. M. Pincus, Approximate
entropy as a measure of system complexity,
PNAS March 15, 1991 vol. 88 no. 6 22972301. (See our work
arXiv:1201.0045v1
[condmat.disnn].). H.
R. Kleinberg, and A. Lehman, On
the capacity of information networks,
IEEE
Transactions on Information Theory, 52(6):2345–2364, 2006. N.
Goldenfeld, L. P. Kadanoff, Simple
lessons from complexity,
Science
2 April 1999: Vol. 284 no. 5411 pp. 8789. G.
Tkacik and A M. Walczak, Information transmission in gene regulatory
networks: a review, J. Phys.: Condens. Matter 23 (2011) 153102
(31pp). arXiv:1101.4240v1
[physics.bioph]. E.
Carlstein. Nonparametric
change point estimation, The Annals of Statistics, Vol. 16, No.
1. (1988), pp. 188197. S.
Janson, D. E. Knuth, T. Łuczak, B. Pittel, The
birth of the giant component, Random Structures Algorithms 4 (1993),
no. 3, 231358. arXiv:math/9310236v1
[math.PR]. D. Deutsch, Physics,
Philosophy and Quantum Technology
(talk
PDF),
The Sixth International Conference on Quantum Communication,
Measurement and Computing, in Proceedings
of the Sixth International Conference on Quantum Communication,
Measurement and Computing, Shapiro, J.H. and Hirota, O., Eds.
(Rinton Press, Princeton, NJ. 2003). E.
A. Rietman, R. L. Karp, and J. A Tuszynski, Review
and application of group theory to molecular systems biology,
Theoretical Biology and Medical Modelling 2011, 8:21. L. A. Zager,
G. C. Verghese, Graph
similarity scoring and matching, Applied Mathematics Letters,
21:1(2008), 8694. M. M. Wilde, From Classical to Quantum Shannon
Theory, 2011. arXiv:1106.1445v2
[quantph] N. Alon, C. Avin, M. Koucky, G. Kozma, Z. Lotker, M. R.
Tuttle, Many Random Walks Are Faster Than One, Combinatorics,
Probability and Computing (2011), 20 : pp 481502. arXiv:0705.0467v2
[math.PR]. P.
Expert, T. Evans, V. D. Blondel, R. Lambiotte, Beyond Space For
Spatial Networks, PNAS 2011 108 (19) 76637668.

Planar
Separator Theorem: D.
A. Spielman, S.H. Teng (1996), Disk packings and planar separators,
Proc. 12th ACM Symposium on Computational Geometry (SCG '96), pp.
349–358; D. A. Spielman, S.H. Teng (2007), Spectral
partitioning works: Planar graphs and finite element meshes, Linear
Algebra and its Applications 421 (2–3): 284–305, J. H.
Conway, A. J. Jones, Trigonometric Diophantine equations (On
vanishing sums of roots of unity), Acta Arith. 30 (1976), no. 3,
229240. B.
Poonen, M. Rubinstein, The Number of Intersection Points Made by the
Diagonals of a Regular Polygon, SIAM
Journal on Discrete Mathematics 11 (1998), no. 1, 135156.
arXiv:math/9508209v3
[math.MG]. P.
Bourgade, J. P. Keating, Quantum
chaos, random matrix theory, and the Riemann zetafunction,
Seminaire Poincare, XIV (2010) 115153. And the seminal paper:
M.V.Berry, Riemann's
zeta function: A model for quantum chaos,
in Quantum Chaos and Statistical Nuclear Physics, T.H. Seligman and
H. Nishioka, eds., Lecture Notes in Phys. 263, SpringerVerlag, New
York, 1986, pp. 117. C. W. J. Granger, Investigating causal
relations by econometric models and crossspectral methods,
Econometrica
37:3
(1969), 424–438. Y.A. Kim, S. Wuchty, T. M. Przytycka,
Identifying
causal genes and dysregulated pathways in complex disease, PLoS
Comput Biol 7(3): e1001095. T. Ideker, N. J. Krogan, Differential
network biology, Molecular Systems Biology 8:565. T. Manke, L.
Demetrius, and M. Vingron, An
entropic characterization of protein interaction networks and
cellular robustness, J. R. Soc. Interface. 2006 December 22;
3(11): 843–850. A. E. Motter, Cascade
control and defense in complex networks, Phys. Rev. Lett. 93,
098701 (2004). T. Schreiber, Meauring
information transfer, Phys. Rev. Lett. 85, 461 (2000). H. G.
Tanner, On
the controllability of nearest neighbor interconnections,
Decision
and Control, 2004. CDC. 43rd IEEE Conference on. D. Ruelle, Is
our mathematics natural: The case of equilibrium statistical
mechanics, Bull. Amer. Math. Soc. (N.S.) Volume 19, Number 1
(1988).

J.
Paris, J. and L. Harrington,
A
Mathematical Incompleteness in Peano Arithmetic. In Handbook for
Mathematical Logic (Ed. J. Barwise).
Amsterdam,
Netherlands: NorthHolland, 1977. M. Warmuth, A
Bayes Rule
for Density Matrices, In Y. Weiss, B. Schölkopf, and J.
Platt, editors, Advances in Neural Information Processing Systems
18, pages 1457–1464. MIT Press, Cambridge, MA, 2005. M. K.
Warmuth, D. Kuzmin, Bayesian
Generalized Probability Calculus for Density Matrices, In
Proceedings of the 22^{nd}
Annual
Conference on Uncertainty in Artificial Intelligence, 2006. S.
Boyd, P. Diaconis, and L. Xiao, Fastest
Mixing Markov Chain on a Graph, SIAM Review, 46(4):667689,
2004. K.
P. Murphy, An
introduction to graphical models, 2001. J.
Gunawardena, Six
Lectures on System Biology (Cambridge 2011). Hedetniemi
conjecture. J. Cooper, Graph
Theory Study Guide. Rotor
Router Model by Jim Propp. The model involves a bug moving along
a directed graph. Igraph
is
a free software package for creating and manipulating undirected and
directed graphs. Cytoscape
is an open source software platform for visualizing complex
networks. CFinder
is
a free software for finding and visualizing overlapping dense groups
of nodes in networks, based on the Clique Percolation Method (CPM)
of Palla
et. al., Nature
435,
814818
(2005).
S.
Severini, Mathoverflow: Rewiring
graphs. KONECT
is the Koblenz Network Collection. KONECT is a project to collect
large network datasets of all types in order to perform research in
the area of network mining, collected by the Institute
of Web Science and Technologies of the University
of Koblenz–Landau. (7/2/12). Mark
Newman Network
Data. E. D. Kolaczyk, (2009), Statistical Analysis of Network
Data: Methods and Models. Springer, New York. Kappalanguage:
A rulebased language for modeling protein interaction networks. Two
interesting topics in Markov chains analysis: P. Doyle, Kemeny
constant: C. D. Meyer, Stochastic
Complementation. Smart Cities: World Economic Forum, Urban
Sustainability. Companies in Smart
Cities. Subhash
A. Khot, Nisheeth K. Vishnoi, The
Unique Games Conjecture, Integrality Gap for Cut
Problems and Embeddability of Negative Type Metrics into l_1,
2005. A.
Kavruk, V. I. Paulsen, I. G. Todorov, M. Tomforde, Tensor
products of operator systems.
J.
Funct. Anal.
261
(2011),
no.
2,
267–299.

M.V.
Berry and J.P. Keating The
Riemann zeros and eigenvalue asymptotics, SIAM Review, 41, No. 2
(1999), 236266. A.
Ferrante, M. Pavon, Matrix
completion à la Dempster by the principle of parsimony, IEEE
Trans. Inform. Theory
57
(2011),
no.
6, 39253931. Information
System on Graph Classes and their Inclusions. Yvo
Desmedt, Yongge Wang, Perfectly Secure Message Transmission
Revisited, IEEE Trans. Inform. Theory 54 (2008), 258202595.
arXiv:cs/0208041v1
[cs.CR]. Asu Ozdaglar:
Learning
and dynamics on networks, Acemoglu,
Daron, Munther Dahleh, Ilan Lobel, and Asuman Ozdaglar (2008),
Bayesian
learning in social networks, LIDS Working Paper 2780,
Massachusetts nstitute of Technology. M.
Agrawal, Axiomatic
/ Postulatory Quantum Mechanics, in Fundamental Physics in
NanoStructured Materials
and Devices (Stanford University, 2008). R.
Diestel, Graph
Theory, Electronic Edition 2010. Measuring
Worth, historical data on important economic aggregates, with
particular emphasis on nominal measures. Hà Quang Minh,
Reproducing
Kernel Hilbert Spaces and Learning Problems on the Hypercube ,
preprint, 2012. Network
Workbench: A LargeScale Network Analysis, Modeling and
Visualization Toolkit for Biomedical, Social Science and Physics
Research. Gephi The Open Graph Viz
Platform.

Measuring
complexity (by S. Lloyd): 1.
How hard is it to describe?
Entropy;
Algorithmic
Complexity or Algorithmic Information Content; Minimum Description
Length; Fisher Information; Renyi Entropy; Code Length (prefixfree,
Huffman, ShannonFano, errorcorrecting, Hamming); Chernoff
Information; Dimension; Fractal Dimension; LempelZiv Complexity. 2.
How hard is it to create? Time
Computational Complexity; Space
Computational Complexity; InformationBased Complexity; Logical
Depth; Thermodynamic Depth; Cost; Crypticity. 3.
What is its degree of organization? Metric
Entropy; Fractal Dimension; Excess Entropy; Stochastic
Complexity; Sophistication; Effective Measure Complexity; True
Measure Complexity; Topological epsilonmachine size; Conditional
Information; Conditional Algorithmic Information Content; Schema
length; Ideal Complexity; Hierarchical Complexity; Tree subgraph
diversity; Homogeneous Complexity; Grammatical Complexity.
Algorithmic Mutual Information; Channel Capacity; Correlation;
Stored Information; Organization.

S.
Bhamidi, R. Rajagopal, S. Roch, Network Delay Inference from
Additive Metrics. arXiv:math/0604367v2
[math.PR]. R.
Castro, M. Coates, G. Liang, R. Nowak and B. Yu, Network
Tomography: Recent Developments, Statistical Science, Vol. 19,
No. 3, 499–517, 2004. GraphCrunch2
is a software tool for network analysis, modelling and alignment. L.
Lovász, Very
large graphs, Current Developments in Mathematics 2008 (eds. D.
Jerison, B. Mazur, T. Mrowka, W. Schmid, R. Stanley, and S. T. Yau),
International Press, Somerville, MA (2009), 67128. A. Clauset, C.
R. Shalizi, M. E. J. Newman, Power
law distribution of empirical data, SIAM Review 51, 661703
(2009). Blonstein, D. Fahmy, H., and Grbavec, A, (1996), Issues
in the practical use of graph rewriting. Bioconductor
provides tools for the analysis and comprehension of highthroughput
genomic data. NetworkX
is a Python language software package for the creation,
manipulation, and study of the structure, dynamics, and functions of
complex networks. Pajek,
program for large networks analysis. Guess,
the graph exploration system. Pegasus,
opensource, graphmining system with massive scalability. NetLogo
is a multiagent programmable modeling environment. Massey Tutorial
on Zeroerror Information Theory, Information Theory Winter
School, La Colle Sur Loup, March 2007. D. Zelazo and M. Mesbahi,
Graphtheoretic
methods for networked dynamic systems: Heterogeneity and H_{2}
Performance,
in Efficient Modeling and Control of LargeScale Systems (J.
Mohammadpour and K.M. Grigoriadis, eds.), New York, New York:
Springer, pp. 219249.

B.
Chazelle, The
Convergence of Bird Flocking, arXiv:0905.4241v1
[cs.CG]. Arora,
S., Rao, S., and Vazirani, U. 2009., Expander
flows, geometric embeddings and graph partitioning, J. ACM 56,
2, Article 5 (April 2009). G.
Szabo, G. Fath, Evolutionary
games on graphs, Physics Reports 446 (46), 97217 (2007). L.
Vinet, A. Zhedanov, Dual 1 Hahn polynomials and perfect state
transfer, arXiv:1110.6477v3
[mathph]. Some nice
conjectures in algebraic combinatorics by Tewodros Amdeberhan (8
August 2012). T. Bu, N. Duffield, F. Lo Presti, D. Towsley, Network
Tomography on General Topology, Proc. of ACM SIGMETRICS 2002.
NetEvo is a
computing framework and collection of enduser tools designed to
allow researchers to investigate evolutionary aspects of dynamical
complex networks. P. Malacaria, F. Smeraldi, The
Thermodynamics of Confidentiality, CSF 2012: 280290, 2011. D.
Aharonov, A. TaShma, Adiabatic Quantum State Generation and
Statistical Zero Knowledge, arXiv:quantph/0301023v2.
B.
Sinaimeri, Structures
of Diversity, PhD Thesis, Sapienza University, Roma, 2009. B.
D. McKay, Hadamard
equivalence via graph isomorphism, Discrete Math. 27 (1979), no.
2, 213–214. P. Schweitzer, Problems
of Unknown Complexity, PhD Thesis, Universitat des Saarlandes,
Saarbrucken, 2009. G. Haggard, D. J. Pearce, and G. Royle, Computing
Tutte Polynomials, ACM Trans. Math. Softw. 37, 3, Article 24
(September 2010), 17 pages. Network
Coding Bibliography A. C. Kalloniatis, From
incoherence to synchronicity in the network Kuramoto model,
Phys. Rev. E (3) 82 (2010), no. 6, 066202.

M.
P. Frank, Physical
Limits of Computing, IEEE Computing in Science & Engineering
magazine, May/June 2002. K. Tsuda, Machine
learning with quantum relative entropy, International Workshop
on StatisticalMechanical Informatics 2008 (IWSMI 2008). L. H.
Kauffman, Biologic,
2002. L. G. Valiant, Evolvability, ECCC TR06120.
A beautiful bibliography on the Physics
of Algorithms (Los Alamos National Laboratory). Y. Colin de
Verdiere, Spectral
Graph Theory (Spectres de Graphes). A.
Dutta, U. Divakaranb , D. Senc , B. K Chakrabartid , T. F.
Rosenbaume, and G. Aeppli, Quantum phase transitions in transverse
ﬁeld spin models: From Statistical Physics to Quantum
Information, arXiv:1012.0653
[condmat.statmech]. M. Laurent, Semidefinite
Optimization (great lectures). Some of my favourite conjectures:
Hadamard
conjecture; Hedetniemi
conjecture; Rosenfeld
conjecture: the Shannon capacity of the complement of the Clebsch
graph is 16^(1/3). Hadwiger–Nelson
problem; The Crossing Number of the Complete Graph; Adam's
conjecture,

J.
C. Colburn, The
combinatorics of network reliability, Oxford Univ. Press, 1987.
DBPedia. Writelatex
is good. A good lecture on the Ising
model
(Frank
Krauss). S. Kauffman, L. Smolin, Combinatorial dynamics in quantum
gravity. arXiv:hepth/9809161
Richard
Feynman's lectures (on enhanced video player platform). Cook D.
J. and Holder L. B., Mining Graph Data, John Wiley & Sons, 2007.
Sperner
Capacities, 1993. J. P. Keating and N. C. Snaith (2003), Random
matrices and Lfunctions, J. Phys. A 36, pp. 28592881. Lasse
Kiviluoto, Patric R. J. Östergård, and Vesa P.
Vaskelainen. 2009, Sperner
capacity of small digraphs. Advances in Mathematics of
Communications, volume 3, number 2, pages 125133. Landau, H.G.
(1953), "On dominance relations and the structure of animal
societies. III. The condition for a score structure",
Bulletin of Mathematical Biophysics 15
(2):
143–148. (Landau's Theorem is beautiful). The
Comprehensive LaTeX
Symbols List (useful). British
Combinatorial
Bulletin
2013  University of Essex.
L. Lovasz, Information
and complexity (how to measure them?). R. L. Cilibrasi,
P. M. B. Vitanyi, Clustering
by compression, IEEE Trans. Information Theory, 51:4(2005),
1523–1545. B.
Litow, N. Deo, Graph compression and the zeros of polynomials.
Inform. Process. Lett. 92 (2004), no. 1, 39–44. P.
M. B. Vitanyi, Compressionbased
Similarity, arXiv:1110.4544
[cs.IT]. P.
M. B. Vitanyi, Meaningful
information, arXiv:cs/0111053
[cs.CC] F. Y. Wu, Potts
model and graph theory, J. Stat. Phys., 52, no. 1,2 (1988). S.
Chen, S. S. Plotkin, Statistical
mechanics of graph models and their implications for emergent
manifolds, Physical Review D, vol. 87, Issue 8, id. 084011.

U.
Feige, M. Langberg ,G. Schechtman, Graphs
with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers,
SIAM J. COMPUT. 2004 , Vol. 33, No. 6, pp. 1338–1368. I like
Graph Kernels.
R. Kondor, N. Shervashidze and K. M. Borgwardt,
The graphlet spectrum (ICML 2009) [pdf].
M. Arzano, T. W. Kephart, Y. J. Ng, From
spacetime foam to holographic foam cosmology, arXiv:grqc/0605117.
Halava,
Vesa; Karhumäki, Juhani; Nowotka, Dirk; Rozenberg, Grzegorz
Words, graphs, automata, and languages: special issue honoring the
60th birthday of Professor Tero Harju. Fund. Inform. 116 (2012), no.
14, vii–viii. 6806. F. J. Brandenburg, K. Skodinis, Finite
graph automata for linear and boundary graph languages. Theoret.
Comput. Sci. 332 (2005), no. 13, 199–232. W.
H. Zurek, Decoherence,
einselection, and the quantum origins of the classical, Rev.
Modern Phys. 75 (2003), no. 3, 715–775. C. Rigetti, et al.
Geometric Approach to Digital Quantum Information,
arXiv:quantph/0312196.
(This contains the same graphs of A.
Ashikhmin, A. Robert Calderbank, W. Kewlin, Multidimensional
Second Order ReedMuller Codes as Grassmannian Packings, ISIT
2006, Seattle, USA, July 9 14, 2006.). Y.
Choi and W. Szpankowski, Compression of graphical structures, IEEE
Transaction on Information Theory, 58, 2012; also IEEE International
Symposium on Information Theory, Seoul, 364–368, 2009. Nan Hu,
Leonidas Guibas, Spectral Descriptors for Graph Matching,
arXiv:1304.1572 [cs.CV].
I
like the problem of finding the length of the minimal
superpermutation:
N. Johnston, Nonuniqueness of minimal superpermutations. Discrete
Math. 313 (2013), no. 14, 1553–1557. arXiv:1303.4150
[math.CO]

Final
projects 201314 (COMP3091, COMPM091): 1) A
new measure of complexity for graphs: Perfect
graphs form an important family of graphs. In fact, many hard
problems can be solved efficiently for perfect graphs by using the
ellipsoid method for linear programming or ad hoc combinatorial
techniques. Trivially perfect graphs are a subfamily of perfect
graphs. The project consists on studying a technique to turn a
generic graph into a trivially perfect graph via a sequence of
operations. The minimum number of operations can be interpreted as a
new measure of graph complexity, with potential applications in the
analysis of big data. The project consists on (1) writing a computer
programme to implement the operations and (2) classify graphs
according to the new measure of complexity. 2) A
new measure of similarity for graph: Measures
of similarity for the vertices of a graph are important because they
can help to determine similarity in big data (e.g., members of a
social networks, companies in a large economy, biological data,
etc.). The project consists on (1) writing a computer programme to
implement a new measure of similarity based on a graph distance
introduced by Chartrand, Kubicki, and Schultz in late 90s, (2) apply
the measure to real world data, and (3) check the performance
against other known measures.

Timeseries
of matrices: G. Zumbach, The empirical properties of large
covariance matrices. arXiv:0903.1525
[qfin.ST]. H. Wilf, Generatingfunctionology.
Map of Combinatorics in
Korea. Some notes for the Fellowship
of the Odd Ring (Karol,
Michal, Monika, Ravi, et al.): F.
Arends, A
Lower Bound on the Size of the Smallest KochenSpecker Vector System
in Three Dimensions, Master Thesis, Oxford, 2009. (This contains
the gadget we are interested on and the proof of minimality.) E. R.
Scheinerman, D. H. Ullman, Fractional
graph theory, 2008. (Very detailed overview including the
fractional chromatic number.) V.
Lozin, Graph
Theory Notes, 2012(?). (Great basic intro to graphs.) The
Network Coding Home Page Hillary
S. W. Han, Thomas J. X. Li, Christian M. Reidys, Combinatorics
of $\ gamma
$structures.

This
a conjecture from: D. Emms, S. Severini, R. Wilson, E. Hancock,
A matrix representation of graphs and its spectrum as a graph
invariant, The Electronic Journal of Combinatorics, R34, Volume
13(1), 2006. arXiv:quantph/0505026v2
[See also K. J. Guo, Quantum Walks on Strongly Regular Graphs,
Master Dissertation, University of Waterloo, 2010.] But then there
is (at least) this paper by Jamie Smith
http://arxiv.org/pdf/1103.0262v1.pdf
“Cellular Algebras and Graph Invariants Based on Quantum
Walks” that kills the problem in the general case.

Lovasz
Conjecture: Every finite connected vertextransitive
graph contains a Hamiltonian path. Positive
Semidefinite Minimum Rank (PSMR) Conjecture (for the complement):
The PSMR of a graph plus the PSMR of its complement are no larger
than the number of vertices plus 2. The
independence number project (Craig Larson, Patrick Gaskill).
Index Coding: Local
graph coloring and index coding; Linear
index coding via semidefinite programming; The
rate of index coding;
R.
M. Gray and A. D. Wyner, “Source coding for a simple network,”
Bell System Technical Journal, vol. 53, no. 9, pp. 1681–1721,
November 1974. Perfect
sorting by reversals is interesting (Mathilde Bouvel, Cedric
Chauve, Marni Mishna and Dominique Rossin). I like this talk: The
giant component of a random subgraph of a given graph, Linyuan
Lu, 2011. The Quantum Pontiff
and other blogs: Bits of
DNA, Schroedinger's
Rat, What's new
(the Prince of mathematical blogs), The
polymath blog, ShtetlOptimized.
The CV
of Leonardo da Vinci. Open problem: Minimizing
the gate length in a logic circuit (5/2/14). G. Grimmett, The
RandomCluster Model, 2003. arXiv:math/0205237v2
[math.PR]. O.
Weiss, M. A. JimenezMontano. H.
P. Herzel, Information
Content of Protein Sequences,
J. Theor. Biol. (2000) 206, 379—386.

Stringology:
A.
Apostolico and Z. Galil, editors, Pattern
Matching Algorithms,
Oxford University Press, New York, 1997, 377 pages. M. Crochemore,
C. Hancart et T. Lecroq, Algorithmique
du texte,
Vuibert, Paris, 2001, 347 pages. M. Crochemore and W. Rytter, Text
Algorithms,
Oxford University Press, New York, 1994, 412 pages. D. Gusfield,
Algorithms
on Strings, Trees, and Sequences,
Cambridge University Press, New York, 1997, 534 pages. W. F. Smyth,
Computing
Patterns in Strings,
AddisonWesley, 2002. G.A. Stephen, String
Searching Algorithms,
World Scientific Publishing Co., 1994, 243 pages.

J.
Spencer, Nine
Lectures on Random Graphs. D. Sculley and Carla E. Brodley,
Compression
and Machine Learning: A New Perspective on Feature Space Vectors.
How
journals like Nature,
Cell and
Science
are
damaging science: The incentives offered by top journals distort
science, just as big bonuses distort banking.
P. Di Francesco, Integrable
combinatorics, ICMP2012. Bioconductor,
Open Source Software for Bioinformatics. "A scientist should be
judged not by his (papers) prizes or other honours bestowed upon
him, but by the quality of the people he has helped to produce. Let
these works speak for themselves." (Brenner); “Mathematics
is the art of giving the same name to different things: Politics is
the art of giving different names to the same thing.”
(Severi).
Mohammad Bavarian, Peter W. Shor, Information Causality,
SzemerédiTrotter and Algebraic Variants of CHSH,
arXiv:1311.5186
[quantph]. D.
Stahlke, Entanglement
and interference resources in quantum computation and communication,
PhD Thesis, Carnegie Mellon University, July 2014.
(Congratulations!). CP projects at CoMPLEX should be written in
LaTeX. A good introduction to LaTeX is "Essential
LaTeX" . I like this book: Information,
physics, and computation (2008). Compressed
fulltext indexes. D. Kovach, The computational
theory of intelligence, Dec 2014. arXiv:1412.7978
[cs.AI] (interesting philosophical perspective). M. Laurent,
Networks
and semidefinite programming, Lecture notes, 2013. A. Bookatz,
QMAcomplete
problems, 2012. M. Otto, Finite
model theory, Lecture notes 2005. R. Milo, N. Kashtan, S.
Itzkovitz, M. E. J. Newman, U. Alon, On
the uniform generation of random graphs with prescribed degree
sequences, arXiv:condmat/0312028v2
[condmat.statmech]

Computational
complexity: learning resources. Tim
Gowers
– Computational
Complexity and Quantum Computation, 12 Graduate Levels Lectures,
Cambridge 2009 (video). Luca Trevisan, Lecture
notes on computational complexity, 2002. Computational
Complexity: A Modern Approach, by Arora and Barak. Moni Naor,
Complexity
theory, 2005. "The sprawling web of known relations among
complexity classes", link
to the zoo. Michael Garey and David Johnson: Computers and
Intractability  A Guide to the Theory of NPcompleteness; Freeman,
1979. Hopcroft, Ullman and Motwani,
Introduction to Automata Theory, Languages, and Computation (second
edition), AddisonWesley, 2001 website.
Christos
Papadimitriou, Elements of the theory of computation
(PrenticeHall 1982, with Harry Lewis, second edition September
1997). Lance Fortnow's Computational
Complexity Web Log. Chee
K. Yap: Introduction to Complexity Classes. Antonina
Kolokolova lecture
notes. Zeroerror
(reprise): Xiaodong
Xu, Stanisław Radziszowski, Bounds
on Shannon capacity and Ramsey numbers for products of graphs,
IEEE Transactions on Information Theory, 59(8) (2013) 47674770. A.
Vesel, J. Zerovnik, Improved
lower bounds on the Shannon capacity of C_7,
Information
Processing Letters, Volume 81, Issue 5, 16 March 2002, Pages
277–282. Graceful
labelings: Kernels: Cubelike graphs: Graph representations: (A
fundamental problem of computer science is to determine the relative
efficiencies of different data structures for representing a given
problem (Rivest & Vuillemin, 1976). Homomorphisms:
Graph
drawing:

Graph
limits: Borgs,
Christian; Chayes, Jennifer; Lovász, László;
Sós, Vera T.; Vesztergombi, Katalin Counting graph
homomorphisms. Topics in discrete mathematics, 315–371,
Algorithms Combin., 26, Springer, Berlin, 2006. Borgs,
Christian; Chayes,
Jennifer; Lovász,
László; Sós,
Vera T.; Szegedy,
Balázs; Vesztergombi,
Katalin Graph limits and parameter testing. STOC'06:
Proceedings of the 38th Annual ACM Symposium on Theory of Computing,
261–270,
ACM,
New York, 2006.
Diaconis,
Persi; Holmes,
Susan; Janson,
Svante Threshold graph limits and random threshold graphs.
Internet
Math. 5
(2008),
no.
3, 267–320 (2009). Lovász,
László Large networks and graph limits. American
Mathematical Society Colloquium Publications, 60. American
Mathematical Society, Providence, RI, 2012.
Bollobás,
Béla; Janson,
Svante; Riordan,
Oliver Monotone graph limits and quasimonotone graphs. Internet
Math. 8
(2012),
no.
3, 187–231. Janson,
Svante Quasirandom graphs and graph limits. European
J. Combin. 32
(2011),
no.
7, 1054–1083. A talk
at IAS by Lovász. Ramsey
numbers: H.
Haanpaa, Computational
Methods for Ramsey Numbers, Helsinki University of Technology
Report, 65, 2000. M. Lauria ,P. Pudlak, V. Rodl, N. Thapen, The
complexity of proving that a graph is Ramsey, ICALP2013. Very
nice: G. Brinkmann, K. Coolsaet, J. Goedgebeur, and H. Melot, House
of graphs, a database of interesting graphs, Discrete Applied
Mathematics, 161 (2013), 311314. hog.grinvin.org.

Other
references: A. M. Childs, D. Gosset, Z. Webb, The
BoseHubbard model is QMAcomplete, ICALP14. [It also contains a
result about the XY Hamiltonian; recall that QMP is a plausible
quantum analogue of NP; Arnoldi]. D. Murfet, Logic
and linear algebra: an introduction, Jul 2014. A. Alzaga, R.
Iglesias, R. Pignol, Spectra
of symmetric powers of graphs and the WeisfeilerLehman refinements,
Journal of Combinatorial Theory, Series B 100 (2010), 671682.
http://arxiv.org/abs/0801.2322v1.
Course
on combinatorial games in finite model theory by Phokion Kolaitis.
P. Wocjan, S. Zhang, Several natural BQPcomplete problems,
arXiv:quantph/0606179
[It shows that QWGT is BQPcomplete]. E.
Knill and R. Laflamme,”Quantum
Computing and Quadratically Signed Weight Enumerators”,
Information Processing Letters 79 (4) pp. 1731 79, 2001 [It
introduces the QWGT – also it contains a beautiful link
between probabilistic and quantum computation. M.
Muzychuk and I. Ponomarenko, Association
schemes, Schur rings and the isomorphism problem for circulant
graphs. Part 1. D. Lidar, On
the quantum computational complexity of the Ising spin glass
partition function and of knot invariants, 2004 New J. Phys. 6
167. [Link between the QWGT and the spinglass partition function]
 M.
Grohe, The
quest for a logic capturing PTIME, 2008. [Fixed points logic
with nondeterministic choice operators?]. Quantum
computing and polynomial equations over Z_2. Maybe looking at
the logic there...K. Eickmeyer, M. Grohe, Ramdomization
and derandomization in descriptive complexity, LMCS (2011). [An
attempt to capture BPP; inexpressibility result for other classes?].
R. Fagin, Easier
ways to win logical games, 1997. [Use of EFgames to prove
inexpressibility results]. This is an interesting logic:
http://www.joshuasack.info/papers/qpdsol.pdf.
Y.K. Liu, M. Christandl, F. Verstraete, Nrepresentability
is QMAcomplete, Phys. Rev. Lett. 98, 110503 (2007) [an
interesting QMAcomplete problem]. M. Grohe, Equivalence
in finitevariable logics is complete for polynomial time,
Combinatorica 19:507532, 1999. [great result about Pcompleteness
of testing equivalence]. N.
Immerman, E. Lander, Describing
graphs: A firstorder approach to graph canonization, In
Complexity Theory Retrospective, pages 5981. SpringerVerlag,
1990. [fundamental result about C_k]. M.
Grohe, M. Otto, Pebble games and linear equations, arXiv:1204.1990
[cs.LO]. R.
O’Donnell, J. Wright, C. Wu, and Y.
Zhou. Hardness of
Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random
Graphs, chapter 120, pages 1659–1677. 201. Fagin's
Theorem: Anuj
Dawar lecture notes and more
general notes.
http://www.csc.kth.se/~lauria/sos14/lecturenotes/lecture9.pdf.
L. Hella. Logical hierarchies in PTIME. In Proceedings
of the 6th IEEE Symposium on Logic in Computer Science pages
360–368, 1992. M.
Mladenov, K. Kirsting, Lifted
inference via klocality, 2013. [Good description of the links
between WL and SA]. M. Fürer, On
the power of combinatorial and spectral invariants, Linear
Algebra Appl. 432 (2010), no. 9, 2373–2380. Luitpold
Babel, Irina V. Chuvaeva, Mikhail Klin, Dmitrii V. Pasechnik,
Algebraic
Combinatorics in Mathematical Chemistry. Methods and Algorithms. II.
Program Implementation of the WeisfeilerLeman Algorithm, 1997.
A. Dawar, On
tractable approximations of graph isomorphism, 2014. M. Furer,
WeisfeilerLehman
Renement Requires at Least a Linear Number of Iterations, ICALP
2001. C.
Berkholz, P. Bonsma, M. Grohe, Tight
Lower and Upper Bounds for the Complexity
of Canonical Colour Refinement, ESA 2013. Coarsest
partition problem. Quantum
spin glasses. Lovely
notes on graph theory by Vadim Lozin. P. Hell, Pavol; J.
Nešetřil, The core of a graph. Algebraic graph theory
(Leibnitz, 1989). Discrete Math. 109 (1992), no. 13, 117–126.
Three problems: color refinement; coarsest equitable partition;
floyd algorithm for collisions; VC dimension; graceful labelings;
Ulam's reconctruction conjecture:
http://www.automata.rwthaachen.de/~grohe/cap/all.pdf
http://en.wikipedia.org/wiki/Reconstruction_conjecture
http://folk.uio.no/taralgs/artikler/hovedfag.pdf
http://www.cs.yale.edu/homes/spielman/PAPERS/SGTChapter.pdf
http://pefmath2.etf.rs/files/117/860.pdf
http://vcp.med.harvard.edu/papers/matrices2.pdf
http://wwwlp.fmf.unilj.si/plestenjak/papers/nicegr.pdf
http://www.sciencedirect.com/science/article/pii/S0304397501003036
http://www.jmlr.org/papers/volume12/shervashidze11a/shervashidze11a.pdf.

ke.c.
property: Bonato's
review. GI
(nice). XiaoDong Zhang, A
survey of laplacian eigenvalues. Crossing
numbers of the complete graph: history. RichterSalazar,
Crossing
numbers (2008). Parking
functions, by Richard Stanley. Tree
bijections, by Igor Pak. SVM,
by Tristan Fletcher.
Advisees
Current:
Octavio
Zapata (PhD), Nadish de Silva (postdoc), Daniel
Temko (PhD; Awarded a Bogue Fellowship at Franziska Michor's
Laboratory, Harvard University.), Josh Lockhart (PhD), Fabiano
Andrade (scientific visitor, The State University of Ponta
Grossa, Brazil, 201415), David Roberson (postdoc; from Nov 2015),
James Townsend (PhD, joint with Mark Herbster).
Past:
Nadish
de Silva, PhD, visiting student, University of Oxford at UCL, Josh
Lockhart, MRes, UCL, Adrea Casaccino, PhD, University of Siena / MIT
(then at General Electrics). Alessandro
Cosentino, Laurea Magistrale, University of Pisa (then PhD at
University of Waterloo with John
Watrous). James West, PhD, UCL (then at a hedge
fund). Janos
Hodsagi, MRes, UCL. Lourdes Sriraja, MRes, UCL. Tommaso
Gagliardoni, Laura Magistrale, University of Perugia (then at the
Center for Advanced Security
Research Darmstadt). Soomin Kim and Emma Rahman (Nuffield
Research Placement Scheme). [CPs CoMPLEX: Thomas Wyatt, Sophie
Atkinson , Janos Hodsagi, Andrew Maher, Tim Lucas, Robert Bentham,
Teresa Attenborough], Si Bing MSci, University of Bristol. Walter
Vinci, postdoc, UCL (then postdoc at University of Southern
California), Chris
Banerji, MRes and
PhD, Awarded the UCL Faculty of Mathematical and Physical Sciences
Postgraduate Prize for outstanding achievements during the MRes year
at CoMPLEX; Recipient of the INBIOMEDvision Training Challenge Prize
2012. Hairu Xu: Visiting Student from Guangdong University of
Technology, February 2014April 2014, Banghai Wang: Academic Visitor
from Guangdong University of Technology, April 2013March 2014,
Zhihao Ma: Academic Visitor from Shanghai Jiao Tong University,
October 2011October 2012. Abdul Bhutto, Nuffield Research Placement
Scheme, Summer 2015, Zahra Najib, Nuffield Research Placement Scheme,
Summer 2015, Tianyu Ye, postdoc. Arthur Guerard, MRes, YuChing Yang,
MRes (together with Marco Grimaldi, HarperCollins).
Research
students applications:
Computer
Science: here
(PRISM); Centre for Doctoral Training in Delivering Quantum
Technologies: here;
Centre
for Mathematics, Physics and Engineering in the Life Sciences and
Experimental Biology (CoMPLEX): here.
Module
PHASGQ03 Quantum Communication and Computation for Quantum
Technologies (Strand 2: Quantum Computation and Algorithms), 2015
Strand
1: Quantum Cryptography (Fernando Brandao and Lluis Masanes); Strand
3: Quantum Error Correction and Fault Tolerance (Dan Browne); Strand
4: Lab: Quantum Key Distribution (Jeroen Elzerman). Notes:
reviewing Strand 1, Quantum Information Theory, from “PHASGQ01
Physics and Foundations of Quantum Technologies” thought by
Jonathan Oppenheim is useful.
Lecture
1 (24/02/15; Week 27). Recap and warmup:
Historical background, Ket/bra notation, quantum registers,
projective measurements in different bases, composite systems,
unitary evolution, classical limit and doubly stochastic matrices
vs. unitary matrices, qubits, superpositions, basic quantum gates
(Hadamard, bit flip, phase flip, phase gate, CNOT), Nocloning
theorem, diagrams and circuits, partial measurements, Hamiltonian
dynamics. Exercise: SWAP test. [Exercise: Entanglement in a Bell
pair.]
Lecture
2 (26/02/15; Week 27). From classical to quantum computation:
Entanglement (measuring entanglement), classical gates, Boolean
functions, Boolean circuits, recognizability, Thermodynamics of
computation: Landauer's principle, CCNOT, universal sets,
SolovayKitaev's theorem, function evaluation, parallelism, the
notion of query complexity, Deutsch's algorithm, DeutschJozsa's
algorithm, Exercise: measuring interference.
Lecture
3 (03/03/15; Week 28). The Fourier transform and its
applications: Simon's algorithm, Fourier transform (classical,
quantum), FFT algorithm, efficiency, quantum phase estimation (see
also Aram Harrow's lecture in December 2014), the Hidden Subgroup
Problem. Exercise: Fourier transform.
Lecture
4 (05/03/15; Week 28). Shor's factoring algorithm:
factoring, reduction to period finding, Shor's method for period
finding, continued fractions and postprocessing, Grouptheoretic
setting for the Fourier transform (representations, abelian vs.
nonabelian case). Exercise: Factoring.
Lecture
5 (09/03/15; Week 29). Walks: Graphs 101. Matrices
representing graphs. Spectrum. Random walks. Mixing. Quantum
approaches and physical intuition. Coined quantum walks. Grover
walks. Example: line. Average mixing (cycle and hypercube).
Continuous walks. State transfer on spin systems (perfect state
transfer, distance). Ambainis' Element Distinctness algorithm
(mention).
Lecture
6 (12/03/15; Week 29). Quantum
complexity theory: P,
NP, Pcomplete, PSPACE, NPcompleteness, Notion of polynomial
reductions, P vs NP question, BPP, BQP, QMA, inclusion diagrams
(classical and quantum classes). Reference: J. Watrous, Quantum
Computational Complexity, arXiv:0804.3401
[quantph]
Lecture
7 (17/03/15; Week 30). Hamiltonian
complexity [Guest lecturer: Toby
Cubitt]: Quantum
computation aims to engineer complex manybody systems to process
information in ways that would not be possible classically.
Manybody physics aims to understand the complex behaviour of
naturallyoccurring manybody systems. In a sense, they are two
sides of the same coin. We will investigate the computational
complexity of quantum manybody systems, culminating in Kitaev's
seminal proof of QMAhardness of the ground state problem for local
Hamiltonians.
Lecture
8 (18/03/15; Week 30). Grover's
search: Unstructured
database search, Grover's algorithm, Grover's iterate, Geometric
argument, Search via continuous walks.
Lecture
9 (20/03/15; Week 30). Adiabatic
computation [Guest lecturer: Andrew
Green]: Amongst
the many remarkable changes in viewpoint that have occurred in
condensed matter in recent years, notions of quantum information and
entanglement are perhaps the most prominent. Adiabatic quantum
computation provides an arena where the overlap between condensed
matter physics and quantum information is most direct. Ideas and
analytical methods from quantum phase transitions, manybody
localization, outofequilibrium dynamics and the dynamics of
decoherence may all be used to assess its power and limitations and
provide a complementary view to those of the quantum information
theorists. I will review some of the basic ideas of adiabatic
computation  from the performance of an ideal computation, to the
limiting effects of the environment and how one might hope to
mitigate them. To do this, I will use tools of Langevin equations,
matrix product states and tensor networks. I will spend half an hour
or so at the blackboard introducing these ideas as appropriate
during the talk.
General
references:
J.
Watrous, CPSC 519/619, University of Waterloo: Quantum
Computation, 2006.
J.
Preskill, Ph219/CS219, Caltech, Quantum Computation, 201314.
Chapter
6
P.
Kaye, R. Laflamme, and M. Mosca, An Introduction to Quantum
Computing, Oxford University Press (2007).
M.
A. Nielsen and I. L. Chuang, Quantum Computation and Quantum
Information, Cambridge University Press (2000).
S.
Aaronson, PHYS771, University of Waterloo, Quantum
Computing Since Democritus, 2006.
S.
Arora and B. Barak, Complexity theory: a modern approach, (free
pdf draft), Cambridge University Press (2007).
Module
PHASGQ03 2016: Syllabus
See
general references of 2015. Mostly similar to the 2015 lectures.
Ashley Montanaro as a guest lecturer.
Recap
and warmup: Historical
background, Ket/bra notation, quantum registers, projective
measurements in different bases, composite systems, unitary
evolution, classical limit and doubly stochastic matrices vs. unitary
matrices, qubits, superpositions, basic quantum gates (Hadamard, bit
flip, phase flip, phase gate, CNOT), Nocloning theorem, diagrams and
circuits, partial measurements, Hamiltonian dynamics. Exercises
(C_swap). From
classical to quantum computation: Entanglement
(measuring entanglement), classical gates, Boolean functions, Boolean
circuits. A bit about thermodynamics of computation: Landauer's
principle, CCNOT, universal sets, SolovayKitaev's theorem, function
evaluation in a quantum computer, parallelism, the notion of query
complexity, Deutsch's algorithm, DeutschJozsa's algorithm, Exercise:
measuring interference. (Interference as an ingredient for quantum
speedup: the power of negative numbers in probability densities.)
The
Fourier transform and its applications: Simon's
algorithm, Fourier transform (classical, quantum), FFT algorithm,
efficiency, quantum phase estimation, Hidden Subgroup Problem (HSP).
Exercise: Fourier transform. Shor's
factoring algorithm: factoring,
reduction to period finding, Shor's method for period finding,
continued fractions and postprocessing, Grouptheoretic setting for
the Fourier transform (representations, abelian vs. nonabelian case).
Graph isomorphism as an HSP. Grover's
search: Unstructured
database search, Grover's algorithm, Grover's iterate, Geometric
argument, Search via continuous walks. Optimality. Walks:
Graphs
101: see Diestel's book.
Matrices representing graphs, Spectrum. Random walks, Mixing time and
the eigenvalue gap and limiting distributions, Quantum approaches and
physical intuition, Coined quantum walks, Grover walks (meaning, with
Grover coin), Average and instantaneous mixing (cycle and hypercube),
Continuous walks, State transfer on spin systems (perfect state
transfer, pretty good state transfer). Other
models of quantum computation: Graph
states (two definitions), the cluster state, measurement based
quantum computation, entanglement as a resource, the adiabatic
theorem, adiabatic quantum computation, eigenvalue gap (again, but in
a different context), universality, examples of algorithms (Grover
search), issues concerning adiabatic quantum computation. See this
great talk
by Andrew Childs. Quantum
complexity theory [Guest lecturer: Ashley
Montanaro]: P,
NP, Pcomplete, PSPACE, NPcompleteness, Notion of polynomial
reductions, P vs NP question, BPP, BQP, QMA, inclusion diagrams
(classical and quantum classes). Reference: J. Watrous, Quantum
Computational Complexity, arXiv:0804.3401
[quantph]. Hamiltonian
complexity [Guest lecturer: Toby
Cubitt]: Quantum
computation aims to engineer complex manybody systems to process
information in ways that would not be possible classically. Manybody
physics aims to understand the complex behaviour of
naturallyoccurring manybody systems. In a sense, they are two sides
of the same coin. We will investigate the computational complexity of
quantum manybody systems, culminating in Kitaev's seminal proof of
QMAhardness of the ground state problem for local Hamiltonians.