|
Continuous-time Quantum Walk
A continuous-time quantum walk (CTQW) is a quantum walk on a given (simple) graph that is dictated by a time-varying unitary matrix that relies on the Hamiltonian of the quantum system and the adjacency matrix. The concept of a CTQW is believed to have been first considered for quantum computation by Edward Farhi and Sam Gutmann; since many classical algorithms are based on (classical) random walks, the concept of CTQWs were originally considered to see if there could be quantum analogues of these algorithms with e.g. better time-complexity than their classical counterparts. In recent times, problems such as deciding what graphs admit properties such as perfect state transfer with respect to their CTQWs have been of particular interest. Definitions Suppose that G is a graph on n vertices, and that t \in \mathbb. Continuous-time quantum walks The continuous-time quantum walk U(t) \in \operatorname_(\mathbb) on G at time t is defined as:U(t) := e^letting A denote the adjacency m ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
 |
Quantum Walk
Quantum walks are quantum analogues of classical random walks. In contrast to the classical random walk, where the walker occupies definite states and the randomness arises due to stochastic transitions between states, in quantum walks randomness arises through: (1) quantum superposition of states, (2) non-random, reversible unitary evolution and (3) collapse of the wave function due to state measurements. As with classical random walks, quantum walks admit formulations in both discrete time and continuous time. Motivation Quantum walks are motivated by the widespread use of classical random walks in the design of randomized algorithms, and are part of several quantum algorithms. For some oracular problems, quantum walks provide an exponential speedup over any classical algorithm. Quantum walks also give polynomial speedups over classical algorithms for many practical problems, such as the element distinctness problem, the triangle finding problem, and evaluating NAND trees. ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
 |
Disjoint Union Of Graphs
In graph theory, a branch of mathematics, the disjoint union of graphs is an operation that combines two or more graphs to form a larger graph. It is analogous to the disjoint union of sets, and is constructed by making the vertex set of the result be the disjoint union of the vertex sets of the given graphs, and by making the edge set of the result be the disjoint union of the edge sets of the given graphs. Any disjoint union of two or more nonempty graphs is necessarily disconnected. Notation The disjoint union is also called the graph sum, and may be represented either by a plus sign or a circled plus sign: If G and H are two graphs, then G+H or G\oplus H denotes their disjoint union. Related graph classes Certain special classes of graphs may be represented using disjoint union operations. In particular: *The forests are the disjoint unions of trees. *The cluster graphs are the disjoint unions of complete graphs. *The 2-regular graphs are the disjoint unions of cycle gra ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
 |
Distance-regular Graph
In the mathematical field of graph theory, a distance-regular graph is a regular graph such that for any two vertices and , the number of vertices at distance from and at distance from depends only upon , , and the distance between and . Every distance-transitive graph is distance-regular. Indeed, distance-regular graphs were introduced as a combinatorial generalization of distance-transitive graphs, having the numerical regularity properties of the latter without necessarily having a large automorphism group. Intersection arrays It turns out that a graph G of diameter d is distance-regular if and only if there is an array of integers \ such that for all 1 \leq j \leq d , b_j gives the number of neighbours of u at distance j+1 from v and c_j gives the number of neighbours of u at distance j - 1 from v for any pair of vertices u and v at distance j on G . The array of integers characterizing a distance-regular graph is known as its intersection array. Co ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
 |
Cubic Graph
In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs. A bicubic graph is a cubic bipartite graph. Symmetry In 1932, Ronald M. Foster began collecting examples of cubic symmetric graphs, forming the start of the Foster census.. Many well-known individual graphs are cubic and symmetric, including the utility graph, the Petersen graph, the Heawood graph, the Möbius–Kantor graph, the Pappus graph, the Desargues graph, the Nauru graph, the Coxeter graph, the Tutte–Coxeter graph, the Dyck graph, the Foster graph and the Biggs–Smith graph. W. T. Tutte classified the symmetric cubic graphs by the smallest integer number ''s'' such that each two oriented paths of length ''s'' can be mapped to each other by exactly one symmetry of the graph. He showed that ''s'' is at most 5, and provided examples of graphs with ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
 |
Graph Complement
In the mathematical field of graph theory, the complement or inverse of a graph is a graph on the same vertices such that two distinct vertices of are adjacent if and only if they are not adjacent in . That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and removes all the edges that were previously there.. The complement is not the set complement of the graph; only the edges are complemented. Definition Let be a simple graph and let consist of all 2-element subsets of . Then is the complement of , where is the relative complement of in . For directed graphs, the complement can be defined in the same way, as a directed graph on the same vertex set, using the set of all 2-element ordered pairs of in place of the set in the formula above. In terms of the adjacency matrix ''A'' of the graph, if ''Q'' is the adjacency matrix of the complete graph of the same number of vertices (i.e. all entries are unity e ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
Strongly Regular Graph
In graph theory, a strongly regular graph (SRG) is defined as follows. Let be a regular graph with vertices and degree . is said to be strongly regular if there are also integers and such that: * Every two adjacent vertices have common neighbours. * Every two non-adjacent vertices have common neighbours. The complement of an is also strongly regular. It is a . A strongly regular graph is a distance-regular graph with diameter 2 whenever μ is non-zero. It is a locally linear graph whenever . Etymology A strongly regular graph is denoted an srg(''v'', ''k'', λ, μ) in the literature. By convention, graphs which satisfy the definition trivially are excluded from detailed studies and lists of strongly regular graphs. These include the disjoint union of one or more equal-sized complete graphs, and their complements, the complete multipartite graphs with equal-sized independent sets. Andries Brouwer and Hendrik van Maldeghem (see #References) use an alternate ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
|
Edge-transitive Graph
In the mathematical field of graph theory, an edge-transitive graph is a graph such that, given any two edges and of , there is an automorphism of that maps to . In other words, a graph is edge-transitive if its automorphism group acts transitively on its edges. Examples and properties The number of connected simple edge-transitive graphs on n vertices is 1, 1, 2, 3, 4, 6, 5, 8, 9, 13, 7, 19, 10, 16, 25, 26, 12, 28 ... Edge-transitive graphs include all symmetric graph, such as the vertices and edges of the cube. Symmetric graphs are also vertex-transitive (if they are connected), but in general edge-transitive graphs need not be vertex-transitive. Every connected edge-transitive graph that is not vertex-transitive must be bipartite, (and hence can be colored with only two colors), and either semi-symmetric or biregular.. Examples of edge but not vertex transitive graphs include the complete bipartite graphs K_ where m ≠ n, which includes the star graphs K_. ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
|
Perfect Matching
In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactly one edge in . A perfect matching is also called a 1-factor; see Graph factorization for an explanation of this term. In some literature, the term complete matching is used. Every perfect matching is a maximum-cardinality matching, but the opposite is not true. For example, consider the following graphs: : In graph (b) there is a perfect matching (of size 3) since all 6 vertices are matched; in graphs (a) and (c) there is a maximum-cardinality matching (of size 2) which is not perfect, since some vertices are unmatched. A perfect matching is also a minimum-size edge cover. If there is a perfect matching, then both the matching number and the edge cover number equal . A perfect matching can only occur when the graph has an even n ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
|
Association Scheme
The theory of association schemes arose in statistics, in the theory of experimental design for the analysis of variance. In mathematics, association schemes belong to both algebra and combinatorics. In algebraic combinatorics, association schemes provide a unified approach to many topics, for example combinatorial designs and coding theory. In algebra, association schemes generalize groups, and the theory of association schemes generalizes the character theory of linear representations of groups. Definition An ''n''-class association scheme consists of a set ''X'' together with a partition ''S'' of ''X'' × ''X'' into ''n'' + 1 binary relations, ''R''0, ''R''1, ..., ''R''''n'' which satisfy: *R_ = \ and is called the identity relation. *Defining R^* := \, if ''R'' in ''S'', then ''R*'' in ''S'' *If (x,y) \in R_, the number of z \in X such that (x,z) \in R_ and (z,y) \in R_ is a constant p^k_ depending on i, j, k but not on the particular choice of x and y. ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
 |
Vertex-transitive Graph
In the mathematical field of graph theory, a vertex-transitive graph is a graph in which, given any two vertices and of , there is some automorphism :f : G \to G\ such that :f(v_1) = v_2.\ In other words, a graph is vertex-transitive if its automorphism group acts transitively on its vertices.. A graph is vertex-transitive if and only if its graph complement is, since the group actions are identical. Every symmetric graph without isolated vertices is vertex-transitive, and every vertex-transitive graph is regular. However, not all vertex-transitive graphs are symmetric (for example, the edges of the truncated tetrahedron), and not all regular graphs are vertex-transitive (for example, the Frucht graph and Tietze's graph). Finite examples Finite vertex-transitive graphs include the symmetric graphs (such as the Petersen graph, the Heawood graph and the vertices and edges of the Platonic solids). The finite Cayley graphs (such as cube-connected cycles) a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
Coherent Algebra
A coherent algebra is an algebra of complex square matrices that is closed under ordinary matrix multiplication, Schur product, transposition, and contains both the identity matrix I and the all-ones matrix J. Definitions A subspace \mathcal of \mathrm_(\mathbb) is said to be a coherent algebra of order n if: * I, J \in \mathcal. * M^ \in \mathcal for all M \in \mathcal. * MN \in \mathcal and M \circ N \in \mathcal for all M, N \in \mathcal. A coherent algebra \mathcal is said to be: * ''Homogeneous'' if every matrix in \mathcal has a constant diagonal. * ''Commutative'' if \mathcal is commutative with respect to ordinary matrix multiplication. * ''Symmetric'' if every matrix in \mathcal is symmetric. The set \Gamma(\mathcal) of ''Schur-primitive matrices'' in a coherent algebra \mathcal is defined as \Gamma(\mathcal) := \ . Dually, the set \Lambda(\mathcal) of ''primitive matrices'' in a coherent algebra \mathcal is defined as \Lambda(\mathcal) := \ . Examples * The c ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
|
Walk-regular Graph
In discrete mathematics, a walk-regular graph is a simple graph where the number of closed walks of any length from a vertex to itself does not depend on the choice of vertex. Equivalent definitions Suppose that G is a simple graph. Let A denote the adjacency matrix of G, V(G) denote the set of vertices of G, and \Phi_(x) denote the characteristic polynomial of the vertex-deleted subgraph G - v for all v \in V(G).Then the following are equivalent: * G is walk-regular. * A^k is a constant-diagonal matrix for all k \geq 0. * \Phi_(x) = \Phi_(x) for all u, v \in V(G). Examples * The vertex-transitive graphs are walk-regular. * The semi-symmetric graphs are walk-regular. * The distance-regular graphs are walk-regular. More generally, any simple graph in a homogeneous coherent algebra is walk-regular. * A connected regular graph is walk-regular if: ** It has at most four distinct eigenvalues. ** It is triangle-free and has at most five distinct eigenvalues. ** It is bipartite a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |