am Professor in Physics
of Information and a Royal
Society University Research Fellow with the UCL
of Computer Science, where I
started our group in Quantum
Our activities are part of UCLQ: UCL
Quantum Science and Technology Institute. At present, I am also a
Visiting Chair Professor with the Institute
of Natural Sciences at Shanghai Jiao Tong University, as a
recipient of a 1000 Talents Program grant – my page at SJTU is
other links at UCL are CoMPLEX
Research Group and UCL
Institute of Origins. Here is a page for the Quantum
Computing, Information, and Algebras of Operators (QCIAO)
was a Newton International Fellow with the Department
of Physics & Astronomy at UCL. I was a Post-Doctoral Research
Fellow of the Institute for Quantum
Computing and the Department
of Combinatorics & Optimization at the University
of Waterloo, mentored by Michele
Mosca (Quantum Computing), and a Post-Doctoral Research Assistant
in the Department of Computer
Science and the Department
of Mathematics at the University
of York mentored by Tony Sudbery and Edwin Hancock. 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, without graduating, and Philosophy (Logic) at the
University of Florence,
where I got my laurea
(pre-Bologna). My long term scientific visits include CRI,
Institute for Theoretical Physics,
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) (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.
Andrea Rocchetto, Scott Aaronson, Simone
Severini, Gonzalo Carvacho, Davide Poderini, Iris Agresti, Marco
Bentivegna, Fabio Sciarrino, Experimental
learning of quantum states, arXiv:1712.00127
Andrew Hallam, Edward Grant, Vid Stojevic,
Simone Severini, Andrew G. Green, Compact
Neural Networks based on the Multiscale Entanglement Renormalization
Andrea Rocchetto, Edward Grant, Sergii
Strelchuk, Giuseppe Carleo, Simone Severini, Learning hard quantum
distributions with variational autoencoders, arXiv:1710.00725v1
[quant-ph]. Conference version in Machine
Learning for Molecules and Materials NIPS 2017 Workshop.
Banerji, Maryna Panamarova, Husam Hebaishi, Robert B. White,
Frédéric Relaix, Simone Severini, Peter S. Zammit,
PAX7 target genes are globally repressed in FSHD skeletal muscle,
Submitted, August 2017.
Simone Severini, Weak Modular Product of Bipartite Graphs, Bicliques
and Isomorphism, July 2017. arXiv:1707.05179
Mark Herbster, Alessandro Davide Ialongo, Massimiliano Pontil,
Andrea Rocchetto, Simone Severini, Leonard Wossnig, Quantum machine
learning: a classical perspective, July 2017. arXiv:1707.08561v2
[quant-ph] Accepted for publication in Proc. Royal Soc. A.
T.P. Le, Ludovica
Donati, Simone Severini, Filippo Caruso,
How to Suppress Dark States in Quantum Networks and Bio-Engineered
Structures, July 2017. arXiv:1707.07482
J. Lockhart, O.
Guehne and S. Severini, Combinatorial entanglement, Eurocomb2017.
See also, J. Lockhart, O. Guehne and S. Severini, Entanglement
properties of quantum grid graphs, May 2017. arXiv:1705.09261
Daniel Temko, Ian
Tomlinson, Simone Severini, Benjamin Schuster-Boeckler, Trevor
effects of mutational process and selection on driver mutations
across cancer types, June 2017. https://doi.org/10.1101/149096
A. Dawar, S.
Severini, O. Zapata, Pebble games and cospectral graphs,
A. Atserias, P.
Kolaitis, S. Severini, Generalized
satisfiability problems via operator assignments, April 2017.
[cs.LO] Poster at STOC 2017
Theory Fest. Conference version in FCT2017.
paper award at FCT2017.
D. E. Roberson, R. Šámal, S. Severini, A.
Varvitsiotis, Quantum and
non-signalling graph isomorphisms, November 2016.
[quant-ph] Conference version in ICALP2017.
Dairyko, Leslie Hogben, Jephian C.-H. Lin, Joshua Lockhart, David
Roberson, Simone Severini, Michael Young, Note
on von Neumann and Rényi entropies of a graph, Linear
Algebra and its Applications, Volume 521, 15 May 2017, Pages
240-253, ISSN 0024-3795,
G. Coutinho, C. Godsil, S. Severini, Pretty
Good State Transfer in Qubit Chains – The Heisenberg
Hamiltonian, Journal of Mathematical Physics
032202 (2017). arXiv:1608.04722
S. Severini, Permutation graphs and unique games, August 2016.
Lockhart, Giorgia Minello, Luca Rossi, Simone Severini, and Andrea
Torsello. Edge Centrality via the Holevo Quantity, pages 143-152.
Springer International Publishing, Cham, 2016. URL:
Rossi, Simone Severini, and Andrea Torsello. The Average Mixing
Matrix Signature, pages 474-484. Springer International Publishing,
Cham, 2016. URL: http://dx.doi.org/10.1007/978-3-319-49055-7_42,
S. Severini, Combinatorial
entanglement, May 2016. arXiv:1605.03564
Dawar, S. Severini, O. Zapata, Descriptive
complexity of graph spectra, March 2016. arXiv:1603.07030
23rd Workshop on Logic, Language, Information and Computation.
August 16th-19th, 2016. Puebla, Mexico.
Gnacinski, M. Rosicka, R. Ramanathan, K. Horodecki, M. Horodecki,
P. Horodecki, S. Severini, Linear
game non-contextuality and Bell inequalities - a graph-theoretic
[quant-ph]. 2016 New J. Phys. 18 045020.
R. Hancock, L. Rossi, S. Severini, A, Torsello, R. C. Wilson, O.
Zapata, Quantum-Inspired Graph Matching, Workshop
on Quantum Machine Learning (as part of NIPS 2015), October 2015
Jurisic, A. Munemasa, S. Severini (Eds.), Algebraic
Combinatorics: Spectral Graph Theory, Erdos-Ko-Rado Theorems and
Quantum Information Theory, Special issue to celebrate the work
of Chris Godsil, Journal of Algebraic Combinatorics, Volume 43,
Number 4, June 2016.
Chen, Z. Ma, T. Gao, S. Severini, A
combinatorial criterion for k-separability of
multipartite Dicke states, November 2015. arXiv:1511.00103
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, accepted for publication in Nat.
R. S. Banerji, Network theoretic tools in the analysis of complex
diseases, PhD thesis, June 2015.
Caravelli, T. Mansour, Sindoni, S. Severini, On
moments of the integrated exponential Brownian motion, Europ. J.
Phys., July 2016; 131:245. arXiv:1509.05980
Duan, S. Severini, A. Winter, On zero-error
communication via quantum channels in the presence of noiseless
Trans. Inf. Theory, 62:9 (2016), 5260-5277.
E. Teschendorff, C. R. S. Banerji , S. Severini , R. Kuehn , P.
signaling entropy in cancer requires the scale-free property of
protein interaction networks, arXiv:1504.00120
[q-bio.MN], Sci. Rep. 5, Article number 9646, 2015.
R. S. Banerji, S. Severini, C. Caldas, A. E. Teschendorff,
signalling entropy determines clinical outcome in breast and lung
cancer, PLoS Comput Biol 11(3): e1004115 (2015).
Hogben, K. Palmowski, D. E. Robertson, S. Severini, Orthogonal
representations, projective ranks, and fractional minimum positive
semidefinite rank: connections and new directions, February
[math.CO] (accepted in ELA)
R. S. Banerji, P. Knopp, L. A. Moyle, S. Severini, R. W. Orrell, A.
E. Teschendorff, P. S. Zammitt, β-catenin
is central to DUX4-driven network rewiring in Facioscapulohumeral
muscular dystrophy, J. R. Soc. Interface, 26 Nov 2014.
Sparsification and Rewiring
a differential network algorithm based on information theoretic
principles that can detect
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 sub-network,
which is sparsified to describe pathways altered between phenotypes.
V. I. Paulsen, S.
Severini, D. Stahlke, I. G. Todorov, A. Winter, Estimating
quantum chromatic numbers, Journal of Functional Analysis 270
(2016), pp. 2188-2222. arXiv:1407.6918
B.-H. Wang, H.-R.
Xu, S. Campbell, S. Severini, Characterization
and properties of weakly optimal entanglement witnesses, QIC
15:13&14 (2015), 1109-1121. arXiv:1407.0870
T. Cubitt, L.
Mancinska, D. Roberson, S. Severini, D. Stahlke, and A. Winter,
on entanglement assisted source-channel coding via the Lovasz theta
number and its variants, IEEE
Trans. Inf. Theory. 60:11,
7330-7340 (2014). arXiv:1310.7120
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),
A. Chailloux, L.
Mančinska, G. Scarpa, S. Severini, Graph-theoretical
Bounds on the Entangled Value of Non-local Games,
[quant-ph], LIPIcs, Vol. 27 (TQC2014).
J.-Y. Wu, M. Rossi,
H. Kampermann, S. Severini, L.-C. Kwek, C. Macchiavello, D. Bruß,
graph states and their entanglement properties, Phys. Rev. A 89,
052335 (2014), Editor's choice, arXiv:1403.3828
Isomorphism Game on crowdcrafting.org;
Isomorphism: Quantum Ideas
W. Vinci, S. Boixo,
K. Markstrom, A. Roy, F. Spedalieri, P. Warburton, S. Severini,
the Shape of the Ising Model with a Programmable
Superconducting-Flux Annealer, Sci. Rep. 4, Article Number:
5703, 2014. arXiv:1307.1114
H. Buhrman, P. T.
S. van der Gulik, S. Severini, D. Speijer, A
mathematical model of kinetoplastid mitochondrial gene scrambling
S. Kirkland, S.
partitions: graph partitions from the frustrated Kuramoto model
generalise equitable partitions, Appl. Anal. Discr. Math. (9),
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
Z.-H. Ma, C. Yao,
Z.-H. Chen, S. Severini, A. Serafini,
A universal memory-assisted
entropic uncertainty relation, Sci.
(2014), 1703. arXiv:1302.1011
T. Feng, S.
channels from association schemes, January 2013. arXiv:1301.1166
S. Severini , F.
Brandao (Eds.), 8th
Conference on the Theory of Quantum Computation, Communication and
Cryptography (TQC 2013), Revised Selected Papers, LIPIcs-Leibniz
International Proceedings in Informatics, Vol. 22, 2013.
R. S. Banerji, T. Mansour, S. Severini, A
notion of graph likelihood and an infinite monkey theorem, J.
Phys. A: Math. Theor.
[cs.DM]. See also Weisstein,
Eric W. "Graph Likelihood." From MathWorld--A
Wolfram Web Resource.
The drawing in the paper (by A. Koroto) is featured on the cover
Phys. A: Math. Theor.
Cabello, S. Severini, A. Winter, (Non)Contextuality
of Physical Theories as an Axiom, arXiv:1010.2163v1
[quant-ph]. See also F.
Me Surprised: Quantum Mechanics and Graph Theory are a Match Made in
FQXi Community, 4 May 2011. And the following version:
Cabello, S. Severini, A. Winter, Graph-theoretic
approach to quantum correlations, Phys. Rev. Lett. 112 (2014)
Two related papers that I like:
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.
Howard, J. Wallman, V. Veitch & J. Emerson, Contextuality
supplies the `magic' for quantum computation, Nature 510,
351--355 (19 June 2014).
Burgarth, V. Giovannetti, L. Hogben, S. Severini, M. Young, Logic
circuits from zero forcing, Nat. Comput., July 2014 DOI
C. R. S. Banerji,
D. Miranda-Saavedra, 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,
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.
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
V. Nicosia, T.
Machida, R. Wilson, E. Hancock, N. Konno, V. Latora, S. Severini,
of networks and quantum dynamics: a generalization of the
Barabási-Albert model of preferential attachment, J.
Stat. Mech. (2013)
A. Cabello, M.
Geoffrey-Parker, G. Scarpa, S. Severini, Exclusive
disjunction structures and graph representatives of local
complementation orbits, J.
Math. Phys. 54,
Giovannetti, S. Severini, The Kirchhoff's
Matrix-Tree Theorem revisited: counting spanning trees with the
quantum relative entropy, Advances in Network Complexity, A.
Mowshowitz M. Dehmer, and F.
Wiley-VCH, 2013. arXiv:1102.2398v1
Burgarth, D. D'Alessandro, L. Hogben, S. Severini, M. Young, Zero
forcing, linear and quantum controllability for systems evolving on
Contr., Vol. 99 (2013).
T. H. Hall, S.
for quantum systems on graphs depends on the number field, J.
Phys. A: Math. Theor. 46
295301 (2013). arXiv:1204.3681v1
K. T. Arasu, S.
Severini, E. Velten, Block
weighing matrices, Cryptogr.
5 (2013), 201-207.
L. Mancinska, G.
Scarpa, S. Severini, Generalized
Kochen-Specker sets relate Quantum Coloring to Entanglement-Assisted
Channel Capacity, IEEE
Trans. Inf. Theory, vol.
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.
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
[quant-ph]. Extended abstract in “AQIS2012,
Asian Quantum Information Science Conference, 23-26 August, Suzhou,
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
Z.-H. Chen, Z.-H.
Ma, J.-L. Chen, S. Severini, Improved
lower bounds on generalized-multipartite-entanglement concurrence,
Rev. A 85, 062320 (2012). arXiv:1205.3057v1
H. Buhrman, P. T.
S. van der Gulik, S. Severini, D. Speijer, A mathematical model of
kinetoplastid mitochondrial gene scrambling advantage, February
Godsil, S. Kirkland, S. Severini, J. Smith, Number-theoretic
nature of communication in quantum spin systems, Phys. Rev.
Lett. 109, 050502 (2012). arXiv:1201.4822v1
[quant-ph] Here is a talk by S. Kirkland on this: State
Transfer in Quantum Spin Networks and the Matrix Exponential,
Duan, S. Severini, A. Winter, On
zero-error communication via quantum channels in the presence of
noiseless feedback, August 2011. [QIP2012]
West, L. Lacasa, S. Severini, A. E. Teschendorff, Approximate
entropy of network parameters, Phys. Rev. E 85, 046111 (2012).
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
[q-bio.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.
Scarpa, S. Severini, On
Kochen-Specker sets and the rank-1 quantum chromatic number,
IEEE Trans. Inf. Theory, vol. 99 (2012). arXiv:1106.0712v1
[quant-ph] Extended abstract in “15th
in Quantum Information Processing, QIP2012,
12-16 December, 2011, Montreal, Canada”. [Price for the Best
Artistic Poster] Poster
Duan, S. Severini, A. Winter,
communication via quantum channels and a quantum Lovasz theta
Trans. Inf. Theory, vol. PP:99 (2012). This is the extended journal
version of the following conference paper: Zero-error communication
via quantum channels and a quantum Lovasz theta function, 2011 IEEE
International Symposium on Information Theory (IEEE ISIT 2011).
Available at IEEEXplore
P. Jordan, T. Mansour, S. Severini, On
the degeneracy of SU(3)_k topological phases, Russ. J. Math.
19, Number 1,
(2012) 21-26. arXiv:1009.0114v1
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).
Zhao, A. Halu, S. Severini, G. Bianconi, Entropy
rate of non-equilibrium growing networks, Phys. Rev. E 84,
066113 (2011). arXiv:1109.0940v1
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.
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 2421-2428.
Kirkland, S. Severini, Spin
systems dynamics and faults detection in threshold networks,
Phys. Rev. A 83, 012310 (2011). arXiv:1009.3394v1
Du, X. Li, Y. Li, S. Severini, A
note on the von Neumann entropy of random graphs, Linear Algebra
Appl., 443: 11-12 (2010), 1722-1725.
E. Teschendorff, S. Severini, Increased
entropy of signal transduction in the cancer metastasis phenotype,
BMC Systems Biology 2010, 4:104. arXiv:1007.0876v1
[q-bio.MN] Qualified as 'Highly accessed'; Featured.
Duan, S. Severini, A. Winter,
communication via quantum channels, non-commutative graphs and a
quantum Lovasz theta function, February
3-dimensional cube is the only periodic, connected cubic graph with
perfect state transfer,
J. Phys.: Conf. Ser. 254 012012 (invited paper in “Quantum
Groups, Quantum Foundations, and Quantum Information: a Festschrift
for Tony Sudbery”).
Casaccino, S. Mancini, S. Severini, Entanglement
manipulation via dynamics in multiple quantum spin systems,
Quantum. Inf. Process. June 07, 2010. arXiv:0912.5499v1
Hamma, F. Markopoulou, F. Caravelli, S. Lloyd, S. Severini, K.
Markstrom, A quantum Bose-Hubbard
model with evolving graph as toy model for emergent spacetime,
Phys. Rev. D 81, 104032 (2010). arXiv:0911.5075v2
Godsil, S. Severini, Control
by quantum dynamics on graphs,
Phys. Rev. A 81, 052316 (2010). arXiv:0910.5397v1
Cosentino, S. Severini,
of quadratic forms and graph states,
Rev. A 80, 052309 (2009).
Markopoulou, S. Severini,
note on observables for counting trails and paths in graphs,
JMMA, Vol. 8, No. 3, 2009. arXiv:0906.0043v1
Casaccino, S. Lloyd, S. Mancini, S. Severini,
state transfer through a qubit network with energy shifts and
Int. J. Quantum Info 7:8, 1417-1427 (2009). arXiv:0904.4510v1
Wei, S. Severini,
permanent and entanglement of permutation symmetric states,
Math. Phys. 51, 092203 (2010).
Vazquez, S. Severini,
theory in a pure exchange non-equilibrium economy,
Phys. Rev. E 81, 036102 (2010). arXiv:0904.1402v1
Hamma, D. Lidar, S. Severini,
and area law with a fractal boundary in a topologically ordered
Phys. Rev. A 81, 010102(R) (2010). arXiv:0903.4444v1
[featured in PRB Kaleidoscope Images]
Djokovic, S. Severini, F. Szöllösi,
ELA, Vol. 18, pp. 649-673, October 2009. arXiv:0903.2853v1
Bose, A. Casaccino, S. Mancini, S. Severini, Communication
in XYZ All-to-All Quantum Networks with a Missing Link, Int. J.
Quantum Info., 2009, v.7, no. 3. arXiv:0808.0748v2
Hamma, T. Mansour, S. Severini, Diffusion
on an Ising Chain with Kinks, Phys. Lett. A.,
373, Issue 31 (2009), Pages 2622-2628. arXiv:0806.4812v1
Klavzar, S. Severini, Tensor
2-sums and entanglement,
Phys. A: Math. Theor. 43 212001 Fast Track Comm. arXiv:0909.1039v2
Flammia, S. Severini, Weighing
matrices and optical quantum computing, J. Phys A: Math. Theor.
42 065302 (2009). arXiv:0808.2057v1
Hamma, F. Markopoulou, I. Premont-Schwarz, S. Severini,
bounds and the speed of light from topological order, Phys. Rev.
Lett. 102, 017204 (2009). arxiv:0808.2495v1
Passerini, S. Severini, The
von Neumann entropy of networks,
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 Multi-Agent Systems: Concepts and
Applications” (G. Trajkovski Ed.), IGI Global, 2011.
Cheung , D. Maslov, S. Severini, Translation
Techniques Between Quantum Circuit Architectures, Nov 2012.
Severini, Graphs of unitary matrices, Ars Comb., XC, January 2009.
Bernasconi, C. Godsil, S. Severini, Quantum
Networks on Cubelike Graphs, Phys. Rev. A 78,052320 (2008).
Mansour, S. Severini, Counting
paths in Bratteli diagrams for SU(2)_k, EPL 86 33001.
Arzano, A. Hamma, S. Severini, Hidden
entanglement at the Planck scale: loss of unitarity and the
information paradox, Mod. Phys. Lett. A25:437-445, 2010.
See also "A black hole's secret files: hiding information at
the Planck scale", Essay for “The Gravity Research
Casaccino, E. Galvao, S. Severini, Extrema
of discrete Wigner functions and applications, Phys. Rev. A 78,
022310 (2008). arXiv:0805.3466v1
Propagation on Trees, J. Phys A: Math. Theor. 41 482002 (2008),
Fast Track Comm. arXiv:0805.0181v1
Konopka, F. Markopoulou, S. Severini, Quantum
Graphity: a model of emergent locality, Phys. Rev. D. 77, 104029
See also the Cover Story of New
Scientist magazine, 3 May, 2008. M. Marshall, "Knowing
the mind of God: Seven theories of everything",
March 2010). K. Smith, Big
Bang theory challenged by big chill, 20 August, 2012.
Batty, A. Casaccino, A. Duncan, S. Rees, S. Severini, An
application of the Deutsch-Jozsa algorithm to formal languages and
the word problem for groups, LNCS 5106, Springer, 2008.
Emms, S. Severini, R. Wilson, E. Hancock, Coined
quantum walks lift the cospectrality of graphs and trees,
Recognition, Vol 42, Issue 9 (2008), 1988-2002. [PDF]
Hildebrand, S. Mancini, S. Severini, Combinatorial
laplacians and positivity under partial transpose, Math. Struct.
in Comp. Science (2008), vol. 18, pp. 205–219.
Schork, T. Mansour, S. Severini, Noncrossing
normal ordering for functions of boson operators, Internat. J.
Theoret. Phys., Vol. 47, No 3 (2008), 832-849.
]. [Schork, T. Mansour, Commutation
Relations, Normal Ordering, and Stirling Numbers, Chapman and
Hall/CRC, 2015, is a very nice book.]
Hou, T. Mansour, S. Severini, Partial
transpose of permutation matrices, Integers, The Electronic
Journal of Combinatorial Number Theory, Vol. 8:1, (2008).
Severini, F. Szöllösi, A
further look into combinatorial orthogonality, ELA, Vol. 17
(2008) pp. 376-388. arXiv:0709.3651v1
Schork, T. Mansour, S. Severini, A
generalization of the boson normal ordering, Phys. Letters A,
364 (2007). arXiv:quant-ph/0608081v2
Braunstein, S. Ghosh, S. Severini, Estimation
of pure qubits on circles, J. Phys. A: Math. Theor. 40 (2007)
Select - Best papers of 2006]
Clarisse, S. Ghosh, A. Sudbery, S. Severini, The
disentangling power of unitaries, Physics Letters A, 365 (2007).
Mancini, S. Severini, The
Quantum Separability Problem for Gaussian States, Electron.
Notes Theor. Comput. Sci., 169, Elsevier Sci. B. V., Amsterdam,
Grayson , T. Keef, S. Severini, R. Twarock, Self-Assembly
of Viral Capsids via a Hamiltonian Paths Approach: The Case of
Bacteriophage MS2, Foundations of Nanoscience (FNANO) 2007. poster
Mansour, S. Severini, Enumeration
of (k,2)-noncrossing partitions, Discrete Math. 308:20 (2008)
Saxena, S. Severini, I. Shparlinski, Parameters
of circulant integral graphs and periodic quantum dynamics, Int.
J. Quantum Info 5, 417-430 (2007). arXiv:quant-ph/0703236v1
Schork, T. Mansour, S. Severini, Wick’s
theorem for q-deformed boson operators, J. Phys. A: Math. Theor.
40 (2007) 8393-8401. arXiv:quant-ph/0703086v1
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.
T. Mansour, S.
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
2-6, 2007. Nankai University, Tianjin, China. arXiv:math/0603225v1
Gutin, A. Rafiey, S. Severini, A. Yeo, Hamilton
Cycles in Digraphs of Unitary Matrices, Discrete Appl. Math. 173
(2006), no. 1-3, 67-78. arXiv:math/0409228v2
quantum computation with unlabeled qubits, J. Phys. A: Math.
Theor. 39 (2006) 8507-8515. arXiv:quant-ph/0601078v3
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:quant-ph/0505026v2
[See also K. J. Guo, Quantum
Walks on Strongly Regular Graphs, Master Dissertation,
University of Waterloo, 2010.]
Severini, On the
structure of the adjacency matrix of the line digraph of a regular
digraph, Discrete Appl. Math. 154 (2006), no 12, 1663-1665.
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), 291-317. arXiv:quant-ph/0406165v2
graph states with maximal Schmidt measure, Physics Letters A,
356 (2006). arXiv:quant-ph/0511147v1
J. Osborne, S. Severini, Quantum
Algorithms and Covering Spaces, Quantum Computers and Computing,
6:1 (2006), 1-22. arXiv:quant-ph/0403127v3
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).
B. Reid, R. Lundgren, S. Severini, D. Stewart, Quadrangularity
and Strong Quadrangularity in Tournaments, Australas. J. Combin.
34 (2006), 247-260. arXiv:math/0409474v1
Bebeacua, T. Mansour, A. Postnikov, S. Severini, On the X-rays of
permutations, ENDM, Vol. 20, 2005. arXiv:math/0506334v1
Clarisse, S. Ghosh, S. Severini, A. Sudbery, Entangling
power of permutations, Phys. Rev. A 72, 012314 (2005).
Gutin, N. Jones, A. Rafiey, S. Severini, A. Yeo, Mediated
Digraphs and Quantum Nonlocality, Discrete Appl. Math. 150
(2005), no. 1-3, 41-50. arXiv:math/0411653v2
the digraph of a unitary matrix, SIAM J. Matrix Anal. Appl.
(SIMAX), 25:1 (2003), 295-300. arXiv:math/0205187v2
Decision Theory Workshop, January 4 – 8 2018, Pecs,
Hungary. (Invited speaker)
6th International Conference on Complex Networks and Their
Applications, November 29 - December 01 2017, Lyon, France. (PC
in Quantum Information Theory, Institut Henri Poincaré,
Paris, France September 4th - December 15th 2017, Main Conference
"Quantum Information Theory", Institut Henri Poincaré,
11-15 December 2017. (Invited speaker)
Physics of Information, KITP, University of California, Santa
Barbara, 20 Nov - 9 Dec. (Invited participant)
program in Quantum
Computing and Quantum Information Processing (QCQIP) at the
Academy of Mathematics and Systems Sciences (AMSS) of the Chinese
Academy of Sciences (CAS), 9 Nov - 19 Nov. (Invited speaker)
Workshop on Quantum Techniques in Machine Learning, QTML 2017,
Verona, Italy, November 6-8, 2017. (Program Committee)
Semantic Information Pursuit for Multimodal Data Analysis, 2017
Kickoff meeting, November 1-2, 2017, Baltimore, MD. (Speaker)
forcing and its applications, Jan 30-Feb 3, 2017, American
Institute of Mathematics, San Jose, CA (Co-organizer with Shaun
Fallat and Michael Young)
Research School Combinatorics and Operators in Quantum Information
Theory, Queen’s University, Belfast, 5-9 September 2016.
(Co-organizer with Ivan Todorov)
Central European Quantum Information Processing Workshop, 16-19
June 2016, Valtice, Czech Republic. (Invited speaker)
Structures in Computation, Simons Institute, Berkeley, CA, Aug
17-Dec 16, 2016. (Long term invited participant)
Summer School on Complex Networks, Bertinoro, Italy, July 11-15
2016. (Invited lecturer)
workshop on Contextuality as a Resource in Quantum Computation,
20-22 June 2016, London, UK. (Co-organizer with Samson Abramsky,
Nadish de Silva, Rui Soares Barbosa)
Century: Leah Clements, 'Beside',
Gallery Tuesday, 8
December 2015. (Invited panellist)
information, Operators, and Graphs Barcelona, 25-27 November
2015. (Organizer with Andreas Winter and Giannicola Scarpa)
on Quantum Correlations, Contextuality and All That... Again,
November 9-13, 2015. (Invited participant)
Workshop on Mathematical and Engineering Methods in Computer Science
(MEMICS), Telč, Czech Republic, October 23-25, 2015. (Invited
Symposium on Complex Systems, Grenoble, 14-17 September 2015.
Colóquio Brasileiro de Matemática, Matemática
da Teoria Quântica, IMPA, Rio de Janeiro, 26-31 July 2015.
Geometry Workshop, QMUL, 16 July 2015, London. (Invited speaker)
Asian Quantum Information Science Conference, August 24-30,
2015, Korea Institute for Advanced Study (KIAS), Seoul, Korea.
(Sub-reviewer; Long contributed talk by Runyao Duan)
10th Conference on the Theory
of Quantum Computation, Communication and Cryptography (TQC15),
Université libre de Bruxelles, 20–22 May 2015.
(Steering committee member)
Central European Quantum Information Processing Workshop (CEQIP15),
18-21 June 2015, Telč, Czech Republic. (PC member)
Science 2015 (CitSci2015), San Jose, California, 11-12 February
2015. (PC member)
on Quantum Metrology, Interaction, and Causal Structure,
Tsinghua University, Beijing, China, 1-5 December 2014. (Invited
research: addressing future challenges and directions, INI,
Cambridge, UK, 18-19 September 2014. (Invited speaker) Video
on Integrability and Exact Solvability as Avatars of Symmetry,
de recherches mathématiques (CRM), Montreal, QC, 25-29 August
2014. (Invited speaker)
Symposium on Complex Systems: Florence, Italy, 15-18 September
2014. (PC member)
School on Complex Systems, Bertinoro, Italy, July 14-18, 2014.
Frontiers of Quantum Information, Ascoli Piceno, Italy, July
7-11, 2014. (Invited speaker)
Combinatorics: Spectral Graph Theory, Erdos-Ko-Rado Theorems and
Quantum Information Theory, A Conference to celebrate the work
of Chris Godsil, Fields Institute, Toronto, ON, June 23-27, 2014.
Central European Quantum Information Processing Workshop,
Znojmo, Czech Republic, 5-8 June 2014. (Invited speaker; PC member)
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 21-23 May 2014. (Steering
Paris (QuPa), Institut H.
Poincare, Paris, France, 27 March 2014. (Invited speaker)
of Communication, Queen's University, Belfast, UK, 7-15 March
2014. (Invited speaker)
London, UK, 20-22 February, 2014. (Invited speaker)
on Quantum Correlations, Contextuality and All That, Natal,
December 9-13, 2013. (Invited speaker)
Quantum Algorithms Meeting, Newton
Institute for Mathematical Science, Cambridge, 27-28 November 2013.
of the talk: Graph
Isomorphism: quantum ideas
Quantum Connection, UCL, 4-5 November, 2013; including Peter
Shor's public lecture. (Co-organizer)
Symposium on Complex Systems, Prague, Czech Republic, 10-13
September 2013. (PC member)
Quantum Matter, Higgs Centre for Theoretical Physics, University
of Edinburgh, 2-3 September 2013. (Invited participant)
Challenges in Quantum Information, Newton Institute for
Mathematical Sciences, Cambridge, August-December 2013 (Visiting
Information and Foundations of Quantum Mechanics, University of
British Columbia, Vancouver, BC, 2-5 July 2013. (Invited speaker)
Conference of the International Linear Algebra Society (ILAS),
Providence, Rhode Island, USA on June 3-7, 2013. Advances in
Combinatorial Matrix Theory and its Applications (Invited speaker)
Workshop on Quantum Computation and Complex Networks, Institute
for Quantum Computing, Waterloo, Ontario, 24-26 May, 2013.
on Theory of Quantum Computation, Communication and Cryptography,
Guelph, Ontario, 21-23 May, 2013. (PC Chair).
The Oxford Future
of Science Conference, Rigour
and Openess in 21st
11-12 April 2013, Oxford. (Invited speaker)
Hackday in London, Centre for Creative Collaboration, 16 March
2013. (Invited speaker)
Frontiers of Science, Kazan, Russia, 11-15 March 2013. (Invited
International Workshop on Adiabatic Quantum Computation,
Institute of Physics, London, UK, 6-8 March 2013. (Co-organizer)
Semidefinite Zero-forcing and Applications, Banff
Mathematical Innovation and Discovery, Banff, Alberta, Canada, 23-30
September, 2012. (Organizer)
Complex Network Analysis, University of Cambridge, 19th
September 2012. (Invited participant)
Africa 2, 3-7 September, KwaZulu-Natal, South Africa.
Workshop on Quantum Computing and Quantum Information Processing,
August 31-September 2, 2012, Beijing, China. (Invited speaker)
Physics of Information, Summer School & Workshop, Shanghai
Jiao-Tong University, 22-28 August 2012. (Lecturer; Program
committee) [27-28, Satellite
workshop of AQIS2012]
[organized by David Cai, Runyao Duan, Andreas Winter, and me]
Shanghai Conference in Algebraic Combinatorics, Shanghai
Jiao-Tong University, 17-22 August 2012. (Contribute speaker)
SIAM Conference on Applied Linear Algebra, June 18th-22nd,
Valencia, Spain. (Invited speaker)
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)
Cambridge Networks Day, The Sainsbury Laboratory, Cambridge, 18
May. (Invited Speaker)
Royal Society International Scientific Centre – Function
Prediction in Complex Networks, 28-29 May 2012. (Invited
Technologies Programme 2012, Cumberland Lodge, Windsor, UK, 2-4
April, 2012. (Speaker)
2012, British Applied Mathematics Colloquium 2012, 27-29 March
2012. Minisymposium “Quantum Information”. (Invited
structures in quantum information theory, Banff
Mathematical Innovation and Discovery, Banff, Alberta, Canada, 26
February -2 March, 2012. (Invited participant)
Symposium on Complex Systems, September 19-25, 2012, Kos Island,
Greece. (Programme committee) Alan
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 4-7, 2012. (Invited speaker)
International Fellowship Day, The Royal Society, 25 October 2011.
(Invited speaker / Q&A panelist)
Town Meeting – Quantum Information and Quantum Technology,
November 9, 2011. (Programme comittee)
Workshop on Algebraic Combinatorics, 15-18 September 2011,
Shanghai Jiao-Tong University. (Invited speaker)
Information Workshop, Benasque, Centro
de Ciencias de Benasque Pedro Pascual, July
Information: Codes, Geometry and Random Structures, Centre de
recherches mathematiques (CRM), Montreal, 24-26/10, 2011. (Invited
in Quantum Information Processing, QIP2011,
10-14 January, 2011, Singapore. Presentation Pdf
Graph Theory Workshop, Banff
Mathematical Innovation and Discovery, Banff, Alberta, Canada, 24-29
April, 2011. (Invited Speaker)
International Academic Conference on Quantum and Molecular
Computing, QMC 2011,
Singapore, 15-16 August 2011. (Technical Committee)
Budapest, August 29-September 2, 2011, Rényi Institute.
Slovenian International Conference on Graph Theory, Bled,
Slovenia, June 19-24, 2011. Mini-symposium: Information Theory of
Graphs (Invited speaker)
Asian-Pacific Conference on Quantum Information Science, in
conjunction with the Festschrift in honour of Vladimir Korepin,
Singapore, 25-28 May 2011. (Programme Committee)
biennial Canadian Discrete and Algorithmic Mathematics Conference
(CanaDAM) May 31-June 3, 2011, University of Victoria, BC, Canada.
Symposium on Complex Systems, 9th International Conference of
Numerical Analysis and Applied Mathematics (ICNAAM), Halkidiki,
Greece, September 19-25, 2011. (Programme Committee)
on Theory of Quantum Computation, Communication and Cryptography,
24-26 May 2011. (Programme Committee)
5th Conference on Theory of Quantum Computation, Communication and
University of Leeds, 13-15 April, 2010. (Co-chair of the Programme
Committee together with Wim van Dam)
3th Conference on Theory of Quantum Computation, Communication and
The University of Tokyo, January 30-1 February, 2008. (Contributed
Program on Quantum Information (IPQI),
Institute of Physics, Bhubaneswar, Orissa, India, Jan 4th-30th,
2010. (Invited lecturer)
Research Group for Mathematics of Quantum Information, Pacific
Institute for Mathematics Sciences (PIMS), Vancouver, BC, 2010-2012.
19th International Linear Algebra Society Conference, ILAS
2010, Pisa, 21-25 June, 2010. Mini-symposium: Linear Algebra and
Quantum Information Processing. (Programme Committee)
Monsters From The Id, The Barbican, London, 26 May 2010. (Q&A
Southeastern Section Meeting, Richmond, VA, November 6-7, 2010.
Session on Minimum Rank Problems. (Invited Speaker)
Workshop, NABA, The New Academy of
Fine Arts, Milan (24 hours workshop), December 2009. (Lecturer with
II: "Quantum and Combinatorics" (Zakopane, Poland,
2009). (Invited speaker)
Quantum Information Science Conference, 2009,
November 2009, Scuola Normale Superiore, Pisa, Italy. (Contributed
Quantum Information Science Conference, 2008,
24-29 October 2008, Palazzo Ducale, Camerino, Italy. (Contributed
Summer Meeting 2009. Memorial University of
Newfoundland, St. John's, Newfoundland,
6 - 8, 2009. (Invited speaker: Scientific Session on Algebraic
Information and Graph Theory: emerging connections, Perimeter
Institute for Theoretical Physics, April
28 - May 2, 2008. (Organizing Committee)
International Meeting of the AMS and Shanghai Math Society,
17-21, 2008, Shanghai,
Peoples Republic of China. (Invited speaker: Special
Session on Combinatorics and Discrete Dynamical Systems)
Gravity, August 25-29, 2008, Massachusetts Institute of
Technology / Center for Theoretical Physics.
International Conference on Combinatorial Physics, 24-27
November, Krakow, Poland. (Invited speaker)
19th International Conference on Formal Power Series and Algebraic
Combinatorics (FPSAC2007), July 2-6, 2007, Nankai University,
Tianjin, China. (Contributed talk)
Centre for Theoretical
Studies, IIT Kharagpur,
11-13, 2007. (Invited speaker)
conference on Quantum Information Science 2005, August 26-30,
2005 - National Museum of Emerging Science and Innovation "Nihon
Kagaku Miraikan", JST, Tokyo, Japan. (Contributed talk)
Workshop on Quantum Information Science, Seoul, 22-24 August
2005. (Invited speaker)
British Combinatorial Conference
of Durham, 11-15 July 2005. (Contributed talk)
Experimental Mathematics Seminar, 16 June, 2005, Rutgers
University, Department of Mathematics and
the Center for Discrete Mathematics and Theoretical Computer Science
speaker; host: Doron
third conference on permutation patterns (PP2005), May 29–June
3, 2005, University of Haifa, Israel. (Invited speaker)
Asia-Pacific Conference on Quantum Information Science, Tainan,
Taiwan, December 10-13, 2004. (Invited speaker)
Haifa Workshop on Interdisciplinary Applications of Graph
theory, Combinatorics, and Algorithms
Michael O. Rabin), May 16-19, 2005, CRI, Haifa, Israel. (Contributed
Third Haifa Workshop on Interdisciplinary Applications of Graph,
Combinatorics, and Algorithms (Honoring Peter Hammer), May
27-29, 2003, 2003, CRI, Haifa, Israel. (Contributed talk)
Prague, Czech Republic, 8-12 September, 2003. (Contributed talk)
and graphs: In 2008, at the Perimeter
Institute for Theoretical Physics, we organized a conference
Information and Graph Theory: emerging connections. Below is an
incomplete list of references on this topic (Oct 2011): Graph
Raussendorf, D.E. Browne, H.J. Briegel, Measurement-based quantum
computation with cluster states, Phys. Rev. A 68, 022312 (2003).
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:quant-ph/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:quant-ph/0411020v2;
Godsil, State Transfer on Graphs, 2011. arXiv:1102.4898v2
[math.CO]. Quantum expanders: A. Ben-Aroya, A. Ta-Shma, Quantum
expanders and the quantum entropy difference problem, 2007.
W. Harrow, R. A. Low, Efficient Quantum Tensor Product Expanders and
k-designs, Proceedings of RANDOM 2009, LNCS, 5687:548-561, 2009.
[quant-ph]. 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. 50-59; A. Ambainis, Quantum
walks and their algorithmic applications, International Journal
of Quantum Information, 1:507-518, 2003. arXiv:quant-ph/0403120v3;
M. Mohseni, P. Rebentrost, S. Lloyd, A. Aspuru-Guzik.
quantum walks in photosynthetic energy transfer, Journal of
Chemical Physics 129, 174106 (2008). arXiv:0805.2741v2
[quant-ph]; A. M. Childs, Universal
computation by quantum walk, Phys. Rev. Lett. 102, 180501
Kottos and U. Smilansky, Quantum
Chaos on Graphs, Phys. Rev. Lett. 79, 4794-797, (1997); U.
Smilansky, Quantum chaos on discrete graphs, 2007. arXiv:0704.3525v1
of unitary matrices: L.
minimum semidefinite rank of a triangle-free graph, Linear
Algebra and its Applications 434
(2011), 1945-1955; T. J. Osborne, Approximate Locality for Quantum
Systems on Graphs, Phys. Rev. Lett. 101, 140503 (2008).
Jozsa, On the simulation of quantum circuits, 2006.
I. L. Markov, Y. Shi, Simulating quantum computation by contracting
tensor networks, SIAM Journal on Computing, 38(3):963-981, 2008.
D. Aharonov, Z. Landau, J. Makowsky, The quantum FFT can be
classically simulated, 2006, arXiv:quant-ph/0611156v2.
(via encoding): K.
Audenaert, C. D. Godsil, G. F. Royle, T.
Symmetric squares of graphs, J. Comb. Theory, Ser. B 97(1): 74-90
[math.CO]; J. K. Gamble, M. Friesen, D. Zhou, R. Joynt, S. N.
Coppersmith, Two-particle quantum walks applied to the graph
Phys. Rev. A, 81(5):052313, 2010. arXiv:1002.3003v1
[quant-ph]. 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.
Leung, J. Oppenheim, and A.Winter. Quantum network communication —
the butterfly and beyond. IEEE Transactions on Information Theory,
56(7):3478–3490, 2010. arXiv:quant-ph/0608223v5.
Perseguers, M. Lewenstein, A. Acín, J. I. Cirac,
complex networks, Nature Physics 6, 539 - 543 (2010).
as channels; T. S. Cubitt, D. Leung, W. Matthews, A. Winter,
Improving zero-error classical communication with entanglement,
Phys. Rev. Lett., 104(23):230503, 2010. arXiv:0911.5300v2
Leung, L. Mancinska, W. Matthews, M. Ozols, A. Roy,
can increase asymptotic rates of zero-error classical communication
over classical channels, 2010. arXiv:1009.1195v2
colouring: C. Godsil, M. W. Newman, Coloring an Orthogonality Graph,
SIAM J. Discrete Math. 22(2): 683-692 (2008). arXiv:math/0509151v1
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 time-dependent
Hamma, F. Markopoulou, Background independent condensed matter
models for quantum gravity, New J. Phys. 13:095006, 2011.
Caravelli, F. Markopoulou, Properties of quantum graphity at low
temperature, Phys. Rev. D 84 024002, 2011. arXiv:1008.1340v3
the nature of quantum geometry, in Magic
ed. J. Klauder, Freeman, San Francisco, 1972, pp. 333-354. N.
Linial, Z. Luria, An
upper bound on the number of high dimensional permutations,
[math.CO] A. Ashikhmin, A. Robert Calderbank, W. Kewlin,
Second Order Reed-Muller Codes as Grassmannian Packings, ISIT
2006, Seattle, USA, July 9 14, 2006. P. Diaconis and J. Salzman,
pursuit for discrete data. IMS Collections Probability and
Statistics: Essays in Honor of David A. Freedman, Vol. 2 (2008)
[math.ST]. B. J. Frey and D. Dueck, Clustering
by Passing Messages Between Data Points, Science
315, 972–976, February 2007. citeseerx.
Jakobson, S. D.Miller, I. Rivin, Z. Rudnick,
spacings for regular graphs, IMA vol. 109 (Emerging applications of
number theory, Minneapolis, MN 1996). arXiv:hep-th/0310002v1.
S. M. Pincus, Approximate
entropy as a measure of system complexity,
PNAS March 15, 1991 vol. 88 no. 6 2297-2301. (See our work
R. Kleinberg, and A. Lehman, On
the capacity of information networks,
Transactions on Information Theory, 52(6):2345–2364, 2006. N.
Goldenfeld, L. P. Kadanoff, Simple
lessons from complexity,
2 April 1999: Vol. 284 no. 5411 pp. 87-89. G.
Tkacik and A M. Walczak, Information transmission in gene regulatory
networks: a review, J. Phys.: Condens. Matter 23 (2011) 153102
change point estimation, The Annals of Statistics, Vol. 16, No.
1. (1988), pp. 188-197. S.
Janson, D. E. Knuth, T. Łuczak, B. Pittel, The
birth of the giant component, Random Structures Algorithms 4 (1993),
no. 3, 231-358. arXiv:math/9310236v1
[math.PR]. D. Deutsch, Physics,
Philosophy and Quantum Technology
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), 86-94. M. M. Wilde, From Classical to Quantum Shannon
Theory, 2011. arXiv:1106.1445v2
[quant-ph] 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 481-502. arXiv:0705.0467v2
Expert, T. Evans, V. D. Blondel, R. Lambiotte, Beyond Space For
Spatial Networks, PNAS 2011 108 (19) 7663-7668. 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,
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, 135-156. arXiv:math/9508209v3
[math.MG]. P. Bourgade, J. P. Keating, Quantum
chaos, random matrix theory, and the Riemann zeta-function,
Seminaire Poincare, XIV (2010) 115-153. And the seminal paper:
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, Springer-Verlag, New
York, 1986, pp. 1-17. C. W. J. Granger, Investigating causal
relations by econometric models and cross-spectral methods,
(1969), 424–438. Y.-A. Kim, S. Wuchty, T. M. Przytycka,
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.
the controllability of nearest neighbor interconnections,
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,
Mathematical Incompleteness in Peano Arithmetic. In Handbook for
Mathematical Logic (Ed. J. Barwise).
Netherlands: North-Holland, 1977. M. Warmuth, A
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 22nd
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):667-689,
P. Murphy, An
introduction to graphical models, 2001. J.
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
a free software package for creating and manipulating undirected and
directed graphs. Cytoscape
is an open source software platform for visualizing complex
a free software for finding and visualizing overlapping dense groups
of nodes in networks, based on the Clique Percolation Method (CPM)
et. al., Nature
Severini, Mathoverflow: Rewiring
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
Data. E. D. Kolaczyk, (2009), Statistical Analysis of Network
Data: Methods and Models. Springer, New York. Kappalanguage:
A rule-based 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
A. Khot, Nisheeth K. Vishnoi, The
Unique Games Conjecture, Integrality Gap for Cut
Problems and Embeddability of Negative Type Metrics into l_1,
Kavruk, V. I. Paulsen, I. G. Todorov, M. Tomforde, Tensor
products of operator systems.
Berry and J.P. Keating The
Riemann zeros and eigenvalue asymptotics, SIAM Review, 41, No. 2
(1999), 236-266. A.
Ferrante, M. Pavon, Matrix
completion à la Dempster by the principle of parsimony, IEEE
Trans. Inform. Theory
6, 3925-3931. Information
System on Graph Classes and their Inclusions. Yvo
Desmedt, Yongge Wang, Perfectly Secure Message Transmission
Revisited, IEEE Trans. Inform. Theory 54 (2008), 25820-2595.
[cs.CR]. Asu Ozdaglar:
and dynamics on networks, Acemoglu,
Daron, Munther Dahleh, Ilan Lobel, and Asuman Ozdaglar (2008),
learning in social networks, LIDS Working Paper 2780,
Massachusetts nstitute of Technology. M.
/ Postulatory Quantum Mechanics, in Fundamental Physics in
and Devices (Stanford University, 2008). R.
Theory, Electronic Edition 2010. Measuring
Worth, historical data on important economic aggregates, with
particular emphasis on nominal measures. Hà Quang Minh,
Kernel Hilbert Spaces and Learning Problems on the Hypercube ,
preprint, 2012. Network
Workbench: A Large-Scale Network Analysis, Modeling and
Visualization Toolkit for Biomedical, Social Science and Physics
Research. Gephi The Open Graph Viz
complexity (by S. Lloyd): 1.
How hard is it to describe?
Complexity or Algorithmic Information Content; Minimum Description
Length; Fisher Information; Renyi Entropy; Code Length (prefix-free,
Huffman, Shannon-Fano, error-correcting, Hamming); Chernoff
Information; Dimension; Fractal Dimension; Lempel-Ziv Complexity. 2.
How hard is it to create? Time
Computational Complexity; Space
Computational Complexity; Information-Based 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 epsilon-machine 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,
Tomography: Recent Developments, Statistical Science, Vol. 19,
No. 3, 499–517, 2004. GraphCrunch2
is a software tool for network analysis, modelling and alignment. L.
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), 67-128. A. Clauset, C.
R. Shalizi, M. E. J. Newman, Power
law distribution of empirical data, SIAM Review 51, 661-703
(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 high-throughput
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,
open-source, graph-mining system with massive scalability. NetLogo
is a multi-agent programmable modeling environment. Massey Tutorial
on Zero-error Information Theory, Information Theory Winter
School, La Colle Sur Loup, March 2007. D. Zelazo and M. Mesbahi,
methods for networked dynamic systems: Heterogeneity and H2
in Efficient Modeling and Control of Large-Scale Systems (J.
Mohammadpour and K.M. Grigoriadis, eds.), New York, New York:
Springer, pp. 219-249. B.
Convergence of Bird Flocking, arXiv:0905.4241v1
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 (4-6), 97-217 (2007). L.
Vinet, A. Zhedanov, Dual -1 Hahn polynomials and perfect state
[math-ph]. 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 end-user tools designed to
allow researchers to investigate evolutionary aspects of dynamical
complex networks. P. Malacaria, F. Smeraldi, The
Thermodynamics of Confidentiality, CSF 2012: 280-290, 2011. D.
Aharonov, A. Ta-Shma, Adiabatic Quantum State Generation and
Statistical Zero Knowledge, arXiv:quant-ph/0301023v2.
B. Sinaimeri, Structures
of Diversity, PhD Thesis, Sapienza University, Roma, 2009. B. D.
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 Statistical-Mechanical Informatics 2008 (IW-SMI 2008). L. H.
2002. L. G. Valiant, Evolvability, ECCC TR06-120.
A beautiful bibliography on the Physics
of Algorithms (Los Alamos National Laboratory). Y. Colin de
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
[cond-mat.stat-mech]. M. Laurent, Semidefinite
Optimization (great lectures). Some of my favourite conjectures:
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
C. Colburn, The
combinatorics of network reliability, Oxford Univ. Press, 1987.
is good. A good lecture on the Ising
(Frank Krauss). S.
Kauffman, L. Smolin, Combinatorial dynamics in quantum gravity.
Feynman's lectures (on enhanced video player platform). Cook D.
J. and Holder L. B., Mining Graph Data, John Wiley & Sons, 2007.
Capacities, 1993. J. P. Keating and N. C. Snaith (2003), Random
matrices and L-functions, J. Phys. A 36, pp. 2859-2881. 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 125-133. 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
143–148. (Landau's Theorem is beautiful). The
Symbols List (useful). British
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),
Litow, N. Deo, Graph compression and the zeros of polynomials.
Inform. Process. Lett. 92 (2004), no. 1, 39–44. P.
M. B. Vitanyi, Compression-based
M. B. Vitanyi, Meaningful
[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
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:gr-qc/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. 1-4, vii–viii. 68-06. F. J. Brandenburg, K.
Skodinis, Finite graph automata for linear and boundary graph
languages. Theoret. Comput. Sci. 332 (2005), no. 1-3, 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,
(This contains the same graphs of A.
Ashikhmin, A. Robert Calderbank, W. Kewlin, Multidimensional
Second Order Reed-Muller 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,
like the problem of finding the length of the minimal
N. Johnston, Non-uniqueness of minimal superpermutations. Discrete
Math. 313 (2013), no. 14, 1553–1557. arXiv:1303.4150
projects 2013-14 (COMP3091, COMPM091): 1) A
new measure of complexity for graphs:
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:
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. Time-series
of matrices: G. Zumbach, The empirical properties of large
covariance matrices. arXiv:0903.1525
[q-fin.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 Kochen-Specker 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.
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
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:quant-ph/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
“Cellular Algebras and Graph Invariants Based on Quantum
Walks” that kills the problem in the general case. Lovasz
Conjecture: Every finite connected vertex-transitive
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
Rat, What's new
(the Prince of mathematical blogs), The
polymath blog, Shtetl-Optimized.
of Leonardo da Vinci. Open problem: Minimizing
the gate length in a logic circuit (5/2/14). G. Grimmett, The
Random-Cluster Model, 2003. arXiv:math/0205237v2
[math.PR]. O. Weiss, M. A. Jimenez-Montano. H.
P. Herzel, Information
Content of Protein Sequences,
J. Theor. Biol. (2000) 206, 379—386.
Apostolico and Z. Galil, editors, Pattern
Oxford University Press, New York, 1997, 377 pages. M. Crochemore,
C. Hancart et T. Lecroq, Algorithmique
Vuibert, Paris, 2001, 347 pages. M. Crochemore and W. Rytter, Text
Oxford University Press, New York, 1994, 412 pages. D. Gusfield,
on Strings, Trees, and Sequences,
Cambridge University Press, New York, 1997, 534 pages. W. F. Smyth,
Patterns in Strings,
Addison-Wesley, 2002. G.A. Stephen, String
World Scientific Publishing Co., 1994, 243 pages. J. Spencer, Nine
Lectures on Random Graphs. D. Sculley and Carla E. Brodley,
and Machine Learning: A New Perspective on Feature Space Vectors.
journals like Nature,
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.”
Mohammad Bavarian, Peter W. Shor, Information Causality,
Szemerédi-Trotter and Algebraic Variants of CHSH,
[quant-ph]. 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
full-text indexes. D. Kovach, The computational theory of
intelligence, Dec 2014. arXiv:1412.7978
[cs.AI] (interesting philosophical perspective). M. Laurent,
and semidefinite programming, Lecture notes, 2013. A. Bookatz,
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,
complexity: learning resources. Tim
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,
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 NP-completeness; Freeman,
1979. Hopcroft, Ullman and Motwani,
Introduction to Automata Theory, Languages, and Computation (second
edition), Addison-Wesley, 2001 website.
Papadimitriou, Elements of the theory of computation
(Prentice-Hall 1982, with Harry Lewis, second edition September
1997). Lance Fortnow's Computational
Complexity Web Log. Chee
K. Yap: Introduction to Complexity Classes. Antonina
Xu, Stanisław Radziszowski, Bounds
on Shannon capacity and Ramsey numbers for products of graphs,
IEEE Transactions on Information Theory, 59(8) (2013) 4767-4770. A.
Vesel, J. Zerovnik, Improved
lower bounds on the Shannon capacity of C_7,
Processing Letters, Volume 81, Issue 5, 16 March 2002, Pages
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:
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,
Vera T.; Szegedy,
Katalin Graph limits and parameter testing. STOC'06:
Proceedings of the 38th Annual ACM Symposium on Theory of Computing,
New York, 2006.
Svante Threshold graph limits and random threshold graphs.
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.
Oliver Monotone graph limits and quasimonotone graphs. Internet
3, 187–231. Janson,
Svante Quasi-random graphs and graph limits. European
J. Combin. 32
7, 1054–1083. A talk
at IAS by Lovász. Ramsey
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), 311-314. hog.grinvin.org.
references: A. M. Childs, D. Gosset, Z. Webb, The
Bose-Hubbard model is QMA-complete, 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 Weisfeiler-Lehman refinements,
Journal of Combinatorial Theory, Series B 100 (2010), 671-682.
on combinatorial games in finite model theory by Phokion Kolaitis.
P. Wocjan, S. Zhang, Several natural BQP-complete problems,
[It shows that QWGT is BQP-complete]. E.
Knill and R. Laflamme,”Quantum
Computing and Quadratically Signed Weight Enumerators”,
Information Processing Letters 79 (4) pp. 173-1 79, 2001 [It
introduces the QWGT – also it contains a beautiful link
between probabilistic and quantum computation. M. Muzychuk and I.
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 spin-glass partition function]
M. Grohe, The
quest for a logic capturing PTIME, 2008. [Fixed points logic
with non-deterministic 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 EF-games to prove
inexpressibility results]. This is an interesting logic:
Y.-K. Liu, M. Christandl, F. Verstraete, N-representability
is QMA-complete, Phys. Rev. Lett. 98, 110503 (2007) [an
interesting QMA-complete problem]. M. Grohe, Equivalence
in finite-variable logics is complete for polynomial time,
Combinatorica 19:507-532, 1999. [great result about P-completeness
of testing equivalence]. N.
Immerman, E. Lander, Describing
graphs: A first-order approach to graph canonization, In
Complexity Theory Retrospective, pages 59--81. Springer-Verlag,
1990. [fundamental result about C_k]. M.
Grohe, M. Otto, Pebble games and linear equations, arXiv:1204.1990
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
Dawar lecture notes and more
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 k-locality, 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,
Combinatorics in Mathematical Chemistry. Methods and Algorithms. II.
Program Implementation of the Weisfeiler-Leman Algorithm, 1997.
A. Dawar, On
tractable approximations of graph isomorphism, 2014. M. Furer,
Renement Requires at Least a Linear Number of Iterations, ICALP
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. 1-3, 117–126.
Three problems: color refinement; coarsest equitable partition;
floyd algorithm for collisions; VC dimension; graceful labelings;
Ulam's reconctruction conjecture:
k-e.c. property: Bonato's
(nice). Xiao-Dong Zhang, A
survey of laplacian eigenvalues. Crossing
numbers of the complete graph: history. Richter-Salazar,
numbers (2008). Parking
functions, by Richard Stanley. Tree
bijections, by Igor Pak. SVM,
by Tristan Fletcher. Spectacular notes on “Quantum Proofs”
by Vidick and Watrous: https://arxiv.org/pdf/1610.01664v1.pdf.
Entanglement and non-locality course by Vern Paulsen:
(very useful to learn about games/graphs/non-locality). Good review
on the Clique
Problems. 2016: T. Gartner, A
survey of kernels for structured data. R. Hamming, You
and your research. Two beautiful paper: . R. Caianiello,
Combinatorics and renormalization in quantum field theory, Frontiers
in Physics, W. A. Benjamin, Inc., Reading-London-Amsterdam, 1973. L.
Faddeev, Yu. Reshetikhin, Tacktajan, Quantization of Lie groups and
Lie algebras, Algebraic analysis, Vol. I, pp. 129–139,
Academic Press, Boston, MA, 1988. X.-D. Zhang, The
Laplacian eigenvalues of graphs: a survey, 2011. S. Bravyi, D.
classical simulation of quantum circuits dominated by Clifford
gates, 2016. M. Y. Vardi, Database
Queries – Logic and Complexity. B. Rosgen, Hard
quantum problems. Very nice review: Quantum
(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, Proceedings of the National
Academy of Science India Section A: Physical Sciences, Modern
Physics Letters B. 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). 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, Nature Physics, Complex Adaptive
Systems Modeling, Entropy, Networks, Scientific Reports,
Mathematical Programming (Series A), Natural Computing,
Nonlinearity, PLoS ONE.
and sub-reviewer (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
(CDC), ACM Symposium on Theory of Computing (STOC).
(grant applications): Engineering and Physical Research Council
(EPSRC), the Royal Society, US National Security Agency (NSA) –
American Mathematical Society (AMS) Grants Scheme, European
Commission –Directorate General for Communications Networks,
Content and Technology Future & Emerging Technologies, the
Research Council of Norway, National Natural Science Foundation of
China, the Austrian Science Fund, Netherlands Organisation for
Scientific Research, Mathematics of Information Technology and
Complex Systems (MITACS), Member
of the Computer Science Evaluation Group at the Natural Sciences and
Engineering Research Council of Canada (NSERC), 2015-2017.
work: Associate editor: Philosophical Transactions of the Royal
Society A: Mathematical, Physical and Engineering Sciences (The
Royal Society). Associate editor: Journal of Complex Networks
(Oxford University Press). Associate editor: International Journal
of Computer Mathematics (Taylor & Francis). Editorial advisor:
Special Matrices (Versita / De Gruyter). Review editor: Frontiers in
Interdisciplinary Physics (Frontiers Media S. A.). Guest editor:
Springer Lecture Notes in Computer Science (1 proceedings), with W.
van Dam and V. Kendon.
editor: World Scientific (1 multiauthor book), with L.-C. Kwek and
H.-B. Su. Guest editor: LIPIcs – Leibniz International
Proceedings in Informatics (1 proceeding), with F. Brandao. Guest
editor: International Journal of Modern Physics B (1 issue), with
L.-C. Kwek and H.-B. Su. Guest editor: Journal of Algebraic
Combinatorics (1 issue), with A. Munemasa and A. Jurisic.
Computer Science Evaluation Group at the Natural Sciences and
Engineering Research Council of Canada (NSERC), 2014-2017. (The
evaluation group meets every year for the Competition
Week in Ottawa, Ontario.)
The Royal Society International Exchanges Committee, January 2014 –
researchers: Alberto Ottolenghi, Postdoctoral Research Fellow,
September 2016-present. David Roberson, Postdoctoral Research
Associate, December 2015-present. Will Matthews, Postdoctoral
Research Associate, March 2016-October 2016 (then at Arm). Nadish de
Silva, Postdoctoral Research Associate, May 2015-present. Fabiano
Andrade, Postdoctoral Research Fellow, Department of Computer
Science, UCL, January 2015-July 2016. Nairi Usher, Research
Assistant, March 2016-May 2016. Tianyu Ye, Academic Visitor, College
of Information & Electronic Engineering, Zhejiang Gongshang
University, February 2014-August 2015. Banghai Wang, Academic
Visitor from Guangdong University of Technology, April 2013-March
2014; June 2014-August 2014. Walter Vinci, Postdoctoral Research
Associate, Department of Computer Science and London Centre for
Nanotechnology, UCL, October 2012-June 2014 (then at University of
Southern California). Zhihao Ma, Academic Visitor from Shanghai Jiao
Tong University, October 2011-October 2012.
(ongoing): Daniel Temko, 2014- (CoMPLEX; Secondary advisor: Trevor
Graham; Awarded a Bogue Research Fellowship, 2015, Franziska
Michor's Lab, Harvard Medical School). Octavio Zapata, 2014-
(Supported by CONACYT). Josh Lockhart, 2015- (Quantum CDT, supported
by Lockheed-Martin; Secondary advisor: Aram Harrow, MIT). Danial
Dervovic, 2016- (Quantum CDT; Seconday advisor: John Shawe-Taylor).
Andrea Rocchetto, 2016- (University of Oxford, supported by QinetiQ,
Primary advisor: Simon Benjamin), Marcello Benedetti, 2016-
(supported by CQC).
Leonard Wossnig, 2017-. Edward Grant, 2017-.
students (completed): Chris Banerji, Department of Computer Science
and UCL Cancer Institute. Secondary advisor: Andrew Teschendorff
(PICB-Shanghai/UCL). October 2012-July 2015. Recipient of the
INBIOMEDvision Training Challenge Prize 2012. James West, Department
of Computer Science and UCL Cancer Institute. First advisor: Andrew
Teschendorff. Thesis: Network physics in cancer and ageing. Andrea
Casaccino, PhD in Information Engineering, University of Siena /
MIT. First advisor: Enrico Martinelli. Thesis: Quantum computation
and communication with qubit systems.
(2015-16): Artur Guerard (Physics & Astronomy), Yu-Ching Chang
(CSML, intern at HarperCollins), Josh Lockart (Quantum CDT), Thomas
Galley (Quantum CDT), Kyohei Koyama, Zhiguan Mu, Tianyu Cui (CSML,
interns at Invenia Labs), Ermira Zhuka (BUSICS, intern at CQC),
Kostantinos Metallinos (CSML, intern at CQC).
MRes projects (<2015): Lourdes Sriraja (final), Janos Hodsagi
(Secondary advisor: Peter Csermely, Semmelweis University), Chris
Banerji (final; Awarded the UCL Faculty of Mathematical and Physical
Sciences Postgraduate Prize for outstanding achievements), Bobby
Bentham (C3), Thomas Wyatt (CP3), Tim Lucas (CP2), Sophie Atkinson
(CP2), James West (final).
Vacation Bursaries: Markos Karasamanis (then PhD student at ETH).
Foundation Undergraduate Research Bursary Students: Abdul Bhutto,
Zahra Najib, Soomin Kim, Emma Rahman.
students: Hairu Xu, Guangdong University of Technology, February
2014-April 2014. Nadish de Silva, University of Oxford, October
Alessandro Cosentino, MSc in Computer Science, University of Pisa
(First advisor: Anna Bernasconi. Thesis:
On some combinatorial properties of graph states. Then PhD student
at the Institute for Quantum Computing, University of Waterloo).
Tommaso Gagliardoni, MSc in Mathematics, University of Perugia
(First advisor: Marco Baioletti. Thesis: Classical simulation of
quantum circuits. Then PhD student at the Centre for Advanced
Security Research Darmstadt).
PHASGQ03 Quantum Communication and Computation for Quantum
Technologies (Strand 2: Quantum Computation and Algorithms), 2015
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.
1 (24/02/15; Week 27). Recap and warm-up:
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), No-cloning
theorem, diagrams and circuits, partial measurements, Hamiltonian
dynamics. Exercise: SWAP test. [Exercise: Entanglement in a Bell
(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,
Solovay-Kitaev's theorem, function evaluation, parallelism, the
notion of query complexity, Deutsch's algorithm, Deutsch-Jozsa's
algorithm, Exercise: measuring interference.
(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.
(05/03/15; Week 28). Shor's factoring algorithm:
factoring, reduction to period finding, Shor's method for period
finding, continued fractions and post-processing, Group-theoretic
setting for the Fourier transform (representations, abelian vs.
nonabelian case). Exercise: Factoring.
(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.
(12/03/15; Week 29). Quantum
complexity theory: P,
NP, P-complete, PSPACE, NP-completeness, 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
(17/03/15; Week 30). Hamiltonian
complexity [Guest lecturer: Toby
computation aims to engineer complex many-body systems to process
information in ways that would not be possible classically.
Many-body physics aims to understand the complex behaviour of
naturally-occurring many-body systems. In a sense, they are two
sides of the same coin. We will investigate the computational
complexity of quantum many-body systems, culminating in Kitaev's
seminal proof of QMA-hardness of the ground state problem for local
(18/03/15; Week 30). Grover's search: Unstructured
database search, Grover's algorithm, Grover's iterate, Geometric
argument, Search via continuous walks.
(20/03/15; Week 30). Adiabatic
computation [Guest lecturer: Andrew
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, many-body
localization, out-of-equilibrium 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.
J. Watrous, CPSC
519/619, University of Waterloo: Quantum
Ph219/CS219, Caltech, Quantum Computation, 2013-14. Chapter
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).
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).
references of 2015. Mostly similar to the 2015 lectures. Ashley
Montanaro as a guest lecturer.
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), No-cloning theorem, diagrams and
circuits, partial measurements, Hamiltonian dynamics. Exercises
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, Solovay-Kitaev's theorem, function
evaluation in a quantum computer, parallelism, the notion of query
complexity, Deutsch's algorithm, Deutsch-Jozsa's algorithm, Exercise:
measuring interference. (Interference as an ingredient for quantum
speed-up: the power of negative numbers in probability densities.)
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 post-processing, Group-theoretic setting for
the Fourier transform (representations, abelian vs. nonabelian case).
Graph isomorphism as an HSP. Grover's
database search, Grover's algorithm, Grover's iterate, Geometric
argument, Search via continuous walks. Optimality. Walks:
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
by Andrew Childs. Quantum
complexity theory [Guest lecturer: Ashley
NP, P-complete, PSPACE, NP-completeness, 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
complexity [Guest lecturer: Toby
computation aims to engineer complex many-body systems to process
information in ways that would not be possible classically. Many-body
physics aims to understand the complex behaviour of
naturally-occurring many-body systems. In a sense, they are two sides
of the same coin. We will investigate the computational complexity of
quantum many-body systems, culminating in Kitaev's seminal proof of
QMA-hardness of the ground state problem for local Hamiltonians.
purpose computation with neural networks, Optimal
simulation of automata by neural nets, Efficient
Sampling for Bipartite Matching Problems, Invariant
scattering convolutional networks, Mathematical
Foundations of Supervised Learning, Differential
Privacy: a short tutorial, Tighter
PAC-Bayes bounds through distribution-dependent priors. Provable
Bounds for Learning Some Deep Representations, Going
deeper with convolutions, Pac-Bayesian Supervised Classification:
The Thermodynamics of Statistical Learning