An official website of the United States government
Abstract We introduce and examine three subclasses of the family of quantum no-signalling (QNS) correlations introduced by Duan and Winter: quantum commuting, quantum and local. We formalise the notion of a universal TRO of a block operator isometry, define an operator system, universal for stochastic operator matrices, and realise it as a quotient of a matrix algebra. We describe the classes of QNS correlations in terms of states on the tensor products of two copies of the universal operator system and specialise the correlation classes and their representations to classical-to-quantum correlations. We study various quantum versions of synchronous no-signalling correlations and show that they possess invariance properties for suitable sets of states. We introduce quantum non-local games as a generalisation of non-local games. We define the operation of quantum game composition and show that the perfect strategies belonging to a certain class are closed under channel composition. We specialise to the case of graph colourings, where we exhibit quantum versions of the orthogonal rank of a graph as the optimal output dimension for which perfect classical-to-quantum strategies of the graph colouring game exist, as well as to non-commutative graph homomorphisms, where we identify quantum versions of non-commutative graph homomorphisms introduced by Stahlke.
more »
« less
Perfect matchings and derangements on graphs
Abstract We show that each perfect matching in a bipartite graph intersects at least half of the perfect matchings in . This result has equivalent formulations in terms of the permanent of the adjacency matrix of a graph, and in terms of derangements and permutations on graphs. We give several related results and open questions.
more »
« less
- Award ID(s):
- 1802787
- PAR ID:
- 10257535
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Journal of Graph Theory
- Volume:
- 97
- Issue:
- 2
- ISSN:
- 0364-9024
- Page Range / eLocation ID:
- p. 340-354
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Trapped-ion quantum simulators have demonstrated a long history of studying the physics of interacting spin-lattice systems using globally addressed entangling operations. Yet despite the multitude of studies so far, most have been limited to studying variants of the same spin interaction model, namely an Ising model with power-law decay in the couplings. Here, we demonstrate that much broader classes of effective spin–spin interactions are achievable using exclusively global driving fields. Specifically, we find that these new categories of interaction graphs become achievable with perfect or near-perfect theoretical fidelity by tailoring the coupling of the driving fields to each vibrational mode of the ion crystal. Given the relation between the ion crystal vibrational modes and the accessible interaction graphs, we show how the accessible interaction graph set can be further expanded by shaping the trapping potential to include specific anharmonic terms. Finally, we derive a rigorous test to determine whether a desired interaction graph is accessible using only globally driven fields. These tools broaden the reach of trapped-ion quantum simulators so that they may more easily address open questions in materials science and quantum chemistry.more » « less
-
Abstract A graph isstrongly perfectif every induced subgraph of it has a stable set that meets every maximal clique of . A graph isclaw‐freeif no vertex has three pairwise nonadjacent neighbors. The characterization of claw‐free graphs that are strongly perfect by a set of forbidden induced subgraphs was conjectured by Ravindra in 1990 and was proved by Wang in 2006. Here we give a shorter proof of this characterization.more » « less
-
null (Ed.)Abstract A perfect K r -tiling in a graph G is a collection of vertex-disjoint copies of the clique K r in G covering every vertex of G . The famous Hajnal–Szemerédi theorem determines the minimum degree threshold for forcing a perfect K r -tiling in a graph G . The notion of discrepancy appears in many branches of mathematics. In the graph setting, one assigns the edges of a graph G labels from {‒1, 1}, and one seeks substructures F of G that have ‘high’ discrepancy ( i.e. the sum of the labels of the edges in F is far from 0). In this paper we determine the minimum degree threshold for a graph to contain a perfect K r -tiling of high discrepancy.more » « less
-
Abstract MotivationThe size of a genome graph—the space required to store the nodes, node labels and edges—affects the efficiency of operations performed on it. For example, the time complexity to align a sequence to a graph without a graph index depends on the total number of characters in the node labels and the number of edges in the graph. This raises the need for approaches to construct space-efficient genome graphs. ResultsWe point out similarities in the string encoding mechanisms of genome graphs and the external pointer macro (EPM) compression model. We present a pair of linear-time algorithms that transform between genome graphs and EPM-compressed forms. The algorithms result in an upper bound on the size of the genome graph constructed in terms of an optimal EPM compression. To further reduce the size of the genome graph, we propose the source assignment problem that optimizes over the equivalent choices during compression and introduce an ILP formulation that solves that problem optimally. As a proof-of-concept, we introduce RLZ-Graph, a genome graph constructed based on the relative Lempel–Ziv algorithm. Using RLZ-Graph, across all human chromosomes, we are able to reduce the disk space to store a genome graph on average by 40.7% compared to colored compacted de Bruijn graphs constructed by Bifrost under the default settings. The RLZ-Graph scales well in terms of running time and graph sizes with an increasing number of human genome sequences compared to Bifrost and variation graphs produced by VGtoolkit. AvailabilityThe RLZ-Graph software is available at: https://github.com/Kingsford-Group/rlzgraph. Supplementary informationSupplementary data are available at Bioinformatics online.more » « less
