Graph-theoretic approach to quantum correlations.

Science.gov (United States)

Cabello, Adán; Severini, Simone; Winter, Andreas

2014-01-31

Correlations in Bell and noncontextuality inequalities can be expressed as a positive linear combination of probabilities of events. Exclusive events can be represented as adjacent vertices of a graph, so correlations can be associated to a subgraph. We show that the maximum value of the correlations for classical, quantum, and more general theories is the independence number, the Lovász number, and the fractional packing number of this subgraph, respectively. We also show that, for any graph, there is always a correlation experiment such that the set of quantum probabilities is exactly the Grötschel-Lovász-Schrijver theta body. This identifies these combinatorial notions as fundamental physical objects and provides a method for singling out experiments with quantum correlations on demand.

Invariant subsets under compact quantum group actions

OpenAIRE

Huang, Huichi

2012-01-01

We investigate compact quantum group actions on unital $C^*$-algebras by analyzing invariant subsets and invariant states. In particular, we come up with the concept of compact quantum group orbits and use it to show that countable compact metrizable spaces with infinitely many points are not quantum homogeneous spaces.

Entanglement in coined quantum walks on regular graphs

International Nuclear Information System (INIS)

Carneiro, Ivens; Loo, Meng; Xu, Xibai; Girerd, Mathieu; Kendon, Viv; Knight, Peter L

2005-01-01

Quantum walks, both discrete (coined) and continuous time, form the basis of several recent quantum algorithms. Here we use numerical simulations to study the properties of discrete, coined quantum walks. We investigate the variation in the entanglement between the coin and the position of the particle by calculating the entropy of the reduced density matrix of the coin. We consider both dynamical evolution and asymptotic limits for coins of dimensions from two to eight on regular graphs. For low coin dimensions, quantum walks which spread faster (as measured by the mean square deviation of their distribution from uniform) also exhibit faster convergence towards the asymptotic value of the entanglement between the coin and particle's position. For high-dimensional coins, the DFT coin operator is more efficient at spreading than the Grover coin. We study the entanglement of the coin on regular finite graphs such as cycles, and also show that on complete bipartite graphs, a quantum walk with a Grover coin is always periodic with period four. We generalize the 'glued trees' graph used by Childs et al (2003 Proc. STOC, pp 59-68) to higher branching rate (fan out) and verify that the scaling with branching rate and with tree depth is polynomial

Central limit theorems for large graphs: Method of quantum decomposition

International Nuclear Information System (INIS)

Hashimoto, Yukihiro; Hora, Akihito; Obata, Nobuaki

2003-01-01

A new method is proposed for investigating spectral distribution of the combinatorial Laplacian (adjacency matrix) of a large regular graph on the basis of quantum decomposition and quantum central limit theorem. General results are proved for Cayley graphs of discrete groups and for distance-regular graphs. The Coxeter groups and the Johnson graphs are discussed in detail by way of illustration. In particular, the limit distributions obtained from the Johnson graphs are characterized by the Meixner polynomials which form a one-parameter deformation of the Laguerre polynomials

Network-based Arbitrated Quantum Signature Scheme with Graph State

Science.gov (United States)

Ma, Hongling; Li, Fei; Mao, Ningyi; Wang, Yijun; Guo, Ying

2017-08-01

Implementing an arbitrated quantum signature(QAS) through complex networks is an interesting cryptography technology in the literature. In this paper, we propose an arbitrated quantum signature for the multi-user-involved networks, whose topological structures are established by the encoded graph state. The determinative transmission of the shared keys, is enabled by the appropriate stabilizers performed on the graph state. The implementation of this scheme depends on the deterministic distribution of the multi-user-shared graph state on which the encoded message can be processed in signing and verifying phases. There are four parties involved, the signatory Alice, the verifier Bob, the arbitrator Trent and Dealer who assists the legal participants in the signature generation and verification. The security is guaranteed by the entanglement of the encoded graph state which is cooperatively prepared by legal participants in complex quantum networks.

Jointly-check iterative decoding algorithm for quantum sparse graph codes

International Nuclear Information System (INIS)

Jun-Hu, Shao; Bao-Ming, Bai; Wei, Lin; Lin, Zhou

2010-01-01

For quantum sparse graph codes with stabilizer formalism, the unavoidable girth-four cycles in their Tanner graphs greatly degrade the iterative decoding performance with a standard belief-propagation (BP) algorithm. In this paper, we present a jointly-check iterative algorithm suitable for decoding quantum sparse graph codes efficiently. Numerical simulations show that this modified method outperforms the standard BP algorithm with an obvious performance improvement. (general)

Adiabatic graph-state quantum computation

International Nuclear Information System (INIS)

Antonio, B; Anders, J; Markham, D

2014-01-01

Measurement-based quantum computation (MBQC) and holonomic quantum computation (HQC) are two very different computational methods. The computation in MBQC is driven by adaptive measurements executed in a particular order on a large entangled state. In contrast in HQC the system starts in the ground subspace of a Hamiltonian which is slowly changed such that a transformation occurs within the subspace. Following the approach of Bacon and Flammia, we show that any MBQC on a graph state with generalized flow (gflow) can be converted into an adiabatically driven holonomic computation, which we call adiabatic graph-state quantum computation (AGQC). We then investigate how properties of AGQC relate to the properties of MBQC, such as computational depth. We identify a trade-off that can be made between the number of adiabatic steps in AGQC and the norm of H-dot as well as the degree of H, in analogy to the trade-off between the number of measurements and classical post-processing seen in MBQC. Finally the effects of performing AGQC with orderings that differ from standard MBQC are investigated. (paper)

Quantum dressing orbits on compact groups

Energy Technology Data Exchange (ETDEWEB)

Jurco, B. (Technische Univ. Clausthal, Clausthal-Zellerfeld (Germany). Sommerfeld Inst.); Stovicek, P. (Prague Univ. (Czechoslovakia). Dept. of Mathematics)

1993-02-01

The quantum double is shown to imply the dressing transformation on quantum compact groups and the quantum Iwasawa decomposition in the general case. Quantum dressing orbits are describing explicitly as *-algebras. The dual coalgebras consisting of differential operators are related to the quantum Weyl elements. Besides, the differential geometry on a quantum leaf allows a remarkably simple construction of irreducible *-representations of the algebras of quantum functions. Representation spaces then consist of analytic functions on classical phase spaces. These representations are also interpreted in the framework of quantization in the spirit of Berezin applied to symplectic leaves on classical compact groups. Convenient 'coherent states' are introduced and a correspondence between classical and quantum observables is given. (orig.).

Quantum dressing orbits on compact groups

International Nuclear Information System (INIS)

Jurco, B.; Stovicek, P.

1993-01-01

The quantum double is shown to imply the dressing transformation on quantum compact groups and the quantum Iwasawa decomposition in the general case. Quantum dressing orbits are describing explicitly as *-algebras. The dual coalgebras consisting of differential operators are related to the quantum Weyl elements. Besides, the differential geometry on a quantum leaf allows a remarkably simple construction of irreducible *-representations of the algebras of quantum functions. Representation spaces then consist of analytic functions on classical phase spaces. These representations are also interpreted in the framework of quantization in the spirit of Berezin applied to symplectic leaves on classical compact groups. Convenient 'coherent states' are introduced and a correspondence between classical and quantum observables is given. (orig.)

Spectral analysis of growing graphs a quantum probability point of view

CERN Document Server

Obata, Nobuaki

2017-01-01

This book is designed as a concise introduction to the recent achievements on spectral analysis of graphs or networks from the point of view of quantum (or non-commutative) probability theory. The main topics are spectral distributions of the adjacency matrices of finite or infinite graphs and their limit distributions for growing graphs. The main vehicle is quantum probability, an algebraic extension of the traditional probability theory, which provides a new framework for the analysis of adjacency matrices revealing their non-commutative nature. For example, the method of quantum decomposition makes it possible to study spectral distributions by means of interacting Fock spaces or equivalently by orthogonal polynomials. Various concepts of independence in quantum probability and corresponding central limit theorems are used for the asymptotic study of spectral distributions for product graphs. This book is written for researchers, teachers, and students interested in graph spectra, their (asymptotic) spectr...

Isometric coactions of compact quantum groups on compact ...

Indian Academy of Sciences (India)

a compact quantum metric space in the framework of Rieffel, where the ... This problem can be formulated and studied in various settings. ... The spaces we are interested in this paper are metric spaces, both classical and quantum. ... He has given a definition for a quantum symmetry of a classical ...... by the construction of I.

Coherent states for quantum compact groups

CERN Document Server

Jurco, B

1996-01-01

Coherent states are introduced and their properties are discussed for all simple quantum compact groups. The multiplicative form of the canonical element for the quantum double is used to introduce the holomorphic coordinates on a general quantum dressing orbit and interpret the coherent state as a holomorphic function on this orbit with values in the carrier Hilbert space of an irreducible representation of the corresponding quantized enveloping algebra. Using Gauss decomposition, the commutation relations for the holomorphic coordinates on the dressing orbit are derived explicitly and given in a compact R--matrix formulation (generalizing this way the q--deformed Grassmann and flag manifolds). The antiholomorphic realization of the irreducible representations of a compact quantum group (the analogue of the Borel--Weil construction) are described using the concept of coherent state. The relation between representation theory and non--commutative differential geometry is suggested.}

Relating zeta functions of discrete and quantum graphs

Science.gov (United States)

Harrison, Jonathan; Weyand, Tracy

2018-02-01

We write the spectral zeta function of the Laplace operator on an equilateral metric graph in terms of the spectral zeta function of the normalized Laplace operator on the corresponding discrete graph. To do this, we apply a relation between the spectrum of the Laplacian on a discrete graph and that of the Laplacian on an equilateral metric graph. As a by-product, we determine how the multiplicity of eigenvalues of the quantum graph, that are also in the spectrum of the graph with Dirichlet conditions at the vertices, depends on the graph geometry. Finally we apply the result to calculate the vacuum energy and spectral determinant of a complete bipartite graph and compare our results with those for a star graph, a graph in which all vertices are connected to a central vertex by a single edge.

Coherent states for quantum compact groups

International Nuclear Information System (INIS)

Jurco, B.; Stovicek, P.; CTU, Prague

1996-01-01

Coherent states are introduced and their properties are discussed for simple quantum compact groups A l , B l , C l and D l . The multiplicative form of the canonical element for the quantum double is used to introduce the holomorphic coordinates on a general quantum dressing orbit. The coherent state is interpreted as a holomorphic function on this orbit with values in the carrier Hilbert space of an irreducible representation of the corresponding quantized enveloping algebra. Using Gauss decomposition, the commutation relations for the holomorphic coordinates on the dressing orbit are derived explicitly and given in a compact R-matrix formulation (generalizing this way the q-deformed Grassmann and flag manifolds). The antiholomorphic realization of the irreducible representations of a compact quantum group (the analogue of the Borel-Weil construction) is described using the concept of coherent state. The relation between representation theory and non-commutative differential geometry is suggested. (orig.)

Bipartite separability and nonlocal quantum operations on graphs

Science.gov (United States)

Dutta, Supriyo; Adhikari, Bibhas; Banerjee, Subhashish; Srikanth, R.

2016-07-01

In this paper we consider the separability problem for bipartite quantum states arising from graphs. Earlier it was proved that the degree criterion is the graph-theoretic counterpart of the familiar positive partial transpose criterion for separability, although there are entangled states with positive partial transpose for which the degree criterion fails. Here we introduce the concept of partially symmetric graphs and degree symmetric graphs by using the well-known concept of partial transposition of a graph and degree criteria, respectively. Thus, we provide classes of bipartite separable states of dimension m ×n arising from partially symmetric graphs. We identify partially asymmetric graphs that lack the property of partial symmetry. We develop a combinatorial procedure to create a partially asymmetric graph from a given partially symmetric graph. We show that this combinatorial operation can act as an entanglement generator for mixed states arising from partially symmetric graphs.

Coherent states for quantum compact groups

Energy Technology Data Exchange (ETDEWEB)

Jurco, B. [European Organization for Nuclear Research, Geneva (Switzerland). Theory Div.; Stovicek, P. [Ceske Vysoke Uceni Technicke, Prague (Czech Republic). Dept. of Mathematics]|[CTU, Prague (Czech Republic). Doppler Inst.

1996-12-01

Coherent states are introduced and their properties are discussed for simple quantum compact groups A{sub l}, B{sub l}, C{sub l} and D{sub l}. The multiplicative form of the canonical element for the quantum double is used to introduce the holomorphic coordinates on a general quantum dressing orbit. The coherent state is interpreted as a holomorphic function on this orbit with values in the carrier Hilbert space of an irreducible representation of the corresponding quantized enveloping algebra. Using Gauss decomposition, the commutation relations for the holomorphic coordinates on the dressing orbit are derived explicitly and given in a compact R-matrix formulation (generalizing this way the q-deformed Grassmann and flag manifolds). The antiholomorphic realization of the irreducible representations of a compact quantum group (the analogue of the Borel-Weil construction) is described using the concept of coherent state. The relation between representation theory and non-commutative differential geometry is suggested. (orig.)

A simple method for finding the scattering coefficients of quantum graphs

International Nuclear Information System (INIS)

Cottrell, Seth S.

2015-01-01

Quantum walks are roughly analogous to classical random walks, and similar to classical walks they have been used to find new (quantum) algorithms. When studying the behavior of large graphs or combinations of graphs, it is useful to find the response of a subgraph to signals of different frequencies. In doing so, we can replace an entire subgraph with a single vertex with variable scattering coefficients. In this paper, a simple technique for quickly finding the scattering coefficients of any discrete-time quantum graph will be presented. These scattering coefficients can be expressed entirely in terms of the characteristic polynomial of the graph’s time step operator. This is a marked improvement over previous techniques which have traditionally required finding eigenstates for a given eigenvalue, which is far more computationally costly. With the scattering coefficients we can easily derive the “impulse response” which is the key to predicting the response of a graph to any signal. This gives us a powerful set of tools for rapidly understanding the behavior of graphs or for reducing a large graph into its constituent subgraphs regardless of how they are connected

Quantum graphs with the Bethe-Sommerfeld property

Czech Academy of Sciences Publication Activity Database

Exner, Pavel; Turek, Ondřej

2017-01-01

Roč. 8, č. 3 (2017), s. 305-309 ISSN 2220-8054 R&D Projects: GA ČR GA17-01706S Institutional support: RVO:61389005 Keywords : periodic quantum graphs * gap number * delta-coupling * rectangular lattice graph * scale-invariant coupling * Bethe-Sommerfeld conjecture * golden mean Subject RIV: BE - Theoretical Physics OBOR OECD: Atomic, molecular and chemical physics ( physics of atoms and molecules including collision, interaction with radiation, magnetic resonances, Mössbauer effect)

Continuous-Time Classical and Quantum Random Walk on Direct Product of Cayley Graphs

International Nuclear Information System (INIS)

Salimi, S.; Jafarizadeh, M. A.

2009-01-01

In this paper we define direct product of graphs and give a recipe for obtaining probability of observing particle on vertices in the continuous-time classical and quantum random walk. In the recipe, the probability of observing particle on direct product of graph is obtained by multiplication of probability on the corresponding to sub-graphs, where this method is useful to determining probability of walk on complicated graphs. Using this method, we calculate the probability of continuous-time classical and quantum random walks on many of finite direct product Cayley graphs (complete cycle, complete K n , charter and n-cube). Also, we inquire that the classical state the stationary uniform distribution is reached as t → ∞ but for quantum state is not always satisfied. (general)

Non-Weyl asymptotics for quantum graphs with general coupling conditions

International Nuclear Information System (INIS)

Davies, E Brian; Exner, Pavel; Lipovsky, JirI

2010-01-01

Inspired by a recent result of Davies and Pushnitski, we study resonance asymptotics of quantum graphs with general coupling conditions at the vertices. We derive a criterion for the asymptotics to be of a non-Weyl character. We show that for balanced vertices with permutation-invariant couplings the asymptotics is non-Weyl only in the case of Kirchhoff or anti-Kirchhoff conditions. While for graphs without permutation symmetry numerous examples of non-Weyl behaviour can be constructed. Furthermore, we present an insight into what makes the Kirchhoff/anti-Kirchhoff coupling particular from the resonance point of view. Finally, we demonstrate a generalization to quantum graphs with unequal edge weights.

Solving Problem of Graph Isomorphism by Membrane-Quantum Hybrid Model

Directory of Open Access Journals (Sweden)

Artiom Alhazov

2015-10-01

Full Text Available This work presents the application of new parallelization methods based on membrane-quantum hybrid computing to graph isomorphism problem solving. Applied membrane-quantum hybrid computational model was developed by authors. Massive parallelism of unconventional computing is used to implement classic brute force algorithm efficiently. This approach does not suppose any restrictions of considered graphs types. The estimated performance of the model is less then quadratic that makes a very good result for the problem of \\textbf{NP} complexity.

Information Graph Flow: A Geometric Approximation of Quantum and Statistical Systems

Science.gov (United States)

Vanchurin, Vitaly

2018-05-01

Given a quantum (or statistical) system with a very large number of degrees of freedom and a preferred tensor product factorization of the Hilbert space (or of a space of distributions) we describe how it can be approximated with a very low-dimensional field theory with geometric degrees of freedom. The geometric approximation procedure consists of three steps. The first step is to construct weighted graphs (we call information graphs) with vertices representing subsystems (e.g., qubits or random variables) and edges representing mutual information (or the flow of information) between subsystems. The second step is to deform the adjacency matrices of the information graphs to that of a (locally) low-dimensional lattice using the graph flow equations introduced in the paper. (Note that the graph flow produces very sparse adjacency matrices and thus might also be used, for example, in machine learning or network science where the task of graph sparsification is of a central importance.) The third step is to define an emergent metric and to derive an effective description of the metric and possibly other degrees of freedom. To illustrate the procedure we analyze (numerically and analytically) two information graph flows with geometric attractors (towards locally one- and two-dimensional lattices) and metric perturbations obeying a geometric flow equation. Our analysis also suggests a possible approach to (a non-perturbative) quantum gravity in which the geometry (a secondary object) emerges directly from a quantum state (a primary object) due to the flow of the information graphs.

Direct computation of scattering matrices for general quantum graphs

International Nuclear Information System (INIS)

Caudrelier, V.; Ragoucy, E.

2010-01-01

We present a direct and simple method for the computation of the total scattering matrix of an arbitrary finite noncompact connected quantum graph given its metric structure and local scattering data at each vertex. The method is inspired by the formalism of Reflection-Transmission algebras and quantum field theory on graphs though the results hold independently of this formalism. It yields a simple and direct algebraic derivation of the formula for the total scattering and has a number of advantages compared to existing recursive methods. The case of loops (or tadpoles) is easily incorporated in our method. This provides an extension of recent similar results obtained in a completely different way in the context of abstract graph theory. It also allows us to discuss briefly the inverse scattering problem in the presence of loops using an explicit example to show that the solution is not unique in general. On top of being conceptually very easy, the computational advantage of the method is illustrated on two examples of 'three-dimensional' graphs (tetrahedron and cube) for which other methods are rather heavy or even impractical.

Compact representations for the design of quantum logic

CERN Document Server

Niemann, Philipp

2017-01-01

This book discusses modern approaches and challenges of computer-aided design (CAD) of quantum circuits with a view to providing compact representations of quantum functionality. Focusing on the issue of quantum functionality, it presents Quantum Multiple-Valued Decision Diagrams (QMDDs – a means of compactly and efficiently representing and manipulating quantum logic. For future quantum computers, going well beyond the size of present-day prototypes, the manual design of quantum circuits that realize a given (quantum) functionality on these devices is no longer an option. In order to keep up with the technological advances, methods need to be provided which, similar to the design and synthesis of conventional circuits, automatically generate a circuit description of the desired functionality. To this end, an efficient representation of the desired quantum functionality is of the essence. While straightforward representations are restricted due to their (exponentially) large matrix descriptions and other de...

Long range order and giant components of quantum random graphs

CERN Document Server

Ioffe, D

2006-01-01

Mean field quantum random graphs give a natural generalization of classical Erd\\H{o}s-R\\'{e}nyi percolation model on complete graph $G_N$ with $p =\\beta /N$. Quantum case incorporates an additional parameter $\\lambda\\geq 0$, and the short-long range order transition should be studied in the $(\\beta ,\\lambda)$-quarter plane. In this work we explicitly compute the corresponding critical curve $\\gamma_c$, and derive results on two-point functions and sizes of connected components in both short and long range order regions. In this way the classical case corresponds to the limiting point $(\\beta_c ,0) = (1,0)$ on $\\gamma_c$.

Fundamental group of dual graphs and applications to quantum space time

International Nuclear Information System (INIS)

Nada, S.I.; Hamouda, E.H.

2009-01-01

Let G be a connected planar graph with n vertices and m edges. It is known that the fundamental group of G has 1 -(n - m) generators. In this paper, we show that if G is a self-dual graph, then its fundamental group has (n - 1) generators. We indicate that these results are relevant to quantum space time.

Quantum entanglement in non-local games, graph parameters and zero-error information theory

NARCIS (Netherlands)

Scarpa, G.

2013-01-01

We study quantum entanglement and some of its applications in graph theory and zero-error information theory. In Chapter 1 we introduce entanglement and other fundamental concepts of quantum theory. In Chapter 2 we address the question of how much quantum correlations generated by entanglement can

Theoretical issues in quantum computing: Graph isomorphism, PageRank, and Hamiltonian determination

Science.gov (United States)

Rudinger, Kenneth Michael

This thesis explores several theoretical questions pertaining to quantum computing. First we examine several questions regarding multi-particle quantum random walk-based algorithms for the graph isomorphism problem. We find that there exists a non-trivial difference between continuous-time walks of one and two non-interacting particles as compared to non-interacting walks of three or more particles, in that the latter are able to distinguish many strongly regular graphs (SRGs), a class of graphs with many graph pairs that are difficult to distinguish. We demonstrate analytically where this distinguishing power comes from, and we show numerically that three-particle and four-particle non-interacting continuous-time walks can distinguish many pairs of strongly regular graphs. We additionally show that this distinguishing power, while it grows with particle number, is bounded, so that no continuous-time non-interacting walk of fixed particle number can distinguish all strongly regular graphs. We then investigate the relationship between continuous-time and discrete-time walks, in the context of the graph isomorphism problem. While it has been previously demonstrated numerically that discrete-time walks of non-interacting particles can distinguish some SRGs, we demonstrate where this distinguishing power comes from. We also show that while no continuous-time non-interacting walk of fixed particle number can distinguish SRGs, it remains a possibility that such a discrete-time walk could, leaving open the possibility of a non-trivial difference between discrete-time and continuous-time walks. The last piece of our work on graph isomorphism examines limitations on certain kinds of continuous-time walk-based algorithms for distinguishing graphs. We show that a very general class of continuous-time walk algorithms, with a broad class of allowable interactions, cannot distinguish all graphs. We next consider a previously-proposed quantum adiabatic algorithm for computing the

Introduction to compact (matrix) quantum groups and Banica ...

Indian Academy of Sciences (India)

Moritz Weber

2017-11-27

Nov 27, 2017 ... Building on this, we define Banica–Speicher quantum .... four vertices) are ... A compact Hausdorff space X gives rise to a commutative unitalC .... (a) Recall the construction of the group C ..... Having formulated the features of the Haar integration in 'quantum terms', ...... paper: When is the map in [30, Prop.

Quantum star-graph analogues of PT-symmetric square wells

Czech Academy of Sciences Publication Activity Database

Znojil, Miloslav

2012-01-01

Roč. 90, č. 12 (2012), s. 1287-1293 ISSN 0008-4204 R&D Projects: GA ČR GAP203/11/1433 Institutional support: RVO:61389005 Keywords : non-Hermitian interactions * exactly solvable models * quantum graphs * equilateral q-pointed star * Robin boundary condition Subject RIV: BE - Theoretical Physics Impact factor: 0.902, year: 2012

Resonances from perturbations of quantum graphs with rationally related edges

Czech Academy of Sciences Publication Activity Database

Exner, Pavel; Lipovský, Jiří

2010-01-01

Roč. 43, č. 10 (2010), 105301/1-105301/21 ISSN 1751-8113 R&D Projects: GA MŠk LC06002 Institutional research plan: CEZ:AV0Z10480505 Keywords : quantum graphs * resonances * analyze Subject RIV: BE - Theoretical Physics Impact factor: 1.641, year: 2010

The Effect of Quantum Fluctuations in Compact Star Observables

Science.gov (United States)

Pósfay, P.; Barnaföldi, G. G.; Jakovác, A.

2018-05-01

Astrophysical measurements regarding compact stars are just ahead of a big evolution jump, since the NICER experiment deployed on ISS on 2017 June 14. This will provide soon data that would enable the determination of compact star radius with less than 10% error. This can be further constrained by the new observation of gravitational waves originated from merging neutron stars, GW170817. This poses new challenges to nuclear models aiming to explain the structure of super dense nuclear matter found in neutron stars. Detailed studies of the QCD phase diagram show the importance of bosonic quantum fluctuations in the cold dense matter equation of state. Here we used a demonstrative model with one bosonic and one fermionic degree of freedom coupled by Yukawa coupling, we show the effect of bosonic quantum fluctuations on compact star observables such as mass, radius, and compactness. We have also calculated the difference in the value of compressibility which is caused by quantum fluctuations. The above-mentioned quantities are calculated in the mean field, one-loop, and in high order many loop approximation. The results show that the magnitude of these effects is in the range of 4-5%, which place it into the region where modern measurements may detect it. This forms a base for further investigations that how these results carry over to more complicated models.

Searching via walking: How to find a marked clique of a complete graph using quantum walks

International Nuclear Information System (INIS)

Hillery, Mark; Reitzner, Daniel; Buzek, Vladimir

2010-01-01

We show how a quantum walk can be used to find a marked edge or a marked complete subgraph of a complete graph. We employ a version of a quantum walk, the scattering walk, which lends itself to experimental implementation. The edges are marked by adding elements to them that impart a specific phase shift to the particle as it enters or leaves the edge. If the complete graph has N vertices and the subgraph has K vertices, the particle becomes localized on the subgraph in O(N/K) steps. This leads to a quantum search that is quadratically faster than a corresponding classical search. We show how to implement the quantum walk using a quantum circuit and a quantum oracle, which allows us to specify the resources needed for a quantitative comparison of the efficiency of classical and quantum searches--the number of oracle calls.

On the discrete spectrum of the Dirac operator on bent chain quantum graph

Directory of Open Access Journals (Sweden)

Belov Michail

2017-01-01

Full Text Available We study Dirac operators on an infinite quantum graph of a bent chain form which consists of identical rings connected at the touching points by δ-couplings with a parameter α ∈ ℝ. We are interested in the discrete spectrum of the corresponding Hamiltonian. It can be non-empty due to a local (geometrical perturbation of the corresponding infinite chain of rings. The quantum graph of analogous geometry with the Schrodinger operator on the edges was considered by Duclos, Exner and Turek in 2008. They showed that the absence of δ-couplings at vertices (i.e. the Kirchhoff condition at the vertices lead to the absence of eigenvalues. We consider the relativistic particle (the Dirac operator instead of the Schrodinger one but the result is analogous. Quantum graphs of such type are suitable for description of grapheme-based nanostructures. It is established that the negativity of α is the necessary and sufficient condition for the existence of eigenvalues of the Dirac operator (i.e. the discrete spectrum of the Hamiltonian in this case is not empty. The continuous spectrum of the Hamiltonian for bent chain graph coincides with that for the corresponding straight infinite chain. Conditions for appearance of more than one eigenvalue are obtained. It is related to the bending angle. The investigation is based on the transfer-matrix approach. It allows one to reduce the problem to an algebraic task. δ-couplings was introduced by the operator extensions theory method.

Quantum graphs with vertices of a preferred orientation

Czech Academy of Sciences Publication Activity Database

Exner, Pavel; Tater, Miloš

2018-01-01

Roč. 382, č. 5 (2018), s. 283-287 ISSN 0375-9601 R&D Projects: GA ČR GA17-01706S Institutional support: RVO:61389005 Keywords : Quantum graph * Vertex coupling * Preferred orientation * Square lattice * Hexagonal lattice * Band spectrum Subject RIV: BE - Theoretical Physics OBOR OECD: Atomic, molecular and chemical physics ( physics of atoms and molecules including collision, interaction with radiation, magnetic resonances, Mössbauer effect) Impact factor: 1.772, year: 2016

Periodic quantum graphs from the Bethe-Sommerfeld perspective

Czech Academy of Sciences Publication Activity Database

Exner, Pavel; Turek, Ondřej

2017-01-01

Roč. 50, č. 45 (2017), č. článku 455201. ISSN 1751-8113 R&D Projects: GA ČR GA17-01706S Institutional support: RVO:61389005 Keywords : quantum graphs * Bethe-Sommerfeld conjecture * vertex coupling * Diophantine approximation * periodic structure Subject RIV: BE - Theoretical Physics OBOR OECD: Atomic, molecular and chemical physics ( physics of atoms and molecules including collision, interaction with radiation, magnetic resonances, Mössbauer effect) Impact factor: 1.857, year: 2016

Nodal domains on isospectral quantum graphs: the resolution of isospectrality?

International Nuclear Information System (INIS)

Band, Ram; Shapira, Talia; Smilansky, Uzy

2006-01-01

We present and discuss isospectral quantum graphs which are not isometric. These graphs are the analogues of the isospectral domains in R 2 which were introduced recently in Gordon et al (1992 Bull. Am. Math. Soc. 27 134-8), Chapman (1995 Am. Math. Mon. 102 124), Buser et al (1994 Int. Math. Res. Not. 9 391-400), Okada and Shudo (2001 J. Phys. A: Math. Gen. 34 5911-22), Jakobson et al (2006 J. Comput. Appl. Math. 194 141-55) and Levitin et al (2006 J. Phys. A: Math. Gen. 39 2073-82)) all based on Sunada's construction of isospectral domains (Sunada T 1985 Ann. Math. 121 196-86). After presenting some of the properties of these graphs, we discuss a few examples which support the conjecture that by counting the nodal domains of the corresponding eigenfunctions one can resolve the isospectral ambiguity

Topological quantum field theories in terms of coloured graphs associated to quantum groups

International Nuclear Information System (INIS)

Karowski, M.

1993-01-01

Apart from obvious mathematical applications the investigation is motivated by the problem of braid group statistics in physics. Statistics is one of the central concepts in many body quantum systems. Consider a system of two identical particles located at x 1 and x 2 in R d with Schroedinger wave function ψ(x 1 , x 2 ). Under the exchange of particles with these coordinates one usually has Bose or Fermi statistics in case ψ(x 2 , x 1 )=±ψ(x-1,x T 2). For a quick access to the problem consider the following classical geometric space-time description of the exchange of position for two identical particles, reflecting itself in two quantum mechanical transformation laws. We briefly review the set-up of topological quantum field theory and present our new formulation in terms of coloured graphs. (orig.)

Graph Quasicontinuous Functions and Densely Continuous Forms

Directory of Open Access Journals (Sweden)

Lubica Hola

2017-07-01

Full Text Available Let $X, Y$ be topological spaces. A function $f: X \\to Y$ is said to be graph quasicontinuous if there is a quasicontinuous function $g: X \\to Y$ with the graph of $g$ contained in the closure of the graph of $f$. There is a close relation between the notions of graph quasicontinuous functions and minimal usco maps as well as the notions of graph quasicontinuous functions and densely continuous forms. Every function with values in a compact Hausdorff space is graph quasicontinuous; more generally every locally compact function is graph quasicontinuous.

Quantum graphs: a simple model for chaotic scattering

International Nuclear Information System (INIS)

Kottos, Tsampikos; Smilansky, Uzy

2003-01-01

We connect quantum graphs with infinite leads, and turn them into scattering systems. We show that they display all the features which characterize quantum scattering systems with an underlying classical chaotic dynamics: typical poles, delay time and conductance distributions, Ericson fluctuations, and when considered statistically, the ensemble of scattering matrices reproduces quite well the predictions of the appropriately defined random matrix ensembles. The underlying classical dynamics can be defined, and it provides important parameters which are needed for the quantum theory. In particular, we derive exact expressions for the scattering matrix, and an exact trace formula for the density of resonances, in terms of classical orbits, analogous to the semiclassical theory of chaotic scattering. We use this in order to investigate the origin of the connection between random matrix theory and the underlying classical chaotic dynamics. Being an exact theory, and due to its relative simplicity, it offers new insights into this problem which is at the forefront of the research in chaotic scattering and related fields

An Infinite Family of Circulant Graphs with Perfect State Transfer in Discrete Quantum Walks

OpenAIRE

Zhan, Hanmeng

2017-01-01

We study perfect state transfer in a discrete quantum walk. In particular, we show that there are infinitely many $4$-regular circulant graphs that admit perfect state transfer between antipodal vertices. To the best of our knowledge, previously there was no infinite family of $k$-regular graphs with perfect state transfer, for any $k\\ge 3$.

Isospectral discrete and quantum graphs with the same flip counts and nodal counts

Science.gov (United States)

Juul, Jonas S.; Joyner, Christopher H.

2018-06-01

The existence of non-isomorphic graphs which share the same Laplace spectrum (to be referred to as isospectral graphs) leads naturally to the following question: what additional information is required in order to resolve isospectral graphs? It was suggested by Band, Shapira and Smilansky that this might be achieved by either counting the number of nodal domains or the number of times the eigenfunctions change sign (the so-called flip count) (Band et al 2006 J. Phys. A: Math. Gen. 39 13999–4014 Band and Smilansky 2007 Eur. Phys. J. Spec. Top. 145 171–9). Recent examples of (discrete) isospectral graphs with the same flip count and nodal count have been constructed by Ammann by utilising Godsil–McKay switching (Ammann private communication). Here, we provide a simple alternative mechanism that produces systematic examples of both discrete and quantum isospectral graphs with the same flip and nodal counts.

Graph-state preparation and quantum computation with global addressing of optical lattices

International Nuclear Information System (INIS)

Kay, Alastair; Pachos, Jiannis K.; Adams, Charles S.

2006-01-01

We present a way to manipulate ultracold atoms where four atomic levels are trapped by appropriately tuned optical lattices. When employed to perform quantum computation via global control, this unique structure dramatically reduces the number of steps involved in the control procedures, either for the standard, network, model, or for one-way quantum computation. The use of a far-blue-detuned lattice and a magnetically insensitive computational basis makes the scheme robust against decoherence. The present scheme is a promising candidate for experimental implementation of quantum computation and for graph-state preparation in one, two, or three spatial dimensions

Spectral fluctuations of quantum graphs

International Nuclear Information System (INIS)

Pluhař, Z.; Weidenmüller, H. A.

2014-01-01

We prove the Bohigas-Giannoni-Schmit conjecture in its most general form for completely connected simple graphs with incommensurate bond lengths. We show that for graphs that are classically mixing (i.e., graphs for which the spectrum of the classical Perron-Frobenius operator possesses a finite gap), the generating functions for all (P,Q) correlation functions for both closed and open graphs coincide (in the limit of infinite graph size) with the corresponding expressions of random-matrix theory, both for orthogonal and for unitary symmetry

Non-Weyl resonance asymptotics for quantum graphs in a magnetic field

Czech Academy of Sciences Publication Activity Database

Exner, Pavel; Lipovský, J.

2011-01-01

Roč. 375, č. 4 (2011), s. 805-807 ISSN 0375-9601 R&D Projects: GA MŠk LC06002; GA ČR GAP203/11/0701 Institutional research plan: CEZ:AV0Z10480505 Keywords : Quantum graphs * Magnetic field * Resonances Subject RIV: BG - Nuclear, Atomic and Molecular Physics, Colliders Impact factor: 1.632, year: 2011

Simulating triangulations. Graphs, manifolds and (quantum) spacetime

International Nuclear Information System (INIS)

Krueger, Benedikt

2016-01-01

Triangulations, which can intuitively be described as a tessellation of space into simplicial building blocks, are structures that arise in various different branches of physics: They can be used for describing complicated and curved objects in a discretized way, e.g., in foams, gels or porous media, or for discretizing curved boundaries for fluid simulations or dissipative systems. Interpreting triangulations as (maximal planar) graphs makes it possible to use them in graph theory or statistical physics, e.g., as small-world networks, as networks of spins or in biological physics as actin networks. Since one can find an analogue of the Einstein-Hilbert action on triangulations, they can even be used for formulating theories of quantum gravity. Triangulations have also important applications in mathematics, especially in discrete topology. Despite their wide occurrence in different branches of physics and mathematics, there are still some fundamental open questions about triangulations in general. It is a prior unknown how many triangulations there are for a given set of points or a given manifold, or even whether there are exponentially many triangulations or more, a question that relates to a well-defined behavior of certain quantum geometry models. Another major unknown question is whether elementary steps transforming triangulations into each other, which are used in computer simulations, are ergodic. Using triangulations as model for spacetime, it is not clear whether there is a meaningful continuum limit that can be identified with the usual and well-tested theory of general relativity. Within this thesis some of these fundamental questions about triangulations are answered by the use of Markov chain Monte Carlo simulations, which are a probabilistic method for calculating statistical expectation values, or more generally a tool for calculating high-dimensional integrals. Additionally, some details about the Wang-Landau algorithm, which is the primary used

Simulating triangulations. Graphs, manifolds and (quantum) spacetime

Energy Technology Data Exchange (ETDEWEB)

Krueger, Benedikt

2016-07-01

Triangulations, which can intuitively be described as a tessellation of space into simplicial building blocks, are structures that arise in various different branches of physics: They can be used for describing complicated and curved objects in a discretized way, e.g., in foams, gels or porous media, or for discretizing curved boundaries for fluid simulations or dissipative systems. Interpreting triangulations as (maximal planar) graphs makes it possible to use them in graph theory or statistical physics, e.g., as small-world networks, as networks of spins or in biological physics as actin networks. Since one can find an analogue of the Einstein-Hilbert action on triangulations, they can even be used for formulating theories of quantum gravity. Triangulations have also important applications in mathematics, especially in discrete topology. Despite their wide occurrence in different branches of physics and mathematics, there are still some fundamental open questions about triangulations in general. It is a prior unknown how many triangulations there are for a given set of points or a given manifold, or even whether there are exponentially many triangulations or more, a question that relates to a well-defined behavior of certain quantum geometry models. Another major unknown question is whether elementary steps transforming triangulations into each other, which are used in computer simulations, are ergodic. Using triangulations as model for spacetime, it is not clear whether there is a meaningful continuum limit that can be identified with the usual and well-tested theory of general relativity. Within this thesis some of these fundamental questions about triangulations are answered by the use of Markov chain Monte Carlo simulations, which are a probabilistic method for calculating statistical expectation values, or more generally a tool for calculating high-dimensional integrals. Additionally, some details about the Wang-Landau algorithm, which is the primary used

Quantum dynamics via Planck-scale-stepped action-carrying 'Graph Paths'

CERN Document Server

Chew, Geoffrey Foucar

2003-01-01

A divergence-free, parameter-free, path-based discrete-time quantum dynamics is designed to not only enlarge the achievements of general relativity and the standard particle model, by approximations at spacetime scales far above Planck scale while far below Hubble scale, but to allow tackling of hitherto inaccessible questions. ''Path space'' is larger than and precursor to Hilbert-space basis. The wave-function-propagating paths are action-carrying structured graphs-cubic and quartic structured vertices connected by structured ''fermionic'' or ''bosonic'' ''particle'' and ''nonparticle'' arcs. A Planck-scale path step determines the gravitational constant while controlling all graph structure. The basis of the theory's (zero-rest-mass) elementary-particle Hilbert space (which includes neither gravitons nor scalar bosons) resides in particle arcs. Nonparticle arcs within a path are responsible for energy and rest mass.

Low Cost and Compact Quantum Cryptography

OpenAIRE

Duligall, J. L.; Godfrey, M. S.; Harrison, K. A.; Munro, W. J.; Rarity, J. G.

2006-01-01

We present the design of a novel free-space quantum cryptography system, complete with purpose-built software, that can operate in daylight conditions. The transmitter and receiver modules are built using inexpensive off-the-shelf components. Both modules are compact allowing the generation of renewed shared secrets on demand over a short range of a few metres. An analysis of the software is shown as well as results of error rates and therefore shared secret yields at varying background light...

Delay-time distribution in the scattering of time-narrow wave packets (II)—quantum graphs

Science.gov (United States)

Smilansky, Uzy; Schanz, Holger

2018-02-01

We apply the framework developed in the preceding paper in this series (Smilansky 2017 J. Phys. A: Math. Theor. 50 215301) to compute the time-delay distribution in the scattering of ultra short radio frequency pulses on complex networks of transmission lines which are modeled by metric (quantum) graphs. We consider wave packets which are centered at high wave number and comprise many energy levels. In the limit of pulses of very short duration we compute upper and lower bounds to the actual time-delay distribution of the radiation emerging from the network using a simplified problem where time is replaced by the discrete count of vertex-scattering events. The classical limit of the time-delay distribution is also discussed and we show that for finite networks it decays exponentially, with a decay constant which depends on the graph connectivity and the distribution of its edge lengths. We illustrate and apply our theory to a simple model graph where an algebraic decay of the quantum time-delay distribution is established.

Quantum vacuum energy in graphs and billiards

International Nuclear Information System (INIS)

Kaplan, L.

2010-01-01

The vacuum (Casimir) energy in quantum field theory is a problem relevant both to new nanotechnology devices and to dark energy in cosmology. The crucial question is the dependence of the energy on the system geometry. Despite much progress since the first prediction of the Casimir effect in 1948 and its subsequent experimental verification in simple geometries, even the sign of the force in nontrivial situations is still a matter of controversy. Mathematically, vacuum energy fits squarely into the spectral theory of second-order self-adjoint elliptic linear differential operators. Specifically one promising approach is based on the small-t asymptotics of the cylinder kernel e -t√(H) , where H is the self-adjoint operator under study. In contrast with the well-studied heat kernel e -tH , the cylinder kernel depends in a non-local way on the geometry of the problem. We discuss some results by the Louisiana-Oklahoma-Texas collaboration on vacuum energy in model systems, including quantum graphs and two-dimensional cavities. The results may shed light on general questions, including the relationship between vacuum energy and periodic or closed classical orbits, and the contribution to vacuum energy of boundaries, edges, and corners.

Compact 3D quantum memory

Science.gov (United States)

Xie, Edwar; Deppe, Frank; Renger, Michael; Repp, Daniel; Eder, Peter; Fischer, Michael; Goetz, Jan; Pogorzalek, Stefan; Fedorov, Kirill G.; Marx, Achim; Gross, Rudolf

2018-05-01

Superconducting 3D microwave cavities offer state-of-the-art coherence times and a well-controlled environment for superconducting qubits. In order to realize at the same time fast readout and long-lived quantum information storage, one can couple the qubit to both a low-quality readout and a high-quality storage cavity. However, such systems are bulky compared to their less coherent 2D counterparts. A more compact and scalable approach is achieved by making use of the multimode structure of a 3D cavity. In our work, we investigate such a device where a transmon qubit is capacitively coupled to two modes of a single 3D cavity. External coupling is engineered so that the memory mode has an about 100 times larger quality factor than the readout mode. Using an all-microwave second-order protocol, we realize a lifetime enhancement of the stored state over the qubit lifetime by a factor of 6 with a fidelity of approximately 80% determined via quantum process tomography. We also find that this enhancement is not limited by fundamental constraints.

Quantum logic using correlated one-dimensional quantum walks

Science.gov (United States)

Lahini, Yoav; Steinbrecher, Gregory R.; Bookatz, Adam D.; Englund, Dirk

2018-01-01

Quantum Walks are unitary processes describing the evolution of an initially localized wavefunction on a lattice potential. The complexity of the dynamics increases significantly when several indistinguishable quantum walkers propagate on the same lattice simultaneously, as these develop non-trivial spatial correlations that depend on the particle's quantum statistics, mutual interactions, initial positions, and the lattice potential. We show that even in the simplest case of a quantum walk on a one dimensional graph, these correlations can be shaped to yield a complete set of compact quantum logic operations. We provide detailed recipes for implementing quantum logic on one-dimensional quantum walks in two general cases. For non-interacting bosons—such as photons in waveguide lattices—we find high-fidelity probabilistic quantum gates that could be integrated into linear optics quantum computation schemes. For interacting quantum-walkers on a one-dimensional lattice—a situation that has recently been demonstrated using ultra-cold atoms—we find deterministic logic operations that are universal for quantum information processing. The suggested implementation requires minimal resources and a level of control that is within reach using recently demonstrated techniques. Further work is required to address error-correction.

Gaps in the spectrum of a periodic quantum graph with periodically distributed delta '-type interactions

Czech Academy of Sciences Publication Activity Database

Barseghyan, Diana; Khrabustovskyi, A.

2015-01-01

Roč. 48, č. 25 (2015), s. 255201 ISSN 1751-8113 Institutional support: RVO:61389005 Keywords : periodic quantum graphs * delta'-type interactions * spectral gaps Subject RIV: BE - Theoretical Physics Impact factor: 1.933, year: 2015

Compact quantum group C*-algebras as Hopf algebras with approximate unit

International Nuclear Information System (INIS)

Do Ngoc Diep; Phung Ho Hai; Kuku, A.O.

1999-04-01

In this paper, we construct and study the representation theory of a Hopf C*-algebra with approximate unit, which constitutes quantum analogue of a compact group C*-algebra. The construction is done by first introducing a convolution-product on an arbitrary Hopf algebra H with integral, and then constructing the L 2 and C*-envelopes of H (with the new convolution-product) when H is a compact Hopf *-algebra. (author)

A quantum annealing approach for fault detection and diagnosis of graph-based systems

Science.gov (United States)

Perdomo-Ortiz, A.; Fluegemann, J.; Narasimhan, S.; Biswas, R.; Smelyanskiy, V. N.

2015-02-01

Diagnosing the minimal set of faults capable of explaining a set of given observations, e.g., from sensor readouts, is a hard combinatorial optimization problem usually tackled with artificial intelligence techniques. We present the mapping of this combinatorial problem to quadratic unconstrained binary optimization (QUBO), and the experimental results of instances embedded onto a quantum annealing device with 509 quantum bits. Besides being the first time a quantum approach has been proposed for problems in the advanced diagnostics community, to the best of our knowledge this work is also the first research utilizing the route Problem → QUBO → Direct embedding into quantum hardware, where we are able to implement and tackle problem instances with sizes that go beyond previously reported toy-model proof-of-principle quantum annealing implementations; this is a significant leap in the solution of problems via direct-embedding adiabatic quantum optimization. We discuss some of the programmability challenges in the current generation of the quantum device as well as a few possible ways to extend this work to more complex arbitrary network graphs.

Bell inequalities for graph states

International Nuclear Information System (INIS)

Toth, G.; Hyllus, P.; Briegel, H.J.; Guehne, O.

2005-01-01

Full text: In the last years graph states have attracted an increasing interest in the field of quantum information theory. Graph states form a family of multi-qubit states which comprises many popular states such as the GHZ states and the cluster states. They also play an important role in applications. For instance, measurement based quantum computation uses graph states as resources. From a theoretical point of view, it is remarkable that graph states allow for a simple description in terms of stabilizing operators. In this contribution, we investigate the non-local properties of graph states. We derive a family of Bell inequalities which require three measurement settings for each party and are maximally violated by graph states. In turn, any graph state violates at least one of the inequalities. We show that for certain types of graph states the violation of these inequalities increases exponentially with the number of qubits. We also discuss connections to other entanglement properties such as the positively of the partial transpose or the geometric measure of entanglement. (author)

Algebras of functions on compact quantum groups, Schubert cells and quantum tori

International Nuclear Information System (INIS)

Levendorskij, S.; Soibelman, Ya.

1991-01-01

The structure of Poisson Lie groups on a simple compact group are parametrized by pairs (a, u), where aelement ofR, uelement ofΛ 2 f R , and f R is a real Cartan subalgebra of complexification of Lie algebra of the group in question. In the present article the description of the symplectic leaves for all pairs (a, u) is given. Also, the corresponding quantized algebras of functions are constructed and their irreducible representations are described. In the course of investigation Schubert cells and quantum tori appear. At the end of the article the quantum analog of the Weyl group is constructed and some of its applications, among them the formula for the universal R-matrix, are given. (orig.)

Combination of short-length TiO_2 nanorod arrays and compact PbS quantum-dot thin films for efficient solid-state quantum-dot-sensitized solar cells

International Nuclear Information System (INIS)

Zhang, Zhengguo; Shi, Chengwu; Chen, Junjun; Xiao, Guannan; Li, Long

2017-01-01

Graphical abstract: The TiO_2 nanorod array with the length of 600 nm, the diameter of 20 nm, the areal density of 500 μm"−"2 was successfully prepared. The compact PbS quantum-dot thin film was firstly obtained on the TiO_2 nanorod array by spin-coating-assisted successive ionic layer absorption and reaction with using 1,2-ethanedithiol. The photoelectric conversion efficiency (PCE) of the compact PbS quantum-dot thin film sensitized solar cells achieved 4.10% using spiro-OMeTAD as a hole transporting layer, while the PCE of the PbS quantum-dot sensitized solar cells was only 0.54%. - Highlights: • Preparation of TiO_2 nanorod arrays with the length of 600 nm, diameter of 20 nm. • The compact PbS QD thin film and short-length TiO_2 nanorod array were combined. • EDT addition improved PbS nanoparticle coverage and photovoltaic performance. • The compact PbS QD thin film sensitized solar cell achieved the PCE of 4.10%. - Abstract: Considering the balance of the hole diffusion length and the loading quantity of quantum-dots, the rutile TiO_2 nanorod array with the length of 600 nm, the diameter of 20 nm, and the areal density of 500 μm"−"2 is successfully prepared by the hydrothermal method using the aqueous grown solution of 38 mM titanium isopropoxide and 6 M hydrochloric acid at 170 °C for 105 min. The compact PbS quantum-dot thin film on the TiO_2 nanorod array is firstly obtained by the spin-coating-assisted successive ionic layer absorption and reaction with using 1,2-ethanedithiol (EDT). The result reveals that the strong interaction between lead and EDT is very important to control the crystallite size of PbS quantum-dots and obtain the compact PbS quantum-dot thin film on the TiO_2 nanorod array. The all solid-state sensitized solar cell with the combination of the short-length, high-density TiO_2 nanorod array and the compact PbS quantum-dot thin film achieves the photoelectric conversion efficiency of 4.10%, along with an open

Two-dimensional quantum gravity - a laboratory for fluctuating graphs and quenched connectivity disorder

Directory of Open Access Journals (Sweden)

W.Janke

2006-01-01

Full Text Available This paper gives a brief introduction to using two-dimensional discrete and Euclidean quantum gravity approaches as a laboratory for studying the properties of fluctuating and frozen random graphs in interaction with "matter fields" represented by simple spin or vertex models. Due to the existence of numerous exact analytical results and predictions for comparison with simulational work, this is an interesting and useful enterprise.

Exclusivity structures and graph representatives of local complementation orbits

Science.gov (United States)

Cabello, Adán; Parker, Matthew G.; Scarpa, Giannicola; Severini, Simone

2013-07-01

We describe a construction that maps any connected graph G on three or more vertices into a larger graph, H(G), whose independence number is strictly smaller than its Lovász number which is equal to its fractional packing number. The vertices of H(G) represent all possible events consistent with the stabilizer group of the graph state associated with G, and exclusive events are adjacent. Mathematically, the graph H(G) corresponds to the orbit of G under local complementation. Physically, the construction translates into graph-theoretic terms the connection between a graph state and a Bell inequality maximally violated by quantum mechanics. In the context of zero-error information theory, the construction suggests a protocol achieving the maximum rate of entanglement-assisted capacity, a quantum mechanical analogue of the Shannon capacity, for each H(G). The violation of the Bell inequality is expressed by the one-shot version of this capacity being strictly larger than the independence number. Finally, given the correspondence between graphs and exclusivity structures, we are able to compute the independence number for certain infinite families of graphs with the use of quantum non-locality, therefore highlighting an application of quantum theory in the proof of a purely combinatorial statement.

Operating single quantum emitters with a compact Stirling cryocooler.

Science.gov (United States)

Schlehahn, A; Krüger, L; Gschrey, M; Schulze, J-H; Rodt, S; Strittmatter, A; Heindel, T; Reitzenstein, S

2015-01-01

The development of an easy-to-operate light source emitting single photons has become a major driving force in the emerging field of quantum information technology. Here, we report on the application of a compact and user-friendly Stirling cryocooler in the field of nanophotonics. The Stirling cryocooler is used to operate a single quantum emitter constituted of a semiconductor quantum dot (QD) at a base temperature below 30 K. Proper vibration decoupling of the cryocooler and its surrounding enables free-space micro-photoluminescence spectroscopy to identify and analyze different charge-carrier states within a single quantum dot. As an exemplary application in quantum optics, we perform a Hanbury-Brown and Twiss experiment demonstrating a strong suppression of multi-photon emission events with g((2))(0) Stirling-cooled single quantum emitter under continuous wave excitation. Comparative experiments performed on the same quantum dot in a liquid helium (LHe)-flow cryostat show almost identical values of g((2))(0) for both configurations at a given temperature. The results of this proof of principle experiment demonstrate that low-vibration Stirling cryocoolers that have so far been considered exotic to the field of nanophotonics are an attractive alternative to expensive closed-cycle cryostats or LHe-flow cryostats, which could pave the way for the development of high-quality table-top non-classical light sources.

Operating single quantum emitters with a compact Stirling cryocooler

Energy Technology Data Exchange (ETDEWEB)

Schlehahn, A.; Krüger, L.; Gschrey, M.; Schulze, J.-H.; Rodt, S.; Strittmatter, A.; Heindel, T., E-mail: tobias.heindel@tu-berlin.de; Reitzenstein, S. [Institute of Solid State Physics, Technische Universität Berlin, 10623 Berlin (Germany)

2015-01-15

The development of an easy-to-operate light source emitting single photons has become a major driving force in the emerging field of quantum information technology. Here, we report on the application of a compact and user-friendly Stirling cryocooler in the field of nanophotonics. The Stirling cryocooler is used to operate a single quantum emitter constituted of a semiconductor quantum dot (QD) at a base temperature below 30 K. Proper vibration decoupling of the cryocooler and its surrounding enables free-space micro-photoluminescence spectroscopy to identify and analyze different charge-carrier states within a single quantum dot. As an exemplary application in quantum optics, we perform a Hanbury-Brown and Twiss experiment demonstrating a strong suppression of multi-photon emission events with g{sup (2)}(0) < 0.04 from this Stirling-cooled single quantum emitter under continuous wave excitation. Comparative experiments performed on the same quantum dot in a liquid helium (LHe)-flow cryostat show almost identical values of g{sup (2)}(0) for both configurations at a given temperature. The results of this proof of principle experiment demonstrate that low-vibration Stirling cryocoolers that have so far been considered exotic to the field of nanophotonics are an attractive alternative to expensive closed-cycle cryostats or LHe-flow cryostats, which could pave the way for the development of high-quality table-top non-classical light sources.

Efficient quantum circuits for Szegedy quantum walks

International Nuclear Information System (INIS)

Loke, T.; Wang, J.B.

2017-01-01

A major advantage in using Szegedy’s formalism over discrete-time and continuous-time quantum walks lies in its ability to define a unitary quantum walk by quantizing a Markov chain on a directed or weighted graph. In this paper, we present a general scheme to construct efficient quantum circuits for Szegedy quantum walks that correspond to classical Markov chains possessing transformational symmetry in the columns of the transition matrix. In particular, the transformational symmetry criteria do not necessarily depend on the sparsity of the transition matrix, so this scheme can be applied to non-sparse Markov chains. Two classes of Markov chains that are amenable to this construction are cyclic permutations and complete bipartite graphs, for which we provide explicit efficient quantum circuit implementations. We also prove that our scheme can be applied to Markov chains formed by a tensor product. We also briefly discuss the implementation of Markov chains based on weighted interdependent networks. In addition, we apply this scheme to construct efficient quantum circuits simulating the Szegedy walks used in the quantum Pagerank algorithm for some classes of non-trivial graphs, providing a necessary tool for experimental demonstration of the quantum Pagerank algorithm. - Highlights: • A general theoretical framework for implementing Szegedy walks using quantum circuits. • Explicit efficient quantum circuit implementation of the Szegedy walk for several classes of graphs. • Efficient implementation of Szegedy walks for quantum page-ranking of a certain class of graphs.

Counting surface-kernel epimorphisms from a co-compact Fuchsian group to a cyclic group with motivations from string theory and QFT

Directory of Open Access Journals (Sweden)

Khodakhast Bibak

2016-09-01

Full Text Available Graphs embedded into surfaces have many important applications, in particular, in combinatorics, geometry, and physics. For example, ribbon graphs and their counting is of great interest in string theory and quantum field theory (QFT. Recently, Koch et al. (2013 [12] gave a refined formula for counting ribbon graphs and discussed its applications to several physics problems. An important factor in this formula is the number of surface-kernel epimorphisms from a co-compact Fuchsian group to a cyclic group. The aim of this paper is to give an explicit and practical formula for the number of such epimorphisms. As a consequence, we obtain an ‘equivalent’ form of Harvey's famous theorem on the cyclic groups of automorphisms of compact Riemann surfaces. Our main tool is an explicit formula for the number of solutions of restricted linear congruence recently proved by Bibak et al. using properties of Ramanujan sums and of the finite Fourier transform of arithmetic functions.

Counting surface-kernel epimorphisms from a co-compact Fuchsian group to a cyclic group with motivations from string theory and QFT

Energy Technology Data Exchange (ETDEWEB)

Bibak, Khodakhast, E-mail: kbibak@uvic.ca; Kapron, Bruce M., E-mail: bmkapron@uvic.ca; Srinivasan, Venkatesh, E-mail: srinivas@uvic.ca

2016-09-15

Graphs embedded into surfaces have many important applications, in particular, in combinatorics, geometry, and physics. For example, ribbon graphs and their counting is of great interest in string theory and quantum field theory (QFT). Recently, Koch et al. (2013) gave a refined formula for counting ribbon graphs and discussed its applications to several physics problems. An important factor in this formula is the number of surface-kernel epimorphisms from a co-compact Fuchsian group to a cyclic group. The aim of this paper is to give an explicit and practical formula for the number of such epimorphisms. As a consequence, we obtain an ‘equivalent’ form of Harvey's famous theorem on the cyclic groups of automorphisms of compact Riemann surfaces. Our main tool is an explicit formula for the number of solutions of restricted linear congruence recently proved by Bibak et al. using properties of Ramanujan sums and of the finite Fourier transform of arithmetic functions.

Combination of short-length TiO{sub 2} nanorod arrays and compact PbS quantum-dot thin films for efficient solid-state quantum-dot-sensitized solar cells

Energy Technology Data Exchange (ETDEWEB)

Zhang, Zhengguo [School of Chemistry and Chemical Engineering, Hefei University of Technology, Hefei 230009 (China); School of Chemistry and Chemical Engineering, Beifang University of Nationalities, Yinchuan 750021 (China); Shi, Chengwu, E-mail: shicw506@foxmail.com [School of Chemistry and Chemical Engineering, Hefei University of Technology, Hefei 230009 (China); Chen, Junjun; Xiao, Guannan; Li, Long [School of Chemistry and Chemical Engineering, Hefei University of Technology, Hefei 230009 (China)

2017-07-15

Graphical abstract: The TiO{sub 2} nanorod array with the length of 600 nm, the diameter of 20 nm, the areal density of 500 μm{sup −2} was successfully prepared. The compact PbS quantum-dot thin film was firstly obtained on the TiO{sub 2} nanorod array by spin-coating-assisted successive ionic layer absorption and reaction with using 1,2-ethanedithiol. The photoelectric conversion efficiency (PCE) of the compact PbS quantum-dot thin film sensitized solar cells achieved 4.10% using spiro-OMeTAD as a hole transporting layer, while the PCE of the PbS quantum-dot sensitized solar cells was only 0.54%. - Highlights: • Preparation of TiO{sub 2} nanorod arrays with the length of 600 nm, diameter of 20 nm. • The compact PbS QD thin film and short-length TiO{sub 2} nanorod array were combined. • EDT addition improved PbS nanoparticle coverage and photovoltaic performance. • The compact PbS QD thin film sensitized solar cell achieved the PCE of 4.10%. - Abstract: Considering the balance of the hole diffusion length and the loading quantity of quantum-dots, the rutile TiO{sub 2} nanorod array with the length of 600 nm, the diameter of 20 nm, and the areal density of 500 μm{sup −2} is successfully prepared by the hydrothermal method using the aqueous grown solution of 38 mM titanium isopropoxide and 6 M hydrochloric acid at 170 °C for 105 min. The compact PbS quantum-dot thin film on the TiO{sub 2} nanorod array is firstly obtained by the spin-coating-assisted successive ionic layer absorption and reaction with using 1,2-ethanedithiol (EDT). The result reveals that the strong interaction between lead and EDT is very important to control the crystallite size of PbS quantum-dots and obtain the compact PbS quantum-dot thin film on the TiO{sub 2} nanorod array. The all solid-state sensitized solar cell with the combination of the short-length, high-density TiO{sub 2} nanorod array and the compact PbS quantum-dot thin film achieves the photoelectric conversion

Efficient quantum walk on a quantum processor

Science.gov (United States)

Qiang, Xiaogang; Loke, Thomas; Montanaro, Ashley; Aungskunsiri, Kanin; Zhou, Xiaoqi; O'Brien, Jeremy L.; Wang, Jingbo B.; Matthews, Jonathan C. F.

2016-01-01

The random walk formalism is used across a wide range of applications, from modelling share prices to predicting population genetics. Likewise, quantum walks have shown much potential as a framework for developing new quantum algorithms. Here we present explicit efficient quantum circuits for implementing continuous-time quantum walks on the circulant class of graphs. These circuits allow us to sample from the output probability distributions of quantum walks on circulant graphs efficiently. We also show that solving the same sampling problem for arbitrary circulant quantum circuits is intractable for a classical computer, assuming conjectures from computational complexity theory. This is a new link between continuous-time quantum walks and computational complexity theory and it indicates a family of tasks that could ultimately demonstrate quantum supremacy over classical computers. As a proof of principle, we experimentally implement the proposed quantum circuit on an example circulant graph using a two-qubit photonics quantum processor. PMID:27146471

Quantum walks, quantum gates, and quantum computers

International Nuclear Information System (INIS)

Hines, Andrew P.; Stamp, P. C. E.

2007-01-01

The physics of quantum walks on graphs is formulated in Hamiltonian language, both for simple quantum walks and for composite walks, where extra discrete degrees of freedom live at each node of the graph. It is shown how to map between quantum walk Hamiltonians and Hamiltonians for qubit systems and quantum circuits; this is done for both single-excitation and multiexcitation encodings. Specific examples of spin chains, as well as static and dynamic systems of qubits, are mapped to quantum walks, and walks on hyperlattices and hypercubes are mapped to various gate systems. We also show how to map a quantum circuit performing the quantum Fourier transform, the key element of Shor's algorithm, to a quantum walk system doing the same. The results herein are an essential preliminary to a Hamiltonian formulation of quantum walks in which coupling to a dynamic quantum environment is included

Phase-modified CTQW unable to distinguish strongly regular graphs efficiently

International Nuclear Information System (INIS)

Mahasinghe, A; Wijerathna, J K; Izaac, J A; Wang, J B

2015-01-01

Various quantum walk-based algorithms have been developed, aiming to distinguish non-isomorphic graphs with polynomial scaling, within both the discrete-time quantum walk (DTQW) and continuous-time quantum walk (CTQW) frameworks. Whilst both the single-particle DTQW and CTQW have failed to distinguish non-isomorphic strongly regular graph families (prompting the move to multi-particle graph isomorphism (GI) algorithms), the single-particle DTQW has been successfully modified by the introduction of a phase factor to distinguish a wide range of graphs in polynomial time. In this paper, we prove that an analogous phase modification to the single particle CTQW does not have the same distinguishing power as its discrete-time counterpart, in particular it cannot distinguish strongly regular graphs with the same family parameters with the same efficiency. (paper)

Loop quantum gravity in asymptotically flat spaces

International Nuclear Information System (INIS)

Arnsdorf, M.

2000-01-01

This thesis describes applications and extensions of the loop variable approach to non-perturbative quantum gravity. The common theme of the work presented, is the need to generalise loop quantum gravity to be applicable in cases where space is asymptotically flat, and no longer compact as is usually assumed. This is important for the study of isolated gravitational systems. It also presents a natural context in which to search for the semi-classical limit, one of the main outstanding problems in loop quantum gravity. In the first part of the thesis we study how isolated gravitational systems can be attributed particle-like properties. In particular, we show how spinorial states can arise in pure loop quantum gravity if spatial topology is non-trivial, thus confirming an old conjecture of Friedman and Sorkin. Heuristically, this corresponds to the idea that we can rotate isolated regions of spatial topology relative to the environment at infinity, and that only a 4π-rotation will take us back to the original configuration. To do this we extend the standard loop quantum gravity formalism by introducing a compactification of our non-compact spatial manifold, and study the knotting of embedded graphs. The second part of the thesis takes a more systematic approach to the study of loop quantum gravity on non-compact spaces. We look for new representations of the loop algebra, which give rise to quantum theories that are inequivalent to the standard one. These theories naturally describe excitations of a fiducial background state, which is specified via the choice of its vacuum expectation values. In particular, we can choose background states that describe the geometries of non-compact manifolds. We also discuss how suitable background states can be constructed that can approximate classical phase space data, in our case holonomies along embedded paths and geometrical quantities related to areas and volumes. These states extend the notion of the weave and provide a

Greenberger-Horne-Zeilinger paradoxes from qudit graph states.

Science.gov (United States)

Tang, Weidong; Yu, Sixia; Oh, C H

2013-03-08

One fascinating way of revealing quantum nonlocality is the all-versus-nothing test due to Greenberger, Horne, and Zeilinger (GHZ) known as the GHZ paradox. So far genuine multipartite and multilevel GHZ paradoxes are known to exist only in systems containing an odd number of particles. Here we shall construct GHZ paradoxes for an arbitrary number (greater than 3) of particles with the help of qudit graph states on a special kind of graphs, called GHZ graphs. Furthermore, based on the GHZ paradox arising from a GHZ graph, we derive a Bell inequality with two d-outcome observables for each observer, whose maximal violation attained by the corresponding graph state, and a Kochen-Specker inequality testing the quantum contextuality in a state-independent fashion.

Graph-based clustering and data visualization algorithms

CERN Document Server

Vathy-Fogarassy, Ágnes

2013-01-01

This work presents a data visualization technique that combines graph-based topology representation and dimensionality reduction methods to visualize the intrinsic data structure in a low-dimensional vector space. The application of graphs in clustering and visualization has several advantages. A graph of important edges (where edges characterize relations and weights represent similarities or distances) provides a compact representation of the entire complex data set. This text describes clustering and visualization methods that are able to utilize information hidden in these graphs, based on

Efficient quantum circuit implementation of quantum walks

International Nuclear Information System (INIS)

Douglas, B. L.; Wang, J. B.

2009-01-01

Quantum walks, being the quantum analog of classical random walks, are expected to provide a fruitful source of quantum algorithms. A few such algorithms have already been developed, including the 'glued trees' algorithm, which provides an exponential speedup over classical methods, relative to a particular quantum oracle. Here, we discuss the possibility of a quantum walk algorithm yielding such an exponential speedup over possible classical algorithms, without the use of an oracle. We provide examples of some highly symmetric graphs on which efficient quantum circuits implementing quantum walks can be constructed and discuss potential applications to quantum search for marked vertices along these graphs.

A brilliant sandwich type fluorescent nanostructure incorporating a compact quantum dot layer and versatile silica substrates.

Science.gov (United States)

Huang, Liang; Wu, Qiong; Wang, Jing; Foda, Mohamed; Liu, Jiawei; Cai, Kai; Han, Heyou

2014-03-18

A "hydrophobic layer in silica" structure was designed to integrate a compact quantum dot (QD) layer with high quantum yield into scalable silica hosts containing desired functionality. This was based on metal affinity driven assembly of hydrophobic QDs with versatile silica substrates and homogeneous encapsulation of organosilica/silica layers.

Circuit and bond polytopes on series–parallel graphs

OpenAIRE

Borne , Sylvie; Fouilhoux , Pierre; Grappe , Roland; Lacroix , Mathieu; Pesneau , Pierre

2015-01-01

International audience; In this paper, we describe the circuit polytope on series–parallel graphs. We first show the existence of a compact extended formulation. Though not being explicit, its construction process helps us to inductively provide the description in the original space. As a consequence, using the link between bonds and circuits in planar graphs, we also describe the bond polytope on series–parallel graphs.

A compact T-shaped nanodevice for charge sensing of a tunable double quantum dot in scalable silicon technology

Energy Technology Data Exchange (ETDEWEB)

Tagliaferri, M.L.V., E-mail: marco.tagliaferri@mdm.imm.cnr.it [Laboratorio MDM, CNR-IMM, Via C. Olivetti 2, 20864 Agrate Brianza (MB) (Italy); Dipartimento di Scienza dei Materiali, Università di Milano Bicocca, Via Cozzi 53, 20125 Milano (Italy); Crippa, A. [Laboratorio MDM, CNR-IMM, Via C. Olivetti 2, 20864 Agrate Brianza (MB) (Italy); Dipartimento di Scienza dei Materiali, Università di Milano Bicocca, Via Cozzi 53, 20125 Milano (Italy); De Michielis, M. [Laboratorio MDM, CNR-IMM, Via C. Olivetti 2, 20864 Agrate Brianza (MB) (Italy); Mazzeo, G.; Fanciulli, M. [Laboratorio MDM, CNR-IMM, Via C. Olivetti 2, 20864 Agrate Brianza (MB) (Italy); Dipartimento di Scienza dei Materiali, Università di Milano Bicocca, Via Cozzi 53, 20125 Milano (Italy); Prati, E. [Laboratorio MDM, CNR-IMM, Via C. Olivetti 2, 20864 Agrate Brianza (MB) (Italy); Istituto di Fotonica e Nanotecnologie, CNR, Piazza Leonardo da Vinci 32, 20133 Milano (Italy)

2016-03-11

We report on the fabrication and the characterization of a tunable complementary-metal oxide semiconductor (CMOS) system consisting of two quantum dots and a MOS single electron transistor (MOSSET) charge sensor. By exploiting a compact T-shaped design and few gates fabricated by electron beam lithography, the MOSSET senses the charge state of either a single or double quantum dot at 4.2 K. The CMOS compatible fabrication process, the simplified control over the number of quantum dots and the scalable geometry make such architecture exploitable for large scale fabrication of multiple spin-based qubits in circuital quantum information processing. - Highlights: • Charge sensing of tunable, by position and number, quantum dots is demonstrated. • A compact T-shaped design with five gates at a single metalization level is proposed. • The electrometer is a silicon-etched nanowire acting as a disorder tolerant MOSSET.

Pattern graph rewrite systems

Directory of Open Access Journals (Sweden)

Aleks Kissinger

2014-03-01

Full Text Available String diagrams are a powerful tool for reasoning about physical processes, logic circuits, tensor networks, and many other compositional structures. Dixon, Duncan and Kissinger introduced string graphs, which are a combinatoric representations of string diagrams, amenable to automated reasoning about diagrammatic theories via graph rewrite systems. In this extended abstract, we show how the power of such rewrite systems can be greatly extended by introducing pattern graphs, which provide a means of expressing infinite families of rewrite rules where certain marked subgraphs, called !-boxes ("bang boxes", on both sides of a rule can be copied any number of times or removed. After reviewing the string graph formalism, we show how string graphs can be extended to pattern graphs and how pattern graphs and pattern rewrite rules can be instantiated to concrete string graphs and rewrite rules. We then provide examples demonstrating the expressive power of pattern graphs and how they can be applied to study interacting algebraic structures that are central to categorical quantum mechanics.

Classification of locally 2-connected compact metric spaces

DEFF Research Database (Denmark)

Thomassen, Carsten

2005-01-01

The aim of this paper is to prove that, for compact metric spaces which do not contain infinite complete graphs, the (strong) property of being "locally 2-dimensional" is guaranteed just by a (weak) local connectivity condition. Specifically, we prove that a locally 2-connected, compact metric sp...... space M either contains an infinite complete graph or is surface like in the following sense: There exists a unique surface S such that S and M. contain the same finite graphs. Moreover, M is embeddable in S, that is, M is homeomorphic to a subset of S....

The Epstein-Glaser approach to perturbative quantum field theory: graphs and Hopf algebras

International Nuclear Information System (INIS)

Lange, Alexander

2005-01-01

The paper aims at investigating perturbative quantum field theory in the approach of Epstein and Glaser (EG) and, in particular, its formulation in the language of graphs and Hopf algebras (HAs). Various HAs are encountered, each one associated with a special combination of physical concepts such as normalization, localization, pseudounitarity, causal regularization, and renormalization. The algebraic structures, representing the perturbative expansion of the S-matrix, are imposed on operator-valued distributions equipped with appropriate graph indices. Translation invariance ensures the algebras to be analytically well defined and graded total symmetry allows to formulate bialgebras. The algebraic results are given embedded in the corresponding physical framework, covering the two EG versions by Fredenhagen and Scharf that differ with respect to the concrete recursive implementation of causality. Besides, the ultraviolet divergences occurring in Feynman's representation are mathematically reasoned. As a final result, the change of the renormalization scheme in the context of EG is modeled via a HA and interpreted as the EG analog of Kreimer's HA

Compact Gaussian quantum computation by multi-pixel homodyne detection

International Nuclear Information System (INIS)

Ferrini, G; Fabre, C; Treps, N; Gazeau, J P; Coudreau, T

2013-01-01

We study the possibility of producing and detecting continuous variable cluster states in an extremely compact optical setup. This method is based on a multi-pixel homodyne detection system recently demonstrated experimentally, which includes classical data post-processing. It allows the incorporation of the linear optics network, usually employed in standard experiments for the production of cluster states, in the stage of the measurement. After giving an example of cluster state generation by this method, we further study how this procedure can be generalized to perform Gaussian quantum computation. (paper)

Physics and engineering of compact quantum dot-based lasers for biophotonics

CERN Document Server

Rafailov, Edik U

2013-01-01

Written by a team of European experts in the field, this book addresses the physics, the principles, the engineering methods, and the latest developments of efficient and compact ultrafast lasers based on novel quantum-dot structures and devices, as well as their applications in biophotonics. Recommended reading for physicists, engineers, students and lecturers in the fields of photonics, optics, laser physics, optoelectronics, and biophotonics.

Graph-based linear scaling electronic structure theory

Energy Technology Data Exchange (ETDEWEB)

Niklasson, Anders M. N., E-mail: amn@lanl.gov; Negre, Christian F. A.; Cawkwell, Marc J.; Swart, Pieter J.; Germann, Timothy C.; Bock, Nicolas [Theoretical Division, Los Alamos National Laboratory, Los Alamos, New Mexico 87545 (United States); Mniszewski, Susan M.; Mohd-Yusof, Jamal; Wall, Michael E.; Djidjev, Hristo [Computer, Computational, and Statistical Sciences Division, Los Alamos National Laboratory, Los Alamos, New Mexico 87545 (United States); Rubensson, Emanuel H. [Division of Scientific Computing, Department of Information Technology, Uppsala University, Box 337, SE-751 05 Uppsala (Sweden)

2016-06-21

We show how graph theory can be combined with quantum theory to calculate the electronic structure of large complex systems. The graph formalism is general and applicable to a broad range of electronic structure methods and materials, including challenging systems such as biomolecules. The methodology combines well-controlled accuracy, low computational cost, and natural low-communication parallelism. This combination addresses substantial shortcomings of linear scaling electronic structure theory, in particular with respect to quantum-based molecular dynamics simulations.

Renormalization in quantum field theory and the Riemann-Hilbert problem. I. Hopf algebra structure of graphs and the main theorem

International Nuclear Information System (INIS)

Connes, A.; Kreimer, D.

2000-01-01

This paper gives a complete selfcontained proof of our result (1999) showing that renormalization in quantum field theory is a special instance of a general mathematical procedure of extraction of finite values based on the Riemann-Hilbert problem. We shall first show that for any quantum field theory, the combinatorics of Feynman graphs gives rise to a Hopf algebra H which is commutative asan algebra. It is the dual Hopf algebra of the enveloping algebra of a Lie algebra G whose basis is labelled by the one particle irreducible Feynman graphs. The Lie bracket of two such graphs is computed from insertions of one graph in the other and vice versa. The corresponding Lie group G is the group of characters of H. We show then that, using dimensional regularization, the bare (unrenormalized) theory gives rise to a loop γ(z) element of G, z element of C, where C is a small circle of complex dimensions around the integer dimension D of space-time. Our main result is that the renormalized theory is just the evaluation at z=D of the holomorphic part γ + of the Birkhoff decomposition of γ. We begin to analyse the group G and show that it is a semi-direct product of an easily understood abelian group by a highly non-trivial group closely tied up with groups of diffeomorphisms. (orig.)

Winter School on Operator Spaces, Noncommutative Probability and Quantum Groups

CERN Document Server

2017-01-01

Providing an introduction to current research topics in functional analysis and its applications to quantum physics, this book presents three lectures surveying recent progress and open problems.  A special focus is given to the role of symmetry in non-commutative probability, in the theory of quantum groups, and in quantum physics. The first lecture presents the close connection between distributional symmetries and independence properties. The second introduces many structures (graphs, C*-algebras, discrete groups) whose quantum symmetries are much richer than their classical symmetry groups, and describes the associated quantum symmetry groups. The last lecture shows how functional analytic and geometric ideas can be used to detect and to quantify entanglement in high dimensions.  The book will allow graduate students and young researchers to gain a better understanding of free probability, the theory of compact quantum groups, and applications of the theory of Banach spaces to quantum information. The l...

Efficient quantum circuits for Szegedy quantum walks

Science.gov (United States)

Loke, T.; Wang, J. B.

2017-07-01

A major advantage in using Szegedy's formalism over discrete-time and continuous-time quantum walks lies in its ability to define a unitary quantum walk by quantizing a Markov chain on a directed or weighted graph. In this paper, we present a general scheme to construct efficient quantum circuits for Szegedy quantum walks that correspond to classical Markov chains possessing transformational symmetry in the columns of the transition matrix. In particular, the transformational symmetry criteria do not necessarily depend on the sparsity of the transition matrix, so this scheme can be applied to non-sparse Markov chains. Two classes of Markov chains that are amenable to this construction are cyclic permutations and complete bipartite graphs, for which we provide explicit efficient quantum circuit implementations. We also prove that our scheme can be applied to Markov chains formed by a tensor product. We also briefly discuss the implementation of Markov chains based on weighted interdependent networks. In addition, we apply this scheme to construct efficient quantum circuits simulating the Szegedy walks used in the quantum Pagerank algorithm for some classes of non-trivial graphs, providing a necessary tool for experimental demonstration of the quantum Pagerank algorithm.

The Partial Mapping of the Web Graph

Directory of Open Access Journals (Sweden)

Kristina Machova

2009-06-01

Full Text Available The paper presents an approach to partial mapping of a web sub-graph. This sub-graph contains the nearest surroundings of an actual web page. Our work deals with acquiring relevant Hyperlinks of a base web site, generation of adjacency matrix, the nearest distance matrix and matrix of converted distances of Hyperlinks, detection of compactness of web representation, and visualization of its graphical representation. The paper introduces an LWP algorithm – a technique for Hyperlink filtration.  This work attempts to help users with the orientation within the web graph.

Compact quantum dots for single-molecule imaging.

Science.gov (United States)

Smith, Andrew M; Nie, Shuming

2012-10-09

Single-molecule imaging is an important tool for understanding the mechanisms of biomolecular function and for visualizing the spatial and temporal heterogeneity of molecular behaviors that underlie cellular biology (1-4). To image an individual molecule of interest, it is typically conjugated to a fluorescent tag (dye, protein, bead, or quantum dot) and observed with epifluorescence or total internal reflection fluorescence (TIRF) microscopy. While dyes and fluorescent proteins have been the mainstay of fluorescence imaging for decades, their fluorescence is unstable under high photon fluxes necessary to observe individual molecules, yielding only a few seconds of observation before complete loss of signal. Latex beads and dye-labeled beads provide improved signal stability but at the expense of drastically larger hydrodynamic size, which can deleteriously alter the diffusion and behavior of the molecule under study. Quantum dots (QDs) offer a balance between these two problematic regimes. These nanoparticles are composed of semiconductor materials and can be engineered with a hydrodynamically compact size with exceptional resistance to photodegradation (5). Thus in recent years QDs have been instrumental in enabling long-term observation of complex macromolecular behavior on the single molecule level. However these particles have still been found to exhibit impaired diffusion in crowded molecular environments such as the cellular cytoplasm and the neuronal synaptic cleft, where their sizes are still too large (4,6,7). Recently we have engineered the cores and surface coatings of QDs for minimized hydrodynamic size, while balancing offsets to colloidal stability, photostability, brightness, and nonspecific binding that have hindered the utility of compact QDs in the past (8,9). The goal of this article is to demonstrate the synthesis, modification, and characterization of these optimized nanocrystals, composed of an alloyed HgxCd1-xSe core coated with an

Quantum isometry groups

Indian Academy of Sciences (India)

Jyotishman Bhowmick

2015-11-07

Nov 7, 2015 ... Classical. Quantum. Background. Compact Hausdorff space. Unital C∗ algebra. Gelfand-Naimark. Compact Group. Compact Quantum Group. Woronowicz. Group Action. Coaction. Woronowicz. Riemannian manifold. Spectral triple. Connes. Isometry group. Quantum Isometry Group. To be discussed.

On the irreps of the N-extended supersymmetric quantum mechanics and their fusion graphs

International Nuclear Information System (INIS)

Toppan, Francesco.

2006-12-01

In this talk we review the classification of the irreducible representations of the algebra of the N-extended one-dimensional supersymmetric quantum mechanics presented in hep-th/0511274. We answer some issues raised in hep-th/0611060, proving the agreement of the results here contained with those in hep-th/0511274. We further show that the fusion algebra of the 1D N-extended supersymmetric vacua introduced in hep-th/0511274 admits a graphical presentation. The N = 2 graphs are here explicitly presented for the first time. (author)

Compact baby universe model in ten dimension and probability function of quantum gravity

International Nuclear Information System (INIS)

Yan Jun; Hu Shike

1991-01-01

The quantum probability functions are calculated for ten-dimensional compact baby universe model. The authors find that the probability for the Yang-Mills baby universe to undergo a spontaneous compactification down to a four-dimensional spacetime is greater than that to remain in the original homogeneous multidimensional state. Some questions about large-wormhole catastrophe are also discussed

Universal quantum computation by discontinuous quantum walk

International Nuclear Information System (INIS)

Underwood, Michael S.; Feder, David L.

2010-01-01

Quantum walks are the quantum-mechanical analog of random walks, in which a quantum ''walker'' evolves between initial and final states by traversing the edges of a graph, either in discrete steps from node to node or via continuous evolution under the Hamiltonian furnished by the adjacency matrix of the graph. We present a hybrid scheme for universal quantum computation in which a quantum walker takes discrete steps of continuous evolution. This ''discontinuous'' quantum walk employs perfect quantum-state transfer between two nodes of specific subgraphs chosen to implement a universal gate set, thereby ensuring unitary evolution without requiring the introduction of an ancillary coin space. The run time is linear in the number of simulated qubits and gates. The scheme allows multiple runs of the algorithm to be executed almost simultaneously by starting walkers one time step apart.

Isospectral graphs with identical nodal counts

International Nuclear Information System (INIS)

Oren, Idan; Band, Ram

2012-01-01

According to a recent conjecture, isospectral objects have different nodal count sequences (Gnutzmann et al 2005 J. Phys. A: Math. Gen. 38 8921–33). We study generalized Laplacians on discrete graphs, and use them to construct the first non-trivial counterexamples to this conjecture. In addition, these examples demonstrate a surprising connection between isospectral discrete and quantum graphs. (paper)

Compact Interconnection Networks Based on Quantum Dots

Science.gov (United States)

Fijany, Amir; Toomarian, Nikzad; Modarress, Katayoon; Spotnitz, Matthew

2003-01-01

Architectures that would exploit the distinct characteristics of quantum-dot cellular automata (QCA) have been proposed for digital communication networks that connect advanced digital computing circuits. In comparison with networks of wires in conventional very-large-scale integrated (VLSI) circuitry, the networks according to the proposed architectures would be more compact. The proposed architectures would make it possible to implement complex interconnection schemes that are required for some advanced parallel-computing algorithms and that are difficult (and in many cases impractical) to implement in VLSI circuitry. The difficulty of implementation in VLSI and the major potential advantage afforded by QCA were described previously in Implementing Permutation Matrices by Use of Quantum Dots (NPO-20801), NASA Tech Briefs, Vol. 25, No. 10 (October 2001), page 42. To recapitulate: Wherever two wires in a conventional VLSI circuit cross each other and are required not to be in electrical contact with each other, there must be a layer of electrical insulation between them. This, in turn, makes it necessary to resort to a noncoplanar and possibly a multilayer design, which can be complex, expensive, and even impractical. As a result, much of the cost of designing VLSI circuits is associated with minimization of data routing and assignment of layers to minimize crossing of wires. Heretofore, these considerations have impeded the development of VLSI circuitry to implement complex, advanced interconnection schemes. On the other hand, with suitable design and under suitable operating conditions, QCA-based signal paths can be allowed to cross each other in the same plane without adverse effect. In principle, this characteristic could be exploited to design compact, coplanar, simple (relative to VLSI) QCA-based networks to implement complex, advanced interconnection schemes. The proposed architectures require two advances in QCA-based circuitry beyond basic QCA-based binary

Linear game non-contextuality and Bell inequalities—a graph-theoretic approach

International Nuclear Information System (INIS)

Rosicka, M; Ramanathan, R; Gnaciński, P; Horodecki, M; Horodecki, K; Horodecki, P; Severini, S

2016-01-01

We study the classical and quantum values of a class of one- and two-party unique games, that generalizes the well-known XOR games to the case of non-binary outcomes. In the bipartite case the generalized XOR (XOR-d) games we study are a subclass of the well-known linear games. We introduce a ‘constraint graph’ associated to such a game, with the constraints defining the game represented by an edge-coloring of the graph. We use the graph-theoretic characterization to relate the task of finding equivalent games to the notion of signed graphs and switching equivalence from graph theory. We relate the problem of computing the classical value of single-party anti-correlation XOR games to finding the edge bipartization number of a graph, which is known to be MaxSNP hard, and connect the computation of the classical value of XOR-d games to the identification of specific cycles in the graph. We construct an orthogonality graph of the game from the constraint graph and study its Lovász theta number as a general upper bound on the quantum value even in the case of single-party contextual XOR-d games. XOR-d games possess appealing properties for use in device-independent applications such as randomness of the local correlated outcomes in the optimal quantum strategy. We study the possibility of obtaining quantum algebraic violation of these games, and show that no finite XOR-d game possesses the property of pseudo-telepathy leaving the frequently used chained Bell inequalities as the natural candidates for such applications. We also show this lack of pseudo-telepathy for multi-party XOR-type inequalities involving two-body correlation functions. (paper)

Linear game non-contextuality and Bell inequalities—a graph-theoretic approach

Science.gov (United States)

Rosicka, M.; Ramanathan, R.; Gnaciński, P.; Horodecki, K.; Horodecki, M.; Horodecki, P.; Severini, S.

2016-04-01

We study the classical and quantum values of a class of one- and two-party unique games, that generalizes the well-known XOR games to the case of non-binary outcomes. In the bipartite case the generalized XOR (XOR-d) games we study are a subclass of the well-known linear games. We introduce a ‘constraint graph’ associated to such a game, with the constraints defining the game represented by an edge-coloring of the graph. We use the graph-theoretic characterization to relate the task of finding equivalent games to the notion of signed graphs and switching equivalence from graph theory. We relate the problem of computing the classical value of single-party anti-correlation XOR games to finding the edge bipartization number of a graph, which is known to be MaxSNP hard, and connect the computation of the classical value of XOR-d games to the identification of specific cycles in the graph. We construct an orthogonality graph of the game from the constraint graph and study its Lovász theta number as a general upper bound on the quantum value even in the case of single-party contextual XOR-d games. XOR-d games possess appealing properties for use in device-independent applications such as randomness of the local correlated outcomes in the optimal quantum strategy. We study the possibility of obtaining quantum algebraic violation of these games, and show that no finite XOR-d game possesses the property of pseudo-telepathy leaving the frequently used chained Bell inequalities as the natural candidates for such applications. We also show this lack of pseudo-telepathy for multi-party XOR-type inequalities involving two-body correlation functions.

Bell inequalities for the simplest exclusivity graph

OpenAIRE

Sadiq, Muhamad; Badziag, Piotr; Bourennane, Mohamed; Cabello, Adan

2011-01-01

Which is the simplest logical structure for which there is quantum nonlocality? We show that there are only three bipartite Bell inequalities with quantum violation associated with the simplest graph of relationships of exclusivity with a quantum-classical gap. These are the most elementary logical Bell inequalities. We show that the quantum violation of some well-known Bell inequalities is related to them. We test the three Bell inequalities with pairs of polarization-entangled photons and r...

Graphical calculus of volume, inverse volume and Hamiltonian operators in loop quantum gravity

Energy Technology Data Exchange (ETDEWEB)

Yang, Jinsong [Guizhou University, Department of Physics, Guiyang (China); Academia Sinica, Institute of Physics, Taipei (China); Ma, Yongge [Beijing Normal University, Department of Physics, Beijing (China)

2017-04-15

To adopt a practical method to calculate the action of geometrical operators on quantum states is a crucial task in loop quantum gravity. In this paper, the graphical calculus based on the original Brink graphical method is applied to loop quantum gravity along the line of previous work. The graphical method provides a very powerful technique for simplifying complicated calculations. The closed formula of the volume operator and the actions of the Euclidean Hamiltonian constraint operator and the so-called inverse volume operator on spin-network states with trivalent vertices are derived via the graphical method. By employing suitable and non-ambiguous graphs to represent the action of operators as well as the spin-network states, we use the simple rules of transforming graphs to obtain the resulting formula. Comparing with the complicated algebraic derivation in some literature, our procedure is more concise, intuitive and visual. The resulting matrix elements of the volume operator is compact and uniform, fitting for both gauge-invariant and gauge-variant spin-network states. Our results indicate some corrections to the existing results for the Hamiltonian operator and inverse volume operator in the literature. (orig.)

Quantum walks and search algorithms

CERN Document Server

Portugal, Renato

2013-01-01

This book addresses an interesting area of quantum computation called quantum walks, which play an important role in building quantum algorithms, in particular search algorithms. Quantum walks are the quantum analogue of classical random walks. It is known that quantum computers have great power for searching unsorted databases. This power extends to many kinds of searches, particularly to the problem of finding a specific location in a spatial layout, which can be modeled by a graph. The goal is to find a specific node knowing that the particle uses the edges to jump from one node to the next. This book is self-contained with main topics that include: Grover's algorithm, describing its geometrical interpretation and evolution by means of the spectral decomposition of the evolution operater Analytical solutions of quantum walks on important graphs like line, cycles, two-dimensional lattices, and hypercubes using Fourier transforms Quantum walks on generic graphs, describing methods to calculate the limiting d...

Open Graphs and Computational Reasoning

Directory of Open Access Journals (Sweden)

Lucas Dixon

2010-06-01

Full Text Available We present a form of algebraic reasoning for computational objects which are expressed as graphs. Edges describe the flow of data between primitive operations which are represented by vertices. These graphs have an interface made of half-edges (edges which are drawn with an unconnected end and enjoy rich compositional principles by connecting graphs along these half-edges. In particular, this allows equations and rewrite rules to be specified between graphs. Particular computational models can then be encoded as an axiomatic set of such rules. Further rules can be derived graphically and rewriting can be used to simulate the dynamics of a computational system, e.g. evaluating a program on an input. Examples of models which can be formalised in this way include traditional electronic circuits as well as recent categorical accounts of quantum information.

Graph-like continua, augmenting arcs, and Menger's theorem

DEFF Research Database (Denmark)

Thomassen, Carsten; Vella, Antoine

2008-01-01

We show that an adaptation of the augmenting path method for graphs proves Menger's Theorem for wide classes of topological spaces. For example, it holds for locally compact, locally connected, metric spaces, as already known. The method lends itself particularly well to another class of spaces......, connected graph. While closed subsets of such a space behave nicely in that they are compact and locally connected (and therefore locally arcwise connected), the general subspaces do not: They may be connected without being arcwise connected. Nevertheless, they satisfy Menger's Theorem......., namely the locally arcwise connected, hereditarily locally connected, metric spaces. Finally, it applies to every space where every point can be separated from every closed set not containing it by a finite set, in particular to every subspace of the Freudenthal compactification of a locally finite...

The locally connected compact metric spaces embeddable in the plane

DEFF Research Database (Denmark)

Thomassen, Carsten

2004-01-01

We prove that a 2-connected, locally connected, compact topological space M is homeomorphic to a subset of the 2-sphere if and only if M is metrizable and contains none of the Kuratowski graphs K-5 and K-3,K-3.......We prove that a 2-connected, locally connected, compact topological space M is homeomorphic to a subset of the 2-sphere if and only if M is metrizable and contains none of the Kuratowski graphs K-5 and K-3,K-3....

Two-colorable graph states with maximal Schmidt measure

International Nuclear Information System (INIS)

Severini, Simone

2006-01-01

The Schmidt measure was introduced by Eisert and Briegel for quantifying the degree of entanglement of multipartite quantum systems [J. Eisert, H.-J. Briegel, Phys. Rev. A 64 (2001) 22306]. For two-colorable graph states, the Schmidt measure is related to the spectrum of the associated graph. We observe that almost all two-colorable graph states have maximal Schmidt measure and we construct specific examples. By making appeal to a result of Ehrenfeucht et al. [A. Ehrenfeucht, T. Harju, G. Rozenberg, Discrete Math. 278 (2004) 45], we point out that the graph operations called local complementation and switching form a transitive group acting on the set of all graph states of a given dimension

The graph representation approach to topological field theory in 2 + 1 dimensions

International Nuclear Information System (INIS)

Martin, S.P.

1991-02-01

An alternative definition of topological quantum field theory in 2+1 dimensions is discussed. The fundamental objects in this approach are not gauge fields as in the usual approach, but non-local observables associated with graphs. The classical theory of graphs is defined by postulating a simple diagrammatic rule for computing the Poisson bracket of any two graphs. The theory is quantized by exhibiting a quantum deformation of the classical Poisson bracket algebra, which is realized as a commutator algebra on a Hilbert space of states. The wavefunctions in this ''graph representation'' approach are functionals on an appropriate set of graphs. This is in contrast to the usual ''connection representation'' approach in which the theory is defined in terms of a gauge field and the wavefunctions are functionals on the space of flat spatial connections modulo gauge transformations

Quantum symmetries of classical spaces

OpenAIRE

Bhowmick, Jyotishman; Goswami, Debashish; Roy, Subrata Shyam

2009-01-01

We give a general scheme for constructing faithful actions of genuine (noncommutative as $C^*$ algebra) compact quantum groups on classical topological spaces. Using this, we show that: (i) a compact connected classical space can have a faithful action by a genuine compact quantum group, and (ii) there exists a spectral triple on a classical connected compact space for which the quantum group of orientation and volume preserving isometries (in the sense of \\cite{qorient}) is a genuine quantum...

Transformation of UML models to CSP : a case study for graph transformation tools

NARCIS (Netherlands)

Varró, D.; Asztalos, M.; Bisztray, D.; Boronat, A.; Dang, D.; Geiß, R.; Greenyer, J.; Van Gorp, P.M.E.; Kniemeyer, O.; Narayanan, A.; Rencis, E.; Weinell, E.; Schürr, A.; Nagl, M.; Zündorf, A.

2008-01-01

Graph transformation provides an intuitive mechanism for capturing model transformations. In the current paper, we investigate and compare various graph transformation tools using a compact practical model transformation case study carried out as part of the AGTIVE 2007 Tool Contest [22]. The aim of

A General Approximation of Quantum Graph Vertex Couplings by Scaled Schrodinger Operators on Thin Branched Manifolds

Czech Academy of Sciences Publication Activity Database

Exner, Pavel; Post, O.

2013-01-01

Roč. 322, č. 1 (2013), s. 207-227 ISSN 0010-3616 R&D Projects: GA ČR GAP203/11/0701; GA MŠk LC06002 Institutional support: RVO:61389005 Keywords : quantum graph * vertex coupling * tubular network * approximation Subject RIV: BE - Theoretical Physics Impact factor: 1.901, year: 2013 http://download.springer.com/static/pdf/685/art%253A10.1007%252Fs00220-013-1699-9.pdf?auth66=1379859821_26f2df9c1c7e0997b290a90ec2fdfc7e&ext=.pdf

A function space from a compact metrizable space to a dendrite with the hypo-graph topology

Directory of Open Access Journals (Sweden)

Yang Hanbiao

2015-03-01

Full Text Available Let X be an infinite compact metrizable space having only a finite number of isolated points and Y be a non-degenerate dendrite with a distinguished end point v. For each continuous map ƒ : X → Y , we define the hypo-graph ↓vƒ = ∪ x∈X {x} × [v, ƒ (x], where [v, ƒ (x] is the unique arc from v to ƒ (x in Y . Then we can regard ↓v C(X, Y = {↓vƒ | ƒ : X → Y is continuous} as the subspace of the hyperspace Cld(X × Y of nonempty closed sets in X × Y endowed with the Vietoris topology. Let be the closure of ↓v C(X, Y in Cld(X ×Y . In this paper, we shall prove that the pair , ↓v C(X, Y is homeomorphic to (Q, c0, where Q = Iℕ is the Hilbert cube and c0 = {(xi i∈ℕ ∈ Q | limi→∞xi = 0}.

A quantum kinematics for asymptotically flat gravity

Science.gov (United States)

Campiglia, Miguel; Varadarajan, Madhavan

2015-07-01

We construct a quantum kinematics for asymptotically flat gravity based on the Koslowski-Sahlmann (KS) representation. The KS representation is a generalization of the representation underlying loop quantum gravity (LQG) which supports, in addition to the usual LQG operators, the action of ‘background exponential operators’, which are connection dependent operators labelled by ‘background’ su(2) electric fields. KS states have, in addition to the LQG state label corresponding to one dimensional excitations of the triad, a label corresponding to a ‘background’ electric field that describes three dimensional excitations of the triad. Asymptotic behaviour in quantum theory is controlled through asymptotic conditions on the background electric fields that label the states and the background electric fields that label the operators. Asymptotic conditions on the triad are imposed as conditions on the background electric field state label while confining the LQG spin net graph labels to compact sets. We show that KS states can be realised as wave functions on a quantum configuration space of generalized connections and that the asymptotic behaviour of each such generalized connection is determined by that of the background electric fields which label the background exponential operators. Similar to the spatially compact case, the Gauss law and diffeomorphism constraints are then imposed through group averaging techniques to obtain a large sector of gauge invariant states. It is shown that this sector supports a unitary action of the group of asymptotic rotations and translations and that, as anticipated by Friedman and Sorkin, for appropriate spatial topology, this sector contains states that display fermionic behaviour under 2π rotations.

Time- and Cost-Optimal Parallel Algorithms for the Dominance and Visibility Graphs

Directory of Open Access Journals (Sweden)

D. Bhagavathi

1996-01-01

Full Text Available The compaction step of integrated circuit design motivates associating several kinds of graphs with a collection of non-overlapping rectangles in the plane. These graphs are intended to capture various visibility relations amongst the rectangles in the collection. The contribution of this paper is to propose time- and cost-optimal algorithms to construct two such graphs, namely, the dominance graph (DG, for short and the visibility graph (VG, for short. Specifically, we show that with a collection of n non-overlapping rectangles as input, both these structures can be constructed in θ(log n time using n processors in the CREW model.

Optical generation of matter qubit graph states

International Nuclear Information System (INIS)

Benjamin, S C; Eisert, J; Stace, T M

2005-01-01

We present a scheme for rapidly entangling matter qubits in order to create graph states for one-way quantum computing. The qubits can be simple three-level systems in separate cavities. Coupling involves only local fields and a static (unswitched) linear optics network. Fusion of graph-state sections occurs with, in principle, zero probability of damaging the nascent graph state. We avoid the finite thresholds of other schemes by operating on two entangled pairs, so that each generates exactly one photon. We do not require the relatively slow single qubit local flips to be applied during the growth phase: growth of the graph state can then become a purely optical process. The scheme naturally generates graph states with vertices of high degree and so is easily able to construct minimal graph states, with consequent resource savings. The most efficient approach will be to create new graph-state edges even as qubits elsewhere are measured, in a 'just in time' approach. An error analysis indicates that the scheme is relatively robust against imperfections in the apparatus

RT-Symmetric Laplace Operators on Star Graphs: Real Spectrum and Self-Adjointness

Directory of Open Access Journals (Sweden)

Maria Astudillo

2015-01-01

Full Text Available How ideas of PT-symmetric quantum mechanics can be applied to quantum graphs is analyzed, in particular to the star graph. The class of rotationally symmetric vertex conditions is analyzed. It is shown that all such conditions can effectively be described by circulant matrices: real in the case of odd number of edges and complex having particular block structure in the even case. Spectral properties of the corresponding operators are discussed.

[A retrieval method of drug molecules based on graph collapsing].

Science.gov (United States)

Qu, J W; Lv, X Q; Liu, Z M; Liao, Y; Sun, P H; Wang, B; Tang, Z

2018-04-18

To establish a compact and efficient hypergraph representation and a graph-similarity-based retrieval method of molecules to achieve effective and efficient medicine information retrieval. Chemical structural formula (CSF) was a primary search target as a unique and precise identifier for each compound at the molecular level in the research field of medicine information retrieval. To retrieve medicine information effectively and efficiently, a complete workflow of the graph-based CSF retrieval system was introduced. This system accepted the photos taken from smartphones and the sketches drawn on tablet personal computers as CSF inputs, and formalized the CSFs with the corresponding graphs. Then this paper proposed a compact and efficient hypergraph representation for molecules on the basis of analyzing factors that directly affected the efficiency of graph matching. According to the characteristics of CSFs, a hierarchical collapsing method combining graph isomorphism and frequent subgraph mining was adopted. There was yet a fundamental challenge, subgraph overlapping during the collapsing procedure, which hindered the method from establishing the correct compact hypergraph of an original CSF graph. Therefore, a graph-isomorphism-based algorithm was proposed to select dominant acyclic subgraphs on the basis of overlapping analysis. Finally, the spatial similarity among graphical CSFs was evaluated by multi-dimensional measures of similarity. To evaluate the performance of the proposed method, the proposed system was firstly compared with Wikipedia Chemical Structure Explorer (WCSE), the state-of-the-art system that allowed CSF similarity searching within Wikipedia molecules dataset, on retrieval accuracy. The system achieved higher values on mean average precision, discounted cumulative gain, rank-biased precision, and expected reciprocal rank than WCSE from the top-2 to the top-10 retrieved results. Specifically, the system achieved 10%, 1.41, 6.42%, and 1

Multigraph approach to quantum non-locality

International Nuclear Information System (INIS)

Rabelo, Rafael; Duarte, Cristhiano; Cunha, Marcelo Terra; López-Tarrida, Antonio J; Cabello, Adán

2014-01-01

Non-contextuality (NC) and Bell inequalities can be expressed as bounds Ω for positive linear combinations S of probabilities of events, S⩽Ω. Exclusive events in S can be represented as adjacent vertices of a graph called the exclusivity graph of S. In the case that events correspond to the outcomes of quantum projective measurements, quantum probabilities are intimately related to the Grötschel–Lovász–Schrijver theta body of the exclusivity graph. Then, one can easily compute an upper bound to the maximum quantum violation of any NC or Bell inequality by optimizing S over the theta body and calculating the Lovász number of the corresponding exclusivity graph. In some cases, this upper bound is tight and gives the exact maximum quantum violation. However, in general, this is not the case. The reason is that the exclusivity graph does not distinguish among the different ways exclusivity can occur in Bell-inequality (and similar) scenarios. An interesting question is whether there is a graph-theoretical concept which accounts for this problem. Here we show that, for any given N-partite Bell inequality, an edge-coloured multigraph composed of N single-colour graphs can be used to encode the relationships of exclusivity between each party's parts of the events. Then, the maximum quantum violation of the Bell inequality is exactly given by a refinement of the Lovász number that applies to these edge-coloured multigraphs. We show how to calculate upper bounds for this number using a hierarchy of semi-definite programs and calculate upper bounds for I 3 , I 3322 and the three bipartite Bell inequalities whose exclusivity graph is a pentagon. The multigraph-theoretical approach introduced here may remove some obstacles in the program of explaining quantum correlations from first principles. This article is part of a special issue of Journal of Physics A: Mathematical and Theoretical devoted to ‘50 years of Bell’s theorem’. (paper)

Generalized graph manifolds and their effective recognition

International Nuclear Information System (INIS)

Matveev, S V

1998-01-01

A generalized graph manifold is a three-dimensional manifold obtained by gluing together elementary blocks, each of which is either a Seifert manifold or contains no essential tori or annuli. By a well-known result on torus decomposition each compact three-dimensional manifold with boundary that is either empty or consists of tori has a canonical representation as a generalized graph manifold. A short simple proof of the existence of a canonical representation is presented and a (partial) algorithm for its construction is described. A simple hyperbolicity test for blocks that are not Seifert manifolds is also presented

Quantum Graphical Models and Belief Propagation

International Nuclear Information System (INIS)

Leifer, M.S.; Poulin, D.

2008-01-01

Belief Propagation algorithms acting on Graphical Models of classical probability distributions, such as Markov Networks, Factor Graphs and Bayesian Networks, are amongst the most powerful known methods for deriving probabilistic inferences amongst large numbers of random variables. This paper presents a generalization of these concepts and methods to the quantum case, based on the idea that quantum theory can be thought of as a noncommutative, operator-valued, generalization of classical probability theory. Some novel characterizations of quantum conditional independence are derived, and definitions of Quantum n-Bifactor Networks, Markov Networks, Factor Graphs and Bayesian Networks are proposed. The structure of Quantum Markov Networks is investigated and some partial characterization results are obtained, along the lines of the Hammersley-Clifford theorem. A Quantum Belief Propagation algorithm is presented and is shown to converge on 1-Bifactor Networks and Markov Networks when the underlying graph is a tree. The use of Quantum Belief Propagation as a heuristic algorithm in cases where it is not known to converge is discussed. Applications to decoding quantum error correcting codes and to the simulation of many-body quantum systems are described

Quantum social networks

International Nuclear Information System (INIS)

Cabello, Adán; López-Tarrida, Antonio J; Danielsen, Lars Eirik; Portillo, José R

2012-01-01

We introduce a physical approach to social networks (SNs) in which each actor is characterized by a yes–no test on a physical system. This allows us to consider SNs beyond those originated by interactions based on pre-existing properties, as in a classical SN (CSN). As an example of SNs beyond CSNs, we introduce quantum SNs (QSNs) in which actor i is characterized by a test of whether or not the system is in a quantum state |ψ i 〉. We show that QSNs outperform CSNs for a certain task and some graphs. We identify the simplest of these graphs and show that graphs in which QSNs outperform CSNs are increasingly frequent as the number of vertices increases. We also discuss more general SNs and identify the simplest graphs in which QSNs cannot be outperformed. (paper)

Topology-preserving quantum deformation with non-numerical parameter

Science.gov (United States)

Aukhadiev, Marat; Grigoryan, Suren; Lipacheva, Ekaterina

2013-11-01

We introduce a class of compact quantum semigroups, that we call semigroup deformations of compact Abelian qroups. These objects arise from reduced semigroup -algebras, the generalization of the Toeplitz algebra. We study quantum subgroups, quantum projective spaces and quantum quotient groups for such objects, and show that the group is contained as a compact quantum subgroup in the deformation of itself. The connection with the weak Hopf algebra notion is described. We give a grading on the -algebra of the compact quantum semigroups constructed.

Embedded graph invariants in Chern-Simons theory

International Nuclear Information System (INIS)

Major, Seth A.

1999-01-01

Chern-Simons gauge theory, since its inception as a topological quantum field theory, has proved to be a rich source of understanding for knot invariants. In this work the theory is used to explore the definition of the expectation value of a network of Wilson lines -- an embedded graph invariant. Using a generalization of the variational method, lowest-order results for invariants for graphs of arbitrary valence and general vertex tangent space structure are derived. Gauge invariant operators are introduced. Higher order results are found. The method used here provides a Vassiliev-type definition of graph invariants which depend on both the embedding of the graph and the group structure of the gauge theory. It is found that one need not frame individual vertices. However, without a global projection of the graph there is an ambiguity in the relation of the decomposition of distinct vertices. It is suggested that framing may be seen as arising from this ambiguity -- as a way of relating frames at distinct vertices

Entanglement entropy in the quantum networks of a coupled quantum harmonic oscillator

International Nuclear Information System (INIS)

Jafarizadeh, M A; Nami, S; Eghbalifam, F

2015-01-01

We investigate the entanglement of the ground state in the quantum networks that their nodes are considered as quantum harmonic oscillators. To this aim, the Schmidt numbers and entanglement entropy between two arbitrary partitions of a network are calculated.In partitioning an arbitrary graph into two parts there are some nodes in each part which are not connected to the nodes of the other part. So, these nodes of each part can be in distinct subsets. Therefore, the graph is separated into four subsets. The nodes of the first and last subsets are those which are not connected to the nodes of the other part. In theorem 1, by using the generalized Schur complement method in these four subsets, we prove that all the graphs whose connections between the two alternative subsets are complete, have the same entropy. A large number of graphs satisfy this theorem. Then the entanglement entropy in the limit of the large coupling and large size of the system is investigated in these graphs. Also, the asymptotic behaviors of the Schmidt numbers and entanglement entropy in the limit of infinite coupling are shown.One important quantity about partitioning is the conductance of the graph. The conductance of the graph is considered in various graphs. In these graphs we compare the conductance of the graph and the entanglement entropy. (paper)

Pseudo-orbit approach to trajectories of resonances in quantum graphs with general vertex coupling: Fermi rule and high-energy asymptotics

Czech Academy of Sciences Publication Activity Database

Exner, Pavel; Lipovský, J.

2017-01-01

Roč. 58, č. 4 (2017), č. článku 042101. ISSN 0022-2488 R&D Projects: GA ČR GA17-01706S Institutional support: RVO:61389005 Keywords : self-adjoint coupling * high-energy regime * resonances in quantum graphs Subject RIV: BE - Theoretical Physics OBOR OECD: Atomic, molecular and chemical physics ( physics of atoms and molecules including collision, interaction with radiation, magnetic resonances, Mössbauer effect) Impact factor: 1.077, year: 2016

Quantum walks of two interacting particles on percolation graphs

Science.gov (United States)

Siloi, Ilaria; Benedetti, Claudia; Piccinini, Enrico; Paris, Matteo G. A.; Bordone, Paolo

2017-10-01

We address the dynamics of two indistinguishable interacting particles moving on a dynamical percolation graph, i.e., a graph where the edges are independent random telegraph processes whose values jump between 0 and 1, thus mimicking percolation. The interplay between the particle interaction strength, initial state and the percolation rate determine different dynamical regimes for the walkers. We show that, whenever the walkers are initially localised within the interaction range, fast noise enhances the particle spread compared to the noiseless case.

Modeling of tethered satellite formations using graph theory

DEFF Research Database (Denmark)

Larsen, Martin Birkelund; Smith, Roy S; Blanke, Mogens

2011-01-01

satellite formation and proposes a method to deduce the equations of motion for the attitude dynamics of the formation in a compact form. The use of graph theory and Lagrange mechanics together allows a broad class of formations to be described using the same framework. A method is stated for finding...

Generating loop graphs via Hopf algebra in quantum field theory

International Nuclear Information System (INIS)

Mestre, Angela; Oeckl, Robert

2006-01-01

We use the Hopf algebra structure of the time-ordered algebra of field operators to generate all connected weighted Feynman graphs in a recursive and efficient manner. The algebraic representation of the graphs is such that they can be evaluated directly as contributions to the connected n-point functions. The recursion proceeds by loop order and vertex number

Graph theory and the Virasoro master equation

International Nuclear Information System (INIS)

Obers, N.A.J.

1991-01-01

A brief history of affine Lie algebra, the Virasoro algebra and its culmination in the Virasoro master equation is given. By studying ansaetze of the master equation, the author obtains exact solutions and gains insight in the structure of large slices of affine-Virasoro space. He finds an isomorphism between the constructions in the ansatz SO(n) diag , which is a set of unitary, generically irrational affine-Virasoro constructions on SO(n), and the unlabeled graphs of order n. On the one hand, the conformal constructions, are classified by the graphs, while, conversely, a group-theoretic and conformal field-theoretic identification is obtained for every graph of graph theory. He also defines a class of magic Lie group bases in which the Virasoro master equation admits a simple metric ansatz {g metric }, whose structure is visible in the high-level expansion. When a magic basis is real on compact g, the corresponding g metric is a large system of unitary, generically irrational conformal field theories. Examples in this class include the graph-theory ansatz SO(n) diag in the Cartesian basis of SO(n), and the ansatz SU(n) metric in the Pauli-like basis of SU(n). Finally, he defines the 'sine-area graphs' of SU(n), which label the conformal field theories of SU(n) metric , and he notes that, in similar fashion, each magic basis of g defines a generalized graph theory on g which labels the conformal field theories of g metric

Quantum walks with infinite hitting times

International Nuclear Information System (INIS)

Krovi, Hari; Brun, Todd A.

2006-01-01

Hitting times are the average time it takes a walk to reach a given final vertex from a given starting vertex. The hitting time for a classical random walk on a connected graph will always be finite. We show that, by contrast, quantum walks can have infinite hitting times for some initial states. We seek criteria to determine if a given walk on a graph will have infinite hitting times, and find a sufficient condition, which for discrete time quantum walks is that the degeneracy of the evolution operator be greater than the degree of the graph. The set of initial states which give an infinite hitting time form a subspace. The phenomenon of infinite hitting times is in general a consequence of the symmetry of the graph and its automorphism group. Using the irreducible representations of the automorphism group, we derive conditions such that quantum walks defined on this graph must have infinite hitting times for some initial states. In the case of the discrete walk, if this condition is satisfied the walk will have infinite hitting times for any choice of a coin operator, and we give a class of graphs with infinite hitting times for any choice of coin. Hitting times are not very well defined for continuous time quantum walks, but we show that the idea of infinite hitting-time walks naturally extends to the continuous time case as well

Quantum Bio-Informatics:From Quantum Information to Bio-Informatics

CERN Document Server

Freudenberg, W; Ohya, M

2008-01-01

The purpose of this volume is examine bio-informatics and quantum information, which are growing rapidly at present, and to attempt to connect the two, with a view to enumerating and solving the many fundamental problems they entail. To this end, we look for interdisciplinary bridges in mathematics, physics, and information and life sciences. In particular, research into a new paradigm for information science and life science on the basis of quantum theory is emphasized. Sample Chapter(s). Markov Fields on Graphs (599 KB). Contents: Markov Fields on Graphs (L Accardi & H Ohno); Some Aspects of

Path-sum solution of the Weyl quantum walk in 3 + 1 dimensions

Science.gov (United States)

D'Ariano, G. M.; Mosco, N.; Perinotti, P.; Tosini, A.

2017-10-01

We consider the Weyl quantum walk in 3+1 dimensions, that is a discrete-time walk describing a particle with two internal degrees of freedom moving on a Cayley graph of the group , which in an appropriate regime evolves according to Weyl's equation. The Weyl quantum walk was recently derived as the unique unitary evolution on a Cayley graph of that is homogeneous and isotropic. The general solution of the quantum walk evolution is provided here in the position representation, by the analytical expression of the propagator, i.e. transition amplitude from a node of the graph to another node in a finite number of steps. The quantum nature of the walk manifests itself in the interference of the paths on the graph joining the given nodes. The solution is based on the binary encoding of the admissible paths on the graph and on the semigroup structure of the walk transition matrices. This article is part of the themed issue `Second quantum revolution: foundational questions'.

Symmetries of quantum spaces. Subgroups and quotient spaces of quantum SU(2) and SO(3) groups

International Nuclear Information System (INIS)

Podles, P.

1995-01-01

We prove that each action of a compact matrix quantum group on a compact quantum space can be decomposed into irreducible representations of the group. We give the formula for the corresponding multiplicities in the case of the quotient quantum spaces. We describe the subgroups and the quotient spaces of quantum SU(2) and SO(3) groups. (orig.)

Homology groups for particles on one-connected graphs

Science.gov (United States)

MaciÄ Żek, Tomasz; Sawicki, Adam

2017-06-01

We present a mathematical framework for describing the topology of configuration spaces for particles on one-connected graphs. In particular, we compute the homology groups over integers for different classes of one-connected graphs. Our approach is based on some fundamental combinatorial properties of the configuration spaces, Mayer-Vietoris sequences for different parts of configuration spaces, and some limited use of discrete Morse theory. As one of the results, we derive the closed-form formulae for ranks of the homology groups for indistinguishable particles on tree graphs. We also give a detailed discussion of the second homology group of the configuration space of both distinguishable and indistinguishable particles. Our motivation is the search for new kinds of quantum statistics.

A graph with fractional revival

Science.gov (United States)

Bernard, Pierre-Antoine; Chan, Ada; Loranger, Érika; Tamon, Christino; Vinet, Luc

2018-02-01

An example of a graph that admits balanced fractional revival between antipodes is presented. It is obtained by establishing the correspondence between the quantum walk on a hypercube where the opposite vertices across the diagonals of each face are connected and, the coherent transport of single excitations in the extension of the Krawtchouk spin chain with next-to-nearest neighbour interactions.

The signed permutation group on Feynman graphs

Energy Technology Data Exchange (ETDEWEB)

Purkart, Julian, E-mail: purkart@physik.hu-berlin.de [Institute of Physics, Humboldt University, D-12489 Berlin (Germany)

2016-08-15

The Feynman rules assign to every graph an integral which can be written as a function of a scaling parameter L. Assuming L for the process under consideration is very small, so that contributions to the renormalization group are small, we can expand the integral and only consider the lowest orders in the scaling. The aim of this article is to determine specific combinations of graphs in a scalar quantum field theory that lead to a remarkable simplification of the first non-trivial term in the perturbation series. It will be seen that the result is independent of the renormalization scheme and the scattering angles. To achieve that goal we will utilize the parametric representation of scalar Feynman integrals as well as the Hopf algebraic structure of the Feynman graphs under consideration. Moreover, we will present a formula which reduces the effort of determining the first-order term in the perturbation series for the specific combination of graphs to a minimum.

Quantum states and their marginals. From multipartite entanglement to quantum error-correcting codes

International Nuclear Information System (INIS)

Huber, Felix Michael

2017-01-01

At the heart of the curious phenomenon of quantum entanglement lies the relation between the whole and its parts. In my thesis, I explore different aspects of this theme in the multipartite setting by drawing connections to concepts from statistics, graph theory, and quantum error-correcting codes: first, I address the case when joint quantum states are determined by their few-body parts and by Jaynes' maximum entropy principle. This can be seen as an extension of the notion of entanglement, with less complex states already being determined by their few-body marginals. Second, I address the conditions for certain highly entangled multipartite states to exist. In particular, I present the solution of a long-standing open problem concerning the existence of an absolutely maximally entangled state on seven qubits. This sheds light on the algebraic properties of pure quantum states, and on the conditions that constrain the sharing of entanglement amongst multiple particles. Third, I investigate Ulam's graph reconstruction problems in the quantum setting, and obtain legitimacy conditions of a set of states to be the reductions of a joint graph state. Lastly, I apply and extend the weight enumerator machinery from quantum error correction to investigate the existence of codes and highly entangled states in higher dimensions. This clarifies the physical interpretation of the weight enumerators and of the quantum MacWilliams identity, leading to novel applications in multipartite entanglement.

Infinite Random Graphs as Statistical Mechanical Models

DEFF Research Database (Denmark)

Durhuus, Bergfinnur Jøgvan; Napolitano, George Maria

2011-01-01

We discuss two examples of infinite random graphs obtained as limits of finite statistical mechanical systems: a model of two-dimensional dis-cretized quantum gravity defined in terms of causal triangulated surfaces, and the Ising model on generic random trees. For the former model we describe a ...

Compact Quantum Random Number Generator with Silicon Nanocrystals Light Emitting Device Coupled to a Silicon Photomultiplier

Science.gov (United States)

Bisadi, Zahra; Acerbi, Fabio; Fontana, Giorgio; Zorzi, Nicola; Piemonte, Claudio; Pucker, Georg; Pavesi, Lorenzo

2018-02-01

A small-sized photonic quantum random number generator, easy to be implemented in small electronic devices for secure data encryption and other applications, is highly demanding nowadays. Here, we propose a compact configuration with Silicon nanocrystals large area light emitting device (LED) coupled to a Silicon photomultiplier to generate random numbers. The random number generation methodology is based on the photon arrival time and is robust against the non-idealities of the detector and the source of quantum entropy. The raw data show high quality of randomness and pass all the statistical tests in national institute of standards and technology tests (NIST) suite without a post-processing algorithm. The highest bit rate is 0.5 Mbps with the efficiency of 4 bits per detected photon.

EXAMPLES OF QUANTUM HOLONOMY WITH TOPOLOGY CHANGES

Directory of Open Access Journals (Sweden)

Taksu Cheon

2013-10-01

Full Text Available We study a family of closed quantum graphs described by one singular vertex of order n = 4. By suitable choice of the parameters specifying the singular vertex, we can construct a closed path in the parameter space that physically corresponds to the smooth interpolation of different topologies - a ring, separate two lines, separate two rings, two rings with a contact point. We find that the spectrum of a quantum particle on this family of graphs shows quantum holonomy.

Reconstructing Topological Graphs and Continua

OpenAIRE

Gartside, Paul; Pitz, Max F.; Suabedissen, Rolf

2015-01-01

The deck of a topological space $X$ is the set $\\mathcal{D}(X)=\\{[X \\setminus \\{x\\}] \\colon x \\in X\\}$, where $[Z]$ denotes the homeomorphism class of $Z$. A space $X$ is topologically reconstructible if whenever $\\mathcal{D}(X)=\\mathcal{D}(Y)$ then $X$ is homeomorphic to $Y$. It is shown that all metrizable compact connected spaces are reconstructible. It follows that all finite graphs, when viewed as a 1-dimensional cell-complex, are reconstructible in the topological sense, and more genera...

A Rout to Protect Quantum Gates constructed via quantum walks from Noises.

Science.gov (United States)

Du, Yi-Mu; Lu, Li-Hua; Li, You-Quan

2018-05-08

The continuous-time quantum walk on a one-dimensional graph of odd number of sites with an on-site potential at the center is studied. We show that such a quantum-walk system can construct an X-gate of a single qubit as well as a control gate for two qubits, when the potential is much larger than the hopping strength. We investigate the decoherence effect and find that the coherence time can be enhanced by either increasing the number of sites on the graph or the ratio of the potential to the hopping strength, which is expected to motivate the design of the quantum gate with long coherence time. We also suggest several experimental proposals to realize such a system.

Hybrid quantum computation

International Nuclear Information System (INIS)

Sehrawat, Arun; Englert, Berthold-Georg; Zemann, Daniel

2011-01-01

We present a hybrid model of the unitary-evolution-based quantum computation model and the measurement-based quantum computation model. In the hybrid model, part of a quantum circuit is simulated by unitary evolution and the rest by measurements on star graph states, thereby combining the advantages of the two standard quantum computation models. In the hybrid model, a complicated unitary gate under simulation is decomposed in terms of a sequence of single-qubit operations, the controlled-z gates, and multiqubit rotations around the z axis. Every single-qubit and the controlled-z gate are realized by a respective unitary evolution, and every multiqubit rotation is executed by a single measurement on a required star graph state. The classical information processing in our model requires only an information flow vector and propagation matrices. We provide the implementation of multicontrol gates in the hybrid model. They are very useful for implementing Grover's search algorithm, which is studied as an illustrative example.

Quantum computing with incoherent resources and quantum jumps.

Science.gov (United States)

Santos, M F; Cunha, M Terra; Chaves, R; Carvalho, A R R

2012-04-27

Spontaneous emission and the inelastic scattering of photons are two natural processes usually associated with decoherence and the reduction in the capacity to process quantum information. Here we show that, when suitably detected, these photons are sufficient to build all the fundamental blocks needed to perform quantum computation in the emitting qubits while protecting them from deleterious dissipative effects. We exemplify this by showing how to efficiently prepare graph states for the implementation of measurement-based quantum computation.

Scalable quantum computing based on stationary spin qubits in coupled quantum dots inside double-sided optical microcavities.

Science.gov (United States)

Wei, Hai-Rui; Deng, Fu-Guo

2014-12-18

Quantum logic gates are the key elements in quantum computing. Here we investigate the possibility of achieving a scalable and compact quantum computing based on stationary electron-spin qubits, by using the giant optical circular birefringence induced by quantum-dot spins in double-sided optical microcavities as a result of cavity quantum electrodynamics. We design the compact quantum circuits for implementing universal and deterministic quantum gates for electron-spin systems, including the two-qubit CNOT gate and the three-qubit Toffoli gate. They are compact and economic, and they do not require additional electron-spin qubits. Moreover, our devices have good scalability and are attractive as they both are based on solid-state quantum systems and the qubits are stationary. They are feasible with the current experimental technology, and both high fidelity and high efficiency can be achieved when the ratio of the side leakage to the cavity decay is low.

Compact Quantum Random Number Generator with Silicon Nanocrystals Light Emitting Device Coupled to a Silicon Photomultiplier

Directory of Open Access Journals (Sweden)

Zahra Bisadi

2018-02-01

Full Text Available A small-sized photonic quantum random number generator, easy to be implemented in small electronic devices for secure data encryption and other applications, is highly demanding nowadays. Here, we propose a compact configuration with Silicon nanocrystals large area light emitting device (LED coupled to a Silicon photomultiplier to generate random numbers. The random number generation methodology is based on the photon arrival time and is robust against the non-idealities of the detector and the source of quantum entropy. The raw data show high quality of randomness and pass all the statistical tests in national institute of standards and technology tests (NIST suite without a post-processing algorithm. The highest bit rate is 0.5 Mbps with the efficiency of 4 bits per detected photon.

Experimental demonstration of deterministic one-way quantum computing on a NMR quantum computer

OpenAIRE

Ju, Chenyong; Zhu, Jing; Peng, Xinhua; Chong, Bo; Zhou, Xianyi; Du, Jiangfeng

2008-01-01

One-way quantum computing is an important and novel approach to quantum computation. By exploiting the existing particle-particle interactions, we report the first experimental realization of the complete process of deterministic one-way quantum Deutsch-Josza algorithm in NMR, including graph state preparation, single-qubit measurements and feed-forward corrections. The findings in our experiment may shed light on the future scalable one-way quantum computation.

Bounds for percolation thresholds on directed and undirected graphs

Science.gov (United States)

Hamilton, Kathleen; Pryadko, Leonid

2015-03-01

Percolation theory is an efficient approach to problems with strong disorder, e.g., in quantum or classical transport, composite materials, and diluted magnets. Recently, the growing role of big data in scientific and industrial applications has led to a renewed interest in graph theory as a tool for describing complex connections in various kinds of networks: social, biological, technological, etc. In particular, percolation on graphs has been used to describe internet stability, spread of contagious diseases and computer viruses; related models describe market crashes and viral spread in social networks. We consider site-dependent percolation on directed and undirected graphs, and present several exact bounds for location of the percolation transition in terms of the eigenvalues of matrices associated with graphs, including the adjacency matrix and the Hashimoto matrix used to enumerate non-backtracking walks. These bounds correspond t0 a mean field approximation and become asymptotically exact for graphs with no short cycles. We illustrate this convergence numerically by simulating percolation on several families of graphs with different cycle lengths. This research was supported in part by the NSF Grant PHY-1416578 and by the ARO Grant W911NF-11-1-0027.

Efficient growth of complex graph states via imperfect path erasure

International Nuclear Information System (INIS)

Campbell, Earl T; Fitzsimons, Joseph; Benjamin, Simon C; Kok, Pieter

2007-01-01

Given a suitably large and well connected (complex) graph state, any quantum algorithm can be implemented purely through local measurements on the individual qubits. Measurements can also be used to create the graph state: path erasure techniques allow one to entangle multiple qubits by determining only global properties of the qubits. Here, this powerful approach is extended by demonstrating that even imperfect path erasure can produce the required graph states with high efficiency. By characterizing the degree of error in each path erasure attempt, one can subsume the resulting imperfect entanglement into an extended graph state formalism. The subsequent growth of the improper graph state can be guided, through a series of strategic decisions, in such a way as to bound the growth of the error and eventually yield a high-fidelity graph state. As an implementation of these techniques, we develop an analytic model for atom (or atom-like) qubits in mismatched cavities, under the double-heralding entanglement procedure of Barrett and Kok (2005 Phys. Rev. A 71 060310). Compared to straightforward post-selection techniques our protocol offers a dramatic improvement in growing complex high-fidelity graph states

Quantum speedup in solving the maximal-clique problem

Science.gov (United States)

Chang, Weng-Long; Yu, Qi; Li, Zhaokai; Chen, Jiahui; Peng, Xinhua; Feng, Mang

2018-03-01

The maximal-clique problem, to find the maximally sized clique in a given graph, is classically an NP-complete computational problem, which has potential applications ranging from electrical engineering, computational chemistry, and bioinformatics to social networks. Here we develop a quantum algorithm to solve the maximal-clique problem for any graph G with n vertices with quadratic speedup over its classical counterparts, where the time and spatial complexities are reduced to, respectively, O (√{2n}) and O (n2) . With respect to oracle-related quantum algorithms for the NP-complete problems, we identify our algorithm as optimal. To justify the feasibility of the proposed quantum algorithm, we successfully solve a typical clique problem for a graph G with two vertices and one edge by carrying out a nuclear magnetic resonance experiment involving four qubits.

On the stretch factor of convex Delaunay graphs

Directory of Open Access Journals (Sweden)

Prosenjit Bose

2010-06-01

Full Text Available Let C be a compact and convex set in the plane that contains the origin in its interior, and let S be a finite set of points in the plane. The Delaunay graph DGC(S of S is defined to be the dual of the Voronoi diagram of S with respect to the convex distance function defined by C. We prove that DGC(S is a t-spanner for S, for some constant t that depends only on the shape of the set C. Thus, for any two points p and q in S, the graph DGC(S contains a path between p and q whose Euclidean length is at most t times the Euclidean distance between p and q.

Bipartite quantum states and random complex networks

International Nuclear Information System (INIS)

Garnerone, Silvano; Zanardi, Paolo; Giorda, Paolo

2012-01-01

We introduce a mapping between graphs and pure quantum bipartite states and show that the associated entanglement entropy conveys non-trivial information about the structure of the graph. Our primary goal is to investigate the family of random graphs known as complex networks. In the case of classical random graphs, we derive an analytic expression for the averaged entanglement entropy S-bar while for general complex networks we rely on numerics. For a large number of nodes n we find a scaling S-bar ∼c log n +g e where both the prefactor c and the sub-leading O(1) term g e are characteristic of the different classes of complex networks. In particular, g e encodes topological features of the graphs and is named network topological entropy. Our results suggest that quantum entanglement may provide a powerful tool for the analysis of large complex networks with non-trivial topological properties. (paper)

Spectra of magnetic chain graphs: coupling constant perturbations

Czech Academy of Sciences Publication Activity Database

Exner, Pavel; Manko, S. S.

2015-01-01

Roč. 48, č. 12 (2015), s. 125302 ISSN 1751-8113 R&D Projects: GA ČR(CZ) GA14-06818S Institutional support: RVO:61389005 Keywords : quantum graph * magnetic field * coupling constant perturbation * eigenvalues in gaps * weak coupling Subject RIV: BE - Theoretical Physics Impact factor: 1.933, year: 2015

A combinatorial approach to diffeomorphism invariant quantum gauge theories

International Nuclear Information System (INIS)

Zapata, J.A.

1997-01-01

Quantum gauge theory in the connection representation uses functions of holonomies as configuration observables. Physical observables (gauge and diffeomorphism invariant) are represented in the Hilbert space of physical states; physical states are gauge and diffeomorphism invariant distributions on the space of functions of the holonomies of the edges of a certain family of graphs. Then a family of graphs embedded in the space manifold (satisfying certain properties) induces a representation of the algebra of physical observables. We construct a quantum model from the set of piecewise linear graphs on a piecewise linear manifold, and another manifestly combinatorial model from graphs defined on a sequence of increasingly refined simplicial complexes. Even though the two models are different at the kinematical level, they provide unitarily equivalent representations of the algebra of physical observables in separable Hilbert spaces of physical states (their s-knot basis is countable). Hence, the combinatorial framework is compatible with the usual interpretation of quantum field theory. copyright 1997 American Institute of Physics

Random graph states, maximal flow and Fuss-Catalan distributions

International Nuclear Information System (INIS)

Collins, BenoIt; Nechita, Ion; Zyczkowski, Karol

2010-01-01

For any graph consisting of k vertices and m edges we construct an ensemble of random pure quantum states which describe a system composed of 2m subsystems. Each edge of the graph represents a bipartite, maximally entangled state. Each vertex represents a random unitary matrix generated according to the Haar measure, which describes the coupling between subsystems. Dividing all subsystems into two parts, one may study entanglement with respect to this partition. A general technique to derive an expression for the average entanglement entropy of random pure states associated with a given graph is presented. Our technique relies on Weingarten calculus and flow problems. We analyze the statistical properties of spectra of such random density matrices and show for which cases they are described by the free Poissonian (Marchenko-Pastur) distribution. We derive a discrete family of generalized, Fuss-Catalan distributions and explicitly construct graphs which lead to ensembles of random states characterized by these novel distributions of eigenvalues.

Belief propagation decoding of quantum channels by passing quantum messages

International Nuclear Information System (INIS)

Renes, Joseph M

2017-01-01

The belief propagation (BP) algorithm is a powerful tool in a wide range of disciplines from statistical physics to machine learning to computational biology, and is ubiquitous in decoding classical error-correcting codes. The algorithm works by passing messages between nodes of the factor graph associated with the code and enables efficient decoding of the channel, in some cases even up to the Shannon capacity. Here we construct the first BP algorithm which passes quantum messages on the factor graph and is capable of decoding the classical–quantum channel with pure state outputs. This gives explicit decoding circuits whose number of gates is quadratic in the code length. We also show that this decoder can be modified to work with polar codes for the pure state channel and as part of a decoder for transmitting quantum information over the amplitude damping channel. These represent the first explicit capacity-achieving decoders for non-Pauli channels. (fast track communication)

Belief propagation decoding of quantum channels by passing quantum messages

Science.gov (United States)

Renes, Joseph M.

2017-07-01

The belief propagation (BP) algorithm is a powerful tool in a wide range of disciplines from statistical physics to machine learning to computational biology, and is ubiquitous in decoding classical error-correcting codes. The algorithm works by passing messages between nodes of the factor graph associated with the code and enables efficient decoding of the channel, in some cases even up to the Shannon capacity. Here we construct the first BP algorithm which passes quantum messages on the factor graph and is capable of decoding the classical-quantum channel with pure state outputs. This gives explicit decoding circuits whose number of gates is quadratic in the code length. We also show that this decoder can be modified to work with polar codes for the pure state channel and as part of a decoder for transmitting quantum information over the amplitude damping channel. These represent the first explicit capacity-achieving decoders for non-Pauli channels.

Multiple Kernel Learning for adaptive graph regularized nonnegative matrix factorization

KAUST Repository

Wang, Jim Jing-Yan; AbdulJabbar, Mustafa Abdulmajeed

2012-01-01

Nonnegative Matrix Factorization (NMF) has been continuously evolving in several areas like pattern recognition and information retrieval methods. It factorizes a matrix into a product of 2 low-rank non-negative matrices that will define parts-based, and linear representation of non-negative data. Recently, Graph regularized NMF (GrNMF) is proposed to find a compact representation, which uncovers the hidden semantics and simultaneously respects the intrinsic geometric structure. In GNMF, an affinity graph is constructed from the original data space to encode the geometrical information. In this paper, we propose a novel idea which engages a Multiple Kernel Learning approach into refining the graph structure that reflects the factorization of the matrix and the new data space. The GrNMF is improved by utilizing the graph refined by the kernel learning, and then a novel kernel learning method is introduced under the GrNMF framework. Our approach shows encouraging results of the proposed algorithm in comparison to the state-of-the-art clustering algorithms like NMF, GrNMF, SVD etc.

Towards the map of quantum gravity

Science.gov (United States)

Mielczarek, Jakub; Trześniewski, Tomasz

2018-06-01

In this paper we point out some possible links between different approaches to quantum gravity and theories of the Planck scale physics. In particular, connections between loop quantum gravity, causal dynamical triangulations, Hořava-Lifshitz gravity, asymptotic safety scenario, Quantum Graphity, deformations of relativistic symmetries and nonlinear phase space models are discussed. The main focus is on quantum deformations of the Hypersurface Deformations Algebra and Poincaré algebra, nonlinear structure of phase space, the running dimension of spacetime and nontrivial phase diagram of quantum gravity. We present an attempt to arrange the observed relations in the form of a graph, highlighting different aspects of quantum gravity. The analysis is performed in the spirit of a mind map, which represents the architectural approach to the studied theory, being a natural way to describe the properties of a complex system. We hope that the constructed graphs (maps) will turn out to be helpful in uncovering the global picture of quantum gravity as a particular complex system and serve as a useful guide for the researchers.

Quantum group of isometries in classical and noncommutative geometry

International Nuclear Information System (INIS)

Goswami, D.

2007-04-01

We formulate a quantum generalization of the notion of the group of Riemannian isometries for a compact Riemannian manifold, by introducing a natural notion of smooth and isometric action by a compact quantum group on a classical or noncommutative manifold described by spectral triples, and then proving the existence of a universal object (called the quantum isometry group) in the category of compact quantum groups acting smoothly and isometrically on a given (possibly noncommutative) manifold. Our formulation accommodates spectral triples which are not of type II. We give an explicit description of quantum isometry groups of commutative and noncommutative tori, and in this context, obtain the quantum double torus defined in [7] as the universal quantum group of holomorphic isometries of the noncommutative torus. (author)

Quantum computation: algorithms and implementation in quantum dot devices

Science.gov (United States)

Gamble, John King

In this thesis, we explore several aspects of both the software and hardware of quantum computation. First, we examine the computational power of multi-particle quantum random walks in terms of distinguishing mathematical graphs. We study both interacting and non-interacting multi-particle walks on strongly regular graphs, proving some limitations on distinguishing powers and presenting extensive numerical evidence indicative of interactions providing more distinguishing power. We then study the recently proposed adiabatic quantum algorithm for Google PageRank, and show that it exhibits power-law scaling for realistic WWW-like graphs. Turning to hardware, we next analyze the thermal physics of two nearby 2D electron gas (2DEG), and show that an analogue of the Coulomb drag effect exists for heat transfer. In some distance and temperature, this heat transfer is more significant than phonon dissipation channels. After that, we study the dephasing of two-electron states in a single silicon quantum dot. Specifically, we consider dephasing due to the electron-phonon coupling and charge noise, separately treating orbital and valley excitations. In an ideal system, dephasing due to charge noise is strongly suppressed due to a vanishing dipole moment. However, introduction of disorder or anharmonicity leads to large effective dipole moments, and hence possibly strong dephasing. Building on this work, we next consider more realistic systems, including structural disorder systems. We present experiment and theory, which demonstrate energy levels that vary with quantum dot translation, implying a structurally disordered system. Finally, we turn to the issues of valley mixing and valley-orbit hybridization, which occurs due to atomic-scale disorder at quantum well interfaces. We develop a new theoretical approach to study these effects, which we name the disorder-expansion technique. We demonstrate that this method successfully reproduces atomistic tight-binding techniques

Using Graph and Vertex Entropy to Compare Empirical Graphs with Theoretical Graph Models

Directory of Open Access Journals (Sweden)

Tomasz Kajdanowicz

2016-09-01

Full Text Available Over the years, several theoretical graph generation models have been proposed. Among the most prominent are: the Erdős–Renyi random graph model, Watts–Strogatz small world model, Albert–Barabási preferential attachment model, Price citation model, and many more. Often, researchers working with real-world data are interested in understanding the generative phenomena underlying their empirical graphs. They want to know which of the theoretical graph generation models would most probably generate a particular empirical graph. In other words, they expect some similarity assessment between the empirical graph and graphs artificially created from theoretical graph generation models. Usually, in order to assess the similarity of two graphs, centrality measure distributions are compared. For a theoretical graph model this means comparing the empirical graph to a single realization of a theoretical graph model, where the realization is generated from the given model using an arbitrary set of parameters. The similarity between centrality measure distributions can be measured using standard statistical tests, e.g., the Kolmogorov–Smirnov test of distances between cumulative distributions. However, this approach is both error-prone and leads to incorrect conclusions, as we show in our experiments. Therefore, we propose a new method for graph comparison and type classification by comparing the entropies of centrality measure distributions (degree centrality, betweenness centrality, closeness centrality. We demonstrate that our approach can help assign the empirical graph to the most similar theoretical model using a simple unsupervised learning method.

Feynman graphs and gauge theories for experimental physicists. 2. rev. ed.

International Nuclear Information System (INIS)

Schmueser, P.

1995-01-01

This book is an introduction to the foundations of quantum field theory with special regards to gauge theory. After a general introduction to relativistic wave equations the concept of Feynman graphs is introduced. Then after an introduction to the phenomenology of weak interactions and the principle of gauge invariance the standard model of the electroweak interaction is presented. Finally quantum chromodynamics is described. Every chapter contains exercise problems. (HSI)

Band connectivity for topological quantum chemistry: Band structures as a graph theory problem

Science.gov (United States)

Bradlyn, Barry; Elcoro, L.; Vergniory, M. G.; Cano, Jennifer; Wang, Zhijun; Felser, C.; Aroyo, M. I.; Bernevig, B. Andrei

2018-01-01

The conventional theory of solids is well suited to describing band structures locally near isolated points in momentum space, but struggles to capture the full, global picture necessary for understanding topological phenomena. In part of a recent paper [B. Bradlyn et al., Nature (London) 547, 298 (2017), 10.1038/nature23268], we have introduced the way to overcome this difficulty by formulating the problem of sewing together many disconnected local k .p band structures across the Brillouin zone in terms of graph theory. In this paper, we give the details of our full theoretical construction. We show that crystal symmetries strongly constrain the allowed connectivities of energy bands, and we employ graph theoretic techniques such as graph connectivity to enumerate all the solutions to these constraints. The tools of graph theory allow us to identify disconnected groups of bands in these solutions, and so identify topologically distinct insulating phases.

Foodsheds in Virtual Water Flow Networks: A Spectral Graph Theory Approach

Directory of Open Access Journals (Sweden)

Nina Kshetry

2017-06-01

Full Text Available A foodshed is a geographic area from which a population derives its food supply, but a method to determine boundaries of foodsheds has not been formalized. Drawing on the food–water–energy nexus, we propose a formal network science definition of foodsheds by using data from virtual water flows, i.e., water that is virtually embedded in food. In particular, we use spectral graph partitioning for directed graphs. If foodsheds turn out to be geographically compact, it suggests the food system is local and therefore reduces energy and externality costs of food transport. Using our proposed method we compute foodshed boundaries at the global-scale, and at the national-scale in the case of two of the largest agricultural countries: India and the United States. Based on our determination of foodshed boundaries, we are able to better understand commodity flows and whether foodsheds are contiguous and compact, and other factors that impact environmental sustainability. The formal method we propose may be used more broadly to study commodity flows and their impact on environmental sustainability.

Cantor spectra of magnetic chain graphs

Czech Academy of Sciences Publication Activity Database

Exner, Pavel; Vašata, D.

2017-01-01

Roč. 50, č. 16 (2017), č. článku 165201. ISSN 1751-8113 R&D Projects: GA ČR GA17-01706S Institutional support: RVO:61389005 Keywords : quantum chain graph * magnetic field * almost Mathieu operator * Cantor spectrum Subject RIV: BE - Theoretical Physics OBOR OECD: Atomic, molecular and chemical physics ( physics of atoms and molecules including collision, interaction with radiation, magnetic resonances, Mössbauer effect) Impact factor: 1.857, year: 2016

Quantum simulation of a quantum stochastic walk

Science.gov (United States)

Govia, Luke C. G.; Taketani, Bruno G.; Schuhmacher, Peter K.; Wilhelm, Frank K.

2017-03-01

The study of quantum walks has been shown to have a wide range of applications in areas such as artificial intelligence, the study of biological processes, and quantum transport. The quantum stochastic walk (QSW), which allows for incoherent movement of the walker, and therefore, directionality, is a generalization on the fully coherent quantum walk. While a QSW can always be described in Lindblad formalism, this does not mean that it can be microscopically derived in the standard weak-coupling limit under the Born-Markov approximation. This restricts the class of QSWs that can be experimentally realized in a simple manner. To circumvent this restriction, we introduce a technique to simulate open system evolution on a fully coherent quantum computer, using a quantum trajectories style approach. We apply this technique to a broad class of QSWs, and show that they can be simulated with minimal experimental resources. Our work opens the path towards the experimental realization of QSWs on large graphs with existing quantum technologies.

Optimal Quantum Spatial Search on Random Temporal Networks

Science.gov (United States)

Chakraborty, Shantanav; Novo, Leonardo; Di Giorgio, Serena; Omar, Yasser

2017-12-01

To investigate the performance of quantum information tasks on networks whose topology changes in time, we study the spatial search algorithm by continuous time quantum walk to find a marked node on a random temporal network. We consider a network of n nodes constituted by a time-ordered sequence of Erdös-Rényi random graphs G (n ,p ), where p is the probability that any two given nodes are connected: After every time interval τ , a new graph G (n ,p ) replaces the previous one. We prove analytically that, for any given p , there is always a range of values of τ for which the running time of the algorithm is optimal, i.e., O (√{n }), even when search on the individual static graphs constituting the temporal network is suboptimal. On the other hand, there are regimes of τ where the algorithm is suboptimal even when each of the underlying static graphs are sufficiently connected to perform optimal search on them. From this first study of quantum spatial search on a time-dependent network, it emerges that the nontrivial interplay between temporality and connectivity is key to the algorithmic performance. Moreover, our work can be extended to establish high-fidelity qubit transfer between any two nodes of the network. Overall, our findings show that one can exploit temporality to achieve optimal quantum information tasks on dynamical random networks.

Optimal Quantum Spatial Search on Random Temporal Networks.

Science.gov (United States)

Chakraborty, Shantanav; Novo, Leonardo; Di Giorgio, Serena; Omar, Yasser

2017-12-01

To investigate the performance of quantum information tasks on networks whose topology changes in time, we study the spatial search algorithm by continuous time quantum walk to find a marked node on a random temporal network. We consider a network of n nodes constituted by a time-ordered sequence of Erdös-Rényi random graphs G(n,p), where p is the probability that any two given nodes are connected: After every time interval τ, a new graph G(n,p) replaces the previous one. We prove analytically that, for any given p, there is always a range of values of τ for which the running time of the algorithm is optimal, i.e., O(sqrt[n]), even when search on the individual static graphs constituting the temporal network is suboptimal. On the other hand, there are regimes of τ where the algorithm is suboptimal even when each of the underlying static graphs are sufficiently connected to perform optimal search on them. From this first study of quantum spatial search on a time-dependent network, it emerges that the nontrivial interplay between temporality and connectivity is key to the algorithmic performance. Moreover, our work can be extended to establish high-fidelity qubit transfer between any two nodes of the network. Overall, our findings show that one can exploit temporality to achieve optimal quantum information tasks on dynamical random networks.

Group field theory formulation of 3D quantum gravity coupled to matter fields

International Nuclear Information System (INIS)

Oriti, Daniele; Ryan, James

2006-01-01

We present a new group field theory describing 3D Riemannian quantum gravity coupled to matter fields for any choice of spin and mass. The perturbative expansion of the partition function produces fat graphs coloured with SU(2) algebraic data, from which one can reconstruct at once a three-dimensional simplicial complex representing spacetime and its geometry, like in the Ponzano-Regge formulation of pure 3D quantum gravity, and the Feynman graphs for the matter fields. The model then assigns quantum amplitudes to these fat graphs given by spin foam models for gravity coupled to interacting massive spinning point particles, whose properties we discuss

Investigation of continuous-time quantum walk via modules of Bose-Mesner and Terwilliger algebras

International Nuclear Information System (INIS)

Jafarizadeh, M A; Salimi, S

2006-01-01

The continuous-time quantum walk on the underlying graphs of association schemes has been studied, via the algebraic combinatorics structures of association schemes, namely semi-simple modules of their Bose-Mesner and Terwilliger algebras. It is shown that the Terwilliger algebra stratifies the graph into a (d + 1) disjoint union of strata which is different from the stratification based on distance, except for distance regular graphs. In underlying graphs of association schemes, the probability amplitudes and average probabilities are given in terms of dual eigenvalues of association schemes, such that the amplitudes of observing the continuous-time quantum walk on all sites belonging to a given stratum are the same, therefore there are at most (d + 1) different observing probabilities. The importance of association scheme in continuous-time quantum walk is shown by some worked out examples such as arbitrary finite group association schemes followed by symmetric S n , Dihedral D 2m and cyclic groups. At the end it is shown that the highest irreducible representations of Terwilliger algebras pave the way to use the spectral distributions method of Jafarizadeh and Salimi (2005 Preprint quant-ph/0510174) in studying quantum walk on some rather important graphs called distance regular graphs

Belief propagation and loop series on planar graphs

International Nuclear Information System (INIS)

Chertkov, Michael; Teodorescu, Razvan; Chernyak, Vladimir Y

2008-01-01

We discuss a generic model of Bayesian inference with binary variables defined on edges of a planar graph. The Loop Calculus approach of Chertkov and Chernyak (2006 Phys. Rev. E 73 065102(R) [cond-mat/0601487]; 2006 J. Stat. Mech. P06009 [cond-mat/0603189]) is used to evaluate the resulting series expansion for the partition function. We show that, for planar graphs, truncating the series at single-connected loops reduces, via a map reminiscent of the Fisher transformation (Fisher 1961 Phys. Rev. 124 1664), to evaluating the partition function of the dimer-matching model on an auxiliary planar graph. Thus, the truncated series can be easily re-summed, using the Pfaffian formula of Kasteleyn (1961 Physics 27 1209). This allows us to identify a big class of computationally tractable planar models reducible to a dimer model via the Belief Propagation (gauge) transformation. The Pfaffian representation can also be extended to the full Loop Series, in which case the expansion becomes a sum of Pfaffian contributions, each associated with dimer matchings on an extension to a subgraph of the original graph. Algorithmic consequences of the Pfaffian representation, as well as relations to quantum and non-planar models, are discussed

Functionals of Brownian motion, localization and metric graphs

International Nuclear Information System (INIS)

Comtet, Alain; Desbois, Jean; Texier, Christophe

2005-01-01

We review several results related to the problem of a quantum particle in a random environment. In an introductory part, we recall how several functionals of Brownian motion arise in the study of electronic transport in weakly disordered metals (weak localization). Two aspects of the physics of the one-dimensional strong localization are reviewed: some properties of the scattering by a random potential (time delay distribution) and a study of the spectrum of a random potential on a bounded domain (the extreme value statistics of the eigenvalues). Then we mention several results concerning the diffusion on graphs, and more generally the spectral properties of the Schroedinger operator on graphs. The interest of spectral determinants as generating functions characterizing the diffusion on graphs is illustrated. Finally, we consider a two-dimensional model of a charged particle coupled to the random magnetic field due to magnetic vortices. We recall the connection between spectral properties of this model and winding functionals of planar Brownian motion. (topical review)

Frequency and amplitude modulation of ultra-compact terahertz quantum cascade lasers using an integrated avalanche diode oscillator.

Science.gov (United States)

Castellano, Fabrizio; Li, Lianhe; Linfield, Edmund H; Davies, A Giles; Vitiello, Miriam S

2016-03-15

Mode-locked comb sources operating at optical frequencies underpin applications ranging from spectroscopy and ultrafast physics, through to absolute frequency measurements and atomic clocks. Extending their operation into the terahertz frequency range would greatly benefit from the availability of compact semiconductor-based sources. However, the development of any compact mode-locked THz laser, which itself is inherently a frequency comb, has yet to be achieved without the use of an external stimulus. High-power, electrically pumped quantum cascade lasers (QCLs) have recently emerged as a promising solution, owing to their octave spanning bandwidths, the ability to achieve group-velocity dispersion compensation and the possibility of obtaining active mode-locking. Here, we propose an unprecedented compact architecture to induce both frequency and amplitude self-modulation in a THz QCL. By engineering a microwave avalanche oscillator into the laser cavity, which provides a 10 GHz self-modulation of the bias current and output power, we demonstrate multimode laser emission centered around 3 THz, with distinct multiple sidebands. The resulting microwave amplitude and frequency self-modulation of THz QCLs opens up intriguing perspectives, for engineering integrated self-mode-locked THz lasers, with impact in fields such as nano- and ultrafast photonics and optical metrology.

Multiple network alignment on quantum computers

Science.gov (United States)

Daskin, Anmer; Grama, Ananth; Kais, Sabre

2014-12-01

Comparative analyses of graph-structured datasets underly diverse problems. Examples of these problems include identification of conserved functional components (biochemical interactions) across species, structural similarity of large biomolecules, and recurring patterns of interactions in social networks. A large class of such analyses methods quantify the topological similarity of nodes across networks. The resulting correspondence of nodes across networks, also called node alignment, can be used to identify invariant subgraphs across the input graphs. Given graphs as input, alignment algorithms use topological information to assign a similarity score to each -tuple of nodes, with elements (nodes) drawn from each of the input graphs. Nodes are considered similar if their neighbors are also similar. An alternate, equivalent view of these network alignment algorithms is to consider the Kronecker product of the input graphs and to identify high-ranked nodes in the Kronecker product graph. Conventional methods such as PageRank and HITS (Hypertext-Induced Topic Selection) can be used for this purpose. These methods typically require computation of the principal eigenvector of a suitably modified Kronecker product matrix of the input graphs. We adopt this alternate view of the problem to address the problem of multiple network alignment. Using the phase estimation algorithm, we show that the multiple network alignment problem can be efficiently solved on quantum computers. We characterize the accuracy and performance of our method and show that it can deliver exponential speedups over conventional (non-quantum) methods.

A graph rewriting programming language for graph drawing

OpenAIRE

Rodgers, Peter

1998-01-01

This paper describes Grrr, a prototype visual graph drawing tool. Previously there were no visual languages for programming graph drawing algorithms despite the inherently visual nature of the process. The languages which gave a diagrammatic view of graphs were not computationally complete and so could not be used to implement complex graph drawing algorithms. Hence current graph drawing tools are all text based. Recent developments in graph rewriting systems have produced computationally com...

Time series analysis of the developed financial markets' integration using visibility graphs

Science.gov (United States)

Zhuang, Enyu; Small, Michael; Feng, Gang

2014-09-01

A time series representing the developed financial markets' segmentation from 1973 to 2012 is studied. The time series reveals an obvious market integration trend. To further uncover the features of this time series, we divide it into seven windows and generate seven visibility graphs. The measuring capabilities of the visibility graphs provide means to quantitatively analyze the original time series. It is found that the important historical incidents that influenced market integration coincide with variations in the measured graphical node degree. Through the measure of neighborhood span, the frequencies of the historical incidents are disclosed. Moreover, it is also found that large "cycles" and significant noise in the time series are linked to large and small communities in the generated visibility graphs. For large cycles, how historical incidents significantly affected market integration is distinguished by density and compactness of the corresponding communities.

Physical approach to quantum networks with massive particles

Science.gov (United States)

Andersen, Molte Emil Strange; Zinner, Nikolaj Thomas

2018-04-01

Assembling large-scale quantum networks is a key goal of modern physics research with applications in quantum information and computation. Quantum wires and waveguides in which massive particles propagate in tailored confinement is one promising platform for realizing a quantum network. In the literature, such networks are often treated as quantum graphs, that is, the wave functions are taken to live on graphs of one-dimensional edges meeting in vertices. Hitherto, it has been unclear what boundary conditions on the vertices produce the physical states one finds in nature. This paper treats a quantum network from a physical approach, explicitly finds the physical eigenstates and compares them to the quantum-graph description. The basic building block of a quantum network is an X-shaped potential well made by crossing two quantum wires, and we consider a massive particle in such an X well. The system is analyzed using a variational method based on an expansion into modes with fast convergence and it provides a very clear intuition for the physics of the problem. The particle is found to have a ground state that is exponentially localized to the center of the X well, and the other symmetric solutions are formed so to be orthogonal to the ground state. This is in contrast to the predictions of the conventionally used so-called Kirchoff boundary conditions in quantum graph theory that predict a different sequence of symmetric solutions that cannot be physically realized. Numerical methods have previously been the only source of information on the ground-state wave function and our results provide a different perspective with strong analytical insights. The ground-state wave function has a spatial profile that looks very similar to the shape of a solitonic solution to a nonlinear Schrödinger equation, enabling an analytical prediction of the wave number. When combining multiple X wells into a network or grid, each site supports a solitonlike localized state. These

Equivalence of Szegedy's and coined quantum walks

Science.gov (United States)

Wong, Thomas G.

2017-09-01

Szegedy's quantum walk is a quantization of a classical random walk or Markov chain, where the walk occurs on the edges of the bipartite double cover of the original graph. To search, one can simply quantize a Markov chain with absorbing vertices. Recently, Santos proposed two alternative search algorithms that instead utilize the sign-flip oracle in Grover's algorithm rather than absorbing vertices. In this paper, we show that these two algorithms are exactly equivalent to two algorithms involving coined quantum walks, which are walks on the vertices of the original graph with an internal degree of freedom. The first scheme is equivalent to a coined quantum walk with one walk step per query of Grover's oracle, and the second is equivalent to a coined quantum walk with two walk steps per query of Grover's oracle. These equivalences lie outside the previously known equivalence of Szegedy's quantum walk with absorbing vertices and the coined quantum walk with the negative identity operator as the coin for marked vertices, whose precise relationships we also investigate.

Quantum walks based on an interferometric analogy

International Nuclear Information System (INIS)

Hillery, Mark; Bergou, Janos; Feldman, Edgar

2003-01-01

There are presently two models for quantum walks on graphs. The ''coined'' walk uses discrete-time steps, and contains, besides the particle making the walk, a second quantum system, the coin, that determines the direction in which the particle will move. The continuous walk operates with continuous time. Here a third model for quantum walks is proposed, which is based on an analogy to optical interferometers. It is a discrete-time model, and the unitary operator that advances the walk one step depends only on the local structure of the graph on which the walk is taking place. This type of walk also allows us to introduce elements, such as phase shifters, that have no counterpart in classical random walks. Several examples are discussed

Feynman amplitude and the Meijer's function. A unified representation for divergent and convergent graphs

Energy Technology Data Exchange (ETDEWEB)

Kucheryavyi, V I

1974-12-31

A parametric alpha -representation of Feynman amplitude for any spinor graph, which is expressed in terms of the Meijer's G functions, is obtained. This representation is valid both for divergent and convergent graphs. The available ChisholmNakanishi-Symanzik alpha -representation for convergent scalar graph turns out to be a special of the formula obtained. Besides that, the expression has a number of useful features. This representation automatically removes the infrared divergencies connected with zero photon mass. The expression has a form in which the scale-invariant terms are explicitly separated from the terms breaking the invariance. It is shown by considering the simplest graphs of quantum electrodynamics that this representation keeps gauge invariance and Ward's identity for renormalized amplitudes. (auth)

SNAP: A General Purpose Network Analysis and Graph Mining Library.

Science.gov (United States)

Leskovec, Jure; Sosič, Rok

2016-10-01

Large networks are becoming a widely used abstraction for studying complex systems in a broad set of disciplines, ranging from social network analysis to molecular biology and neuroscience. Despite an increasing need to analyze and manipulate large networks, only a limited number of tools are available for this task. Here, we describe Stanford Network Analysis Platform (SNAP), a general-purpose, high-performance system that provides easy to use, high-level operations for analysis and manipulation of large networks. We present SNAP functionality, describe its implementational details, and give performance benchmarks. SNAP has been developed for single big-memory machines and it balances the trade-off between maximum performance, compact in-memory graph representation, and the ability to handle dynamic graphs where nodes and edges are being added or removed over time. SNAP can process massive networks with hundreds of millions of nodes and billions of edges. SNAP offers over 140 different graph algorithms that can efficiently manipulate large graphs, calculate structural properties, generate regular and random graphs, and handle attributes and meta-data on nodes and edges. Besides being able to handle large graphs, an additional strength of SNAP is that networks and their attributes are fully dynamic, they can be modified during the computation at low cost. SNAP is provided as an open source library in C++ as well as a module in Python. We also describe the Stanford Large Network Dataset, a set of social and information real-world networks and datasets, which we make publicly available. The collection is a complementary resource to our SNAP software and is widely used for development and benchmarking of graph analytics algorithms.

Software-defined Quantum Networking Ecosystem

Energy Technology Data Exchange (ETDEWEB)

2017-01-01

The software enables a user to perform modeling and simulation of software-defined quantum networks. The software addresses the problem of how to synchronize transmission of quantum and classical signals through multi-node networks and to demonstrate quantum information protocols such as quantum teleportation. The software approaches this problem by generating a graphical model of the underlying network and attributing properties to each node and link in the graph. The graphical model is then simulated using a combination of discrete-event simulators to calculate the expected state of each node and link in the graph at a future time. A user interacts with the software by providing an initial network model and instantiating methods for the nodes to transmit information with each other. This includes writing application scripts in python that make use of the software library interfaces. A user then initiates the application scripts, which invokes the software simulation. The user then uses the built-in diagnostic tools to query the state of the simulation and to collect statistics on synchronization.

Graph Aggregation

NARCIS (Netherlands)

Endriss, U.; Grandi, U.

Graph aggregation is the process of computing a single output graph that constitutes a good compromise between several input graphs, each provided by a different source. One needs to perform graph aggregation in a wide variety of situations, e.g., when applying a voting rule (graphs as preference

Computer recognition of divergences in Feynman graphs

Energy Technology Data Exchange (ETDEWEB)

Calmet, J

1973-05-01

The program described recognizes whether or not a graph is divergent. It determines the kind of the divergences found: vacuum polarizations, electron self energies and vertices. it does not consider infrared divergences. The programming language used is REDUCE. A LISP version is also available. The nature of the divergences and their counter terms was extensively used to write down this program, therefore it is limited to the case of quantum electrodynamics. (auth)

From modular invariants to graphs: the modular splitting method

International Nuclear Information System (INIS)

Isasi, E; Schieber, G

2007-01-01

We start with a given modular invariant M of a two-dimensional su-hat(n) k conformal field theory (CFT) and present a general method for solving the Ocneanu modular splitting equation and then determine, in a step-by-step explicit construction (1) the generalized partition functions corresponding to the introduction of boundary conditions and defect lines; (2) the quantum symmetries of the higher ADE graph G associated with the initial modular invariant M. Note that one does not suppose here that the graph G is already known, since it appears as a by-product of the calculations. We analyse several su-hat(3) k exceptional cases at levels 5 and 9

Black holes and compact objects: Quantum aspects

Indian Academy of Sciences (India)

This is a summary of the papers presented in session W2 on a fairly wide-ranging variety of topics in the area of black hole physics and quantum aspects of gravity, including quantum field and string theory in curved spacetimes. In addition, experts in a couple of topical subjects were invited to present short surveys on the ...

Thermooptic two-mode interference device for reconfigurable quantum optic circuits

Science.gov (United States)

Sahu, Partha Pratim

2018-06-01

Reconfigurable large-scale integrated quantum optic circuits require compact component having capability of accurate manipulation of quantum entanglement for quantum communication and information processing applications. Here, a thermooptic two-mode interference coupler has been introduced as a compact component for generation of reconfigurable complex multi-photons quantum interference. Both theoretical and experimental approaches are used for the demonstration of two-photon and four-photon quantum entanglement manipulated with thermooptic phase change in TMI region. Our results demonstrate complex multi-photon quantum interference with high fabrication tolerance and quantum fidelity in smaller dimension than previous thermooptic Mach-Zehnder implementations.

Proxy Graph: Visual Quality Metrics of Big Graph Sampling.

Science.gov (United States)

Nguyen, Quan Hoang; Hong, Seok-Hee; Eades, Peter; Meidiana, Amyra

2017-06-01

Data sampling has been extensively studied for large scale graph mining. Many analyses and tasks become more efficient when performed on graph samples of much smaller size. The use of proxy objects is common in software engineering for analysis and interaction with heavy objects or systems. In this paper, we coin the term 'proxy graph' and empirically investigate how well a proxy graph visualization can represent a big graph. Our investigation focuses on proxy graphs obtained by sampling; this is one of the most common proxy approaches. Despite the plethora of data sampling studies, this is the first evaluation of sampling in the context of graph visualization. For an objective evaluation, we propose a new family of quality metrics for visual quality of proxy graphs. Our experiments cover popular sampling techniques. Our experimental results lead to guidelines for using sampling-based proxy graphs in visualization.

More on θ-compact fuzzy topological spaces

International Nuclear Information System (INIS)

Ekici, Erdal

2006-01-01

Recently, El-Naschie has shown that the notion of fuzzy topology may be relevant to quantum particle physics in connection with string theory and ε ∞ theory. In 2005, Caldas and Jafari have introduced θ-compact fuzzy topological spaces. The purpose of this paper is to investigate further properties of θ-compact fuzzy topological spaces. Moreover, the notion of θ-closed fuzzy topological spaces is introduced and properties of it are obtained

Quantum entanglement: Insights via graph parameters and conic optimization

NARCIS (Netherlands)

Piovesan, T.

2016-01-01

In this PhD thesis we study the effects of quantum entanglement, one of quantum mechanics most peculiar features, in nonlocal games and communication problems in zero-error information theory. A nonlocal game is a thought experiment in which two cooperating players, who are forbidden to communicate,

Spatial search by quantum walk

International Nuclear Information System (INIS)

Childs, Andrew M.; Goldstone, Jeffrey

2004-01-01

Grover's quantum search algorithm provides a way to speed up combinatorial search, but is not directly applicable to searching a physical database. Nevertheless, Aaronson and Ambainis showed that a database of N items laid out in d spatial dimensions can be searched in time of order √(N) for d>2, and in time of order √(N) poly(log N) for d=2. We consider an alternative search algorithm based on a continuous-time quantum walk on a graph. The case of the complete graph gives the continuous-time search algorithm of Farhi and Gutmann, and other previously known results can be used to show that √(N) speedup can also be achieved on the hypercube. We show that full √(N) speedup can be achieved on a d-dimensional periodic lattice for d>4. In d=4, the quantum walk search algorithm takes time of order √(N) poly(log N), and in d<4, the algorithm does not provide substantial speedup

The C*-algebras of quantum lens and weighted projective spaces

DEFF Research Database (Denmark)

Brzezinski, Tomasz; Szymanski, Wojciech

2018-01-01

It is shown that the algebra of continuous functions on the quantum 2n+1-dimensional lens space C(L^{2n+1}_q(N; m_0,..., m_n)) is a graph C*-algebra, for arbitrary positive weights m_0,..., m_n. The form of the corresponding graph is determined from the skew product of the graph which defines the...

Entanglement of the valence-bond-solid state on an arbitrary graph

International Nuclear Information System (INIS)

Xu Ying; Korepin, Vladimir E

2008-01-01

The Affleck-Kennedy-Lieb-Tasaki (AKLT) spin interacting model can be defined on an arbitrary graph. We explain the construction of the AKLT Hamiltonian. Given certain conditions, the ground state is unique and known as the valence-bond-solid (VBS) state. It can be used in measurement-based quantum computation as a resource state instead of the cluster state. We study the VBS ground state on an arbitrary connected graph. The graph is cut into two disconnected parts: the block and the environment. We study the entanglement between these two parts and prove that many eigenvalues of the density matrix of the block are zero. We describe a subspace of eigenvectors of the density matrix corresponding to non-zero eigenvalues. The subspace is the degenerate ground states of some Hamiltonian which we call the block Hamiltonian

Chromatic graph theory

CERN Document Server

Chartrand, Gary; Rosen, Kenneth H

2008-01-01

Beginning with the origin of the four color problem in 1852, the field of graph colorings has developed into one of the most popular areas of graph theory. Introducing graph theory with a coloring theme, Chromatic Graph Theory explores connections between major topics in graph theory and graph colorings as well as emerging topics. This self-contained book first presents various fundamentals of graph theory that lie outside of graph colorings, including basic terminology and results, trees and connectivity, Eulerian and Hamiltonian graphs, matchings and factorizations, and graph embeddings. The remainder of the text deals exclusively with graph colorings. It covers vertex colorings and bounds for the chromatic number, vertex colorings of graphs embedded on surfaces, and a variety of restricted vertex colorings. The authors also describe edge colorings, monochromatic and rainbow edge colorings, complete vertex colorings, several distinguishing vertex and edge colorings, and many distance-related vertex coloring...

A linearization of quantum channels

Science.gov (United States)

Crowder, Tanner

2015-06-01

Because the quantum channels form a compact, convex set, we can express any quantum channel as a convex combination of extremal channels. We give a Euclidean representation for the channels whose inverses are also valid channels; these are a subset of the extreme points. They form a compact, connected Lie group, and we calculate its Lie algebra. Lastly, we calculate a maximal torus for the group and provide a constructive approach to decomposing any invertible channel into a product of elementary channels.

Analytic properties of Feynman diagrams in quantum field theory

CERN Document Server

Todorov, I T

1971-01-01

Analytic Properties of Feynman Diagrams in Quantum Field Theory deals with quantum field theory, particularly in the study of the analytic properties of Feynman graphs. This book is an elementary presentation of a self-contained exposition of the majorization method used in the study of these graphs. The author has taken the intermediate position between Eden et al. who assumes the physics of the analytic properties of the S-matrix, containing physical ideas and test results without using the proper mathematical methods, and Hwa and Teplitz, whose works are more mathematically inclined with a

Discrete Morse functions for graph configuration spaces

International Nuclear Information System (INIS)

Sawicki, A

2012-01-01

We present an alternative application of discrete Morse theory for two-particle graph configuration spaces. In contrast to previous constructions, which are based on discrete Morse vector fields, our approach is through Morse functions, which have a nice physical interpretation as two-body potentials constructed from one-body potentials. We also give a brief introduction to discrete Morse theory. Our motivation comes from the problem of quantum statistics for particles on networks, for which generalized versions of anyon statistics can appear. (paper)

Continuous-time quantum walk on an extended star graph: Trapping and superradiance transition

Science.gov (United States)

Yalouz, Saad; Pouthier, Vincent

2018-02-01

A tight-binding model is introduced for describing the dynamics of an exciton on an extended star graph whose central node is occupied by a trap. On this graph, the exciton dynamics is governed by two kinds of eigenstates: many eigenstates are associated with degenerate real eigenvalues insensitive to the trap, whereas three decaying eigenstates characterized by complex energies contribute to the trapping process. It is shown that the excitonic population absorbed by the trap depends on the size of the graph, only. By contrast, both the size parameters and the absorption rate control the dynamics of the trapping. When these parameters are judiciously chosen, the efficiency of the transfer is optimized resulting in the minimization of the absorption time. Analysis of the eigenstates reveals that such a feature arises around the superradiance transition. Moreover, depending on the size of the network, two situations are highlighted where the transport efficiency is either superoptimized or suboptimized.

State transfer in highly connected networks and a quantum Babinet principle

Science.gov (United States)

Tsomokos, D. I.; Plenio, M. B.; de Vega, I.; Huelga, S. F.

2008-12-01

The transfer of a quantum state between distant nodes in two-dimensional networks is considered. The fidelity of state transfer is calculated as a function of the number of interactions in networks that are described by regular graphs. It is shown that perfect state transfer is achieved in a network of size N , whose structure is that of an (N/2) -cross polytope graph, if N is a multiple of 4 . The result is reminiscent of the Babinet principle of classical optics. A quantum Babinet principle is derived, which allows for the identification of complementary graphs leading to the same fidelity of state transfer, in analogy with complementary screens providing identical diffraction patterns.

Realization of vector fields for quantum groups as pseudodifferential operators on quantum spaces

International Nuclear Information System (INIS)

Chu, Chong-Sun; Zumino, B.

1995-01-01

The vector fields of the quantum Lie algebra are described for the quantum groups GL q (n), SL q (N) and SO q (N) as pseudodifferential operators on the linear quantum spaces covariant under the corresponding quantum group. Their expressions are simple and compact. It is pointed out that these vector fields satisfy certain characteristic polynomial identities. The real forms SU q (N) and SO q (N,R) are discussed in detail

Algebraic Bethe ansatz for U(1) invariant integrable models: Compact and non-compact applications

International Nuclear Information System (INIS)

Martins, M.J.; Melo, C.S.

2009-01-01

We apply the algebraic Bethe ansatz developed in our previous paper [C.S. Melo, M.J. Martins, Nucl. Phys. B 806 (2009) 567] to three different families of U(1) integrable vertex models with arbitrary N bond states. These statistical mechanics systems are based on the higher spin representations of the quantum group U q [SU(2)] for both generic and non-generic values of q as well as on the non-compact discrete representation of the SL(2,R) algebra. We present for all these models the explicit expressions for both the on-shell and the off-shell properties associated to the respective transfer matrices eigenvalue problems. The amplitudes governing the vectors not parallel to the Bethe states are shown to factorize in terms of elementary building blocks functions. The results for the non-compact SL(2,R) model are argued to be derived from those obtained for the compact systems by taking suitable N→∞ limits. This permits us to study the properties of the non-compact SL(2,R) model starting from systems with finite degrees of freedom.

Algebraic Bethe ansatz for U(1) invariant integrable models: Compact and non-compact applications

Science.gov (United States)

Martins, M. J.; Melo, C. S.

2009-10-01

We apply the algebraic Bethe ansatz developed in our previous paper [C.S. Melo, M.J. Martins, Nucl. Phys. B 806 (2009) 567] to three different families of U(1) integrable vertex models with arbitrary N bond states. These statistical mechanics systems are based on the higher spin representations of the quantum group U[SU(2)] for both generic and non-generic values of q as well as on the non-compact discrete representation of the SL(2,R) algebra. We present for all these models the explicit expressions for both the on-shell and the off-shell properties associated to the respective transfer matrices eigenvalue problems. The amplitudes governing the vectors not parallel to the Bethe states are shown to factorize in terms of elementary building blocks functions. The results for the non-compact SL(2,R) model are argued to be derived from those obtained for the compact systems by taking suitable N→∞ limits. This permits us to study the properties of the non-compact SL(2,R) model starting from systems with finite degrees of freedom.

Graph sampling

OpenAIRE

Zhang, L.-C.; Patone, M.

2017-01-01

We synthesise the existing theory of graph sampling. We propose a formal definition of sampling in finite graphs, and provide a classification of potential graph parameters. We develop a general approach of Horvitz–Thompson estimation to T-stage snowball sampling, and present various reformulations of some common network sampling methods in the literature in terms of the outlined graph sampling theory.

A graph-Laplacian-based feature extraction algorithm for neural spike sorting.

Science.gov (United States)

Ghanbari, Yasser; Spence, Larry; Papamichalis, Panos

2009-01-01

Analysis of extracellular neural spike recordings is highly dependent upon the accuracy of neural waveform classification, commonly referred to as spike sorting. Feature extraction is an important stage of this process because it can limit the quality of clustering which is performed in the feature space. This paper proposes a new feature extraction method (which we call Graph Laplacian Features, GLF) based on minimizing the graph Laplacian and maximizing the weighted variance. The algorithm is compared with Principal Components Analysis (PCA, the most commonly-used feature extraction method) using simulated neural data. The results show that the proposed algorithm produces more compact and well-separated clusters compared to PCA. As an added benefit, tentative cluster centers are output which can be used to initialize a subsequent clustering stage.

Algorithms for Planar Graphs and Graphs in Metric Spaces

DEFF Research Database (Denmark)

Wulff-Nilsen, Christian

structural properties that can be exploited. For instance, a road network or a wire layout on a microchip is typically (near-)planar and distances in the network are often defined w.r.t. the Euclidean or the rectilinear metric. Specialized algorithms that take advantage of such properties are often orders...... of magnitude faster than the corresponding algorithms for general graphs. The first and main part of this thesis focuses on the development of efficient planar graph algorithms. The most important contributions include a faster single-source shortest path algorithm, a distance oracle with subquadratic...... for geometric graphs and graphs embedded in metric spaces. Roughly speaking, the stretch factor is a real value expressing how well a (geo-)metric graph approximates the underlying complete graph w.r.t. distances. We give improved algorithms for computing the stretch factor of a given graph and for augmenting...

Cryptanalysis of Compact-LWE and Related Lightweight Public Key Encryption

Directory of Open Access Journals (Sweden)

Dianyan Xiao

2018-01-01

Full Text Available In the emerging Internet of Things (IoT, lightweight public key cryptography plays an essential role in security and privacy protection. With the approach of quantum computing era, it is important to design and evaluate lightweight quantum-resistant cryptographic algorithms applicable to IoT. LWE-based cryptography is a widely used and well-studied family of postquantum cryptographic constructions whose hardness is based on worst-case lattice problems. To make LWE friendly to resource-constrained IoT devices, a variant of LWE, named Compact-LWE, was proposed and used to design lightweight cryptographic schemes. In this paper, we study the so-called Compact-LWE problem and clarify that under certain parameter settings it can be solved in polynomial time. As a consequence, our result leads to a practical attack against an instantiated scheme based on Compact-LWE proposed by Liu et al. in 2017.

Enhanced Gain in Slow-Light Photonic Crystal Waveguides with Embedded Quantum Dots

DEFF Research Database (Denmark)

Ek, Sara; Hansen, Per Lunnemann; Semenova, Elizaveta

2011-01-01

We experimentally demonstrate enhanced gain in the slow-light regime of quantum dot photonic crystal waveguide slabs. These are promising results for future compact devices for terabit/s communication, such as compact optical amplifiers and mode-locked lasers.......We experimentally demonstrate enhanced gain in the slow-light regime of quantum dot photonic crystal waveguide slabs. These are promising results for future compact devices for terabit/s communication, such as compact optical amplifiers and mode-locked lasers....

Quantum random-walk search algorithm

International Nuclear Information System (INIS)

Shenvi, Neil; Whaley, K. Birgitta; Kempe, Julia

2003-01-01

Quantum random walks on graphs have been shown to display many interesting properties, including exponentially fast hitting times when compared with their classical counterparts. However, it is still unclear how to use these novel properties to gain an algorithmic speedup over classical algorithms. In this paper, we present a quantum search algorithm based on the quantum random-walk architecture that provides such a speedup. It will be shown that this algorithm performs an oracle search on a database of N items with O(√(N)) calls to the oracle, yielding a speedup similar to other quantum search algorithms. It appears that the quantum random-walk formulation has considerable flexibility, presenting interesting opportunities for development of other, possibly novel quantum algorithms

Orbifolds, quantum cosmology, and nontrivial topology

International Nuclear Information System (INIS)

Fagundes, Helio V.; Vargas, Teofilo

2006-01-01

In order to include nontrivial topologies in the problem of quantum creation of a universe, it seems to be necessary to generalize the sum over compact, smooth 4-manifolds to a sum over finite-volume, compact 4-orbifolds. We consider in detail the case of a 4-spherical orbifold with a cone-point singularity. This allows for the inclusion of a nontrivial topology into the semiclassical path integral approach to quantum cosmology, in the context of a Robertson-Walker minisuperspace. (author)

Verifiable Measurement-Only Blind Quantum Computing with Stabilizer Testing.

Science.gov (United States)

Hayashi, Masahito; Morimae, Tomoyuki

2015-11-27

We introduce a simple protocol for verifiable measurement-only blind quantum computing. Alice, a client, can perform only single-qubit measurements, whereas Bob, a server, can generate and store entangled many-qubit states. Bob generates copies of a graph state, which is a universal resource state for measurement-based quantum computing, and sends Alice each qubit of them one by one. Alice adaptively measures each qubit according to her program. If Bob is honest, he generates the correct graph state, and, therefore, Alice can obtain the correct computation result. Regarding the security, whatever Bob does, Bob cannot get any information about Alice's computation because of the no-signaling principle. Furthermore, malicious Bob does not necessarily send the copies of the correct graph state, but Alice can check the correctness of Bob's state by directly verifying the stabilizers of some copies.

Multipartite fully nonlocal quantum states

International Nuclear Information System (INIS)

Almeida, Mafalda L.; Cavalcanti, Daniel; Scarani, Valerio; Acin, Antonio

2010-01-01

We present a general method for characterizing the quantum correlations obtained after local measurements on multipartite systems. Sufficient conditions for a quantum system to be fully nonlocal according to a given partition, as well as being (genuinely) multipartite fully nonlocal, are derived. These conditions allow us to identify all completely connected graph states as multipartite fully nonlocal quantum states. Moreover, we show that this feature can also be observed in mixed states: the tensor product of five copies of the Smolin state, a biseparable and bound entangled state, is multipartite fully nonlocal.

Bounds of the Spectral Radius and the Nordhaus-Gaddum Type of the Graphs

Directory of Open Access Journals (Sweden)

Tianfei Wang

2013-01-01

Full Text Available The Laplacian spectra are the eigenvalues of Laplacian matrix L(G=D(G-A(G, where D(G and A(G are the diagonal matrix of vertex degrees and the adjacency matrix of a graph G, respectively, and the spectral radius of a graph G is the largest eigenvalue of A(G. The spectra of the graph and corresponding eigenvalues are closely linked to the molecular stability and related chemical properties. In quantum chemistry, spectral radius of a graph is the maximum energy level of molecules. Therefore, good upper bounds for the spectral radius are conducive to evaluate the energy of molecules. In this paper, we first give several sharp upper bounds on the adjacency spectral radius in terms of some invariants of graphs, such as the vertex degree, the average 2-degree, and the number of the triangles. Then, we give some numerical examples which indicate that the results are better than the mentioned upper bounds in some sense. Finally, an upper bound of the Nordhaus-Gaddum type is obtained for the sum of Laplacian spectral radius of a connected graph and its complement. Moreover, some examples are applied to illustrate that our result is valuable.

Degree Associated Edge Reconstruction Number of Graphs with Regular Pruned Graph

Directory of Open Access Journals (Sweden)

P. Anusha Devi

2015-10-01

Full Text Available An ecard of a graph $G$ is a subgraph formed by deleting an edge. A da-ecard specifies the degree of the deleted edge along with the ecard. The degree associated edge reconstruction number of a graph $G,~dern(G,$ is the minimum number of da-ecards that uniquely determines $G.$  The adversary degree associated edge reconstruction number of a graph $G, adern(G,$ is the minimum number $k$ such that every collection of $k$ da-ecards of $G$ uniquely determines $G.$ The maximal subgraph without end vertices of a graph $G$ which is not a tree is the pruned graph of $G.$ It is shown that $dern$ of complete multipartite graphs and some connected graphs with regular pruned graph is $1$ or $2.$ We also determine $dern$ and $adern$ of corona product of standard graphs.

{theta}-Compactness in L-topological spaces

Energy Technology Data Exchange (ETDEWEB)

Hanafy, I.M. [Department of Mathematics, Faculty of Education, Suez Canal University, El-Arish (Egypt)], E-mail: ihanafy@hotmail.com

2009-12-15

Recently, El-Naschie has shown that the notion of fuzzy topology may be relevant to quantum particle physics in connection with string theory and e{sup {infinity}} theory. In 2005, Caldas and Jafari have introduced {theta}-compact fuzzy topological spaces. In this paper, the concepts of{theta}-compactness, countable{theta}-compactness and the{theta}-Lindeloef property are introduced and studied in L-topological spaces, where L is a complete de Morgan algebra. They are defined by means of{theta}-openL-sets and their inequalities. They does not rely on the structure of basis lattice L and no distributivity in L is required. They can also be characterized by{theta}-closedL-sets and their inequalities. When L is a completely de Morgan algebra, their many characterizations are presented.

High-Quality Ultra-Compact Grid Layout of Grouped Networks.

Science.gov (United States)

Yoghourdjian, Vahan; Dwyer, Tim; Gange, Graeme; Kieffer, Steve; Klein, Karsten; Marriott, Kim

2016-01-01

Prior research into network layout has focused on fast heuristic techniques for layout of large networks, or complex multi-stage pipelines for higher quality layout of small graphs. Improvements to these pipeline techniques, especially for orthogonal-style layout, are difficult and practical results have been slight in recent years. Yet, as discussed in this paper, there remain significant issues in the quality of the layouts produced by these techniques, even for quite small networks. This is especially true when layout with additional grouping constraints is required. The first contribution of this paper is to investigate an ultra-compact, grid-like network layout aesthetic that is motivated by the grid arrangements that are used almost universally by designers in typographical layout. Since the time when these heuristic and pipeline-based graph-layout methods were conceived, generic technologies (MIP, CP and SAT) for solving combinatorial and mixed-integer optimization problems have improved massively. The second contribution of this paper is to reassess whether these techniques can be used for high-quality layout of small graphs. While they are fast enough for graphs of up to 50 nodes we found these methods do not scale up. Our third contribution is a large-neighborhood search meta-heuristic approach that is scalable to larger networks.

Introduction to graph theory

CERN Document Server

Trudeau, Richard J

1994-01-01

Preface1. Pure Mathematics Introduction; Euclidean Geometry as Pure Mathematics; Games; Why Study Pure Mathematics?; What's Coming; Suggested Reading2. Graphs Introduction; Sets; Paradox; Graphs; Graph diagrams; Cautions; Common Graphs; Discovery; Complements and Subgraphs; Isomorphism; Recognizing Isomorphic Graphs; Semantics The Number of Graphs Having a Given nu; Exercises; Suggested Reading3. Planar Graphs Introduction; UG, K subscript 5, and the Jordan Curve Theorem; Are there More Nonplanar Graphs?; Expansions; Kuratowski's Theorem; Determining Whether a Graph is Planar or

Graph Theory. 2. Vertex Descriptors and Graph Coloring

Directory of Open Access Journals (Sweden)

Lorentz JÄNTSCHI

2002-12-01

Full Text Available This original work presents the construction of a set of ten sequence matrices and their applications for ordering vertices in graphs. For every sequence matrix three ordering criteria are applied: lexicographic ordering, based on strings of numbers, corresponding to every vertex, extracted as rows from sequence matrices; ordering by the sum of path lengths from a given vertex; and ordering by the sum of paths, starting from a given vertex. We also examine a graph that has different orderings for the above criteria. We then proceed to demonstrate that every criterion induced its own partition of graph vertex. We propose the following theoretical result: both LAVS and LVDS criteria generate identical partitioning of vertices in any graph. Finally, a coloring of graph vertices according to introduced ordering criteria was proposed.

On an edge partition and root graphs of some classes of line graphs

Directory of Open Access Journals (Sweden)

K Pravas

2017-04-01

Full Text Available The Gallai and the anti-Gallai graphs of a graph $G$ are complementary pairs of spanning subgraphs of the line graph of $G$. In this paper we find some structural relations between these graph classes by finding a partition of the edge set of the line graph of a graph $G$ into the edge sets of the Gallai and anti-Gallai graphs of $G$. Based on this, an optimal algorithm to find the root graph of a line graph is obtained. Moreover, root graphs of diameter-maximal, distance-hereditary, Ptolemaic and chordal graphs are also discussed.

Graphs and matrices

CERN Document Server

Bapat, Ravindra B

2014-01-01

This new edition illustrates the power of linear algebra in the study of graphs. The emphasis on matrix techniques is greater than in other texts on algebraic graph theory. Important matrices associated with graphs (for example, incidence, adjacency and Laplacian matrices) are treated in detail. Presenting a useful overview of selected topics in algebraic graph theory, early chapters of the text focus on regular graphs, algebraic connectivity, the distance matrix of a tree, and its generalized version for arbitrary graphs, known as the resistance matrix. Coverage of later topics include Laplacian eigenvalues of threshold graphs, the positive definite completion problem and matrix games based on a graph. Such an extensive coverage of the subject area provides a welcome prompt for further exploration. The inclusion of exercises enables practical learning throughout the book. In the new edition, a new chapter is added on the line graph of a tree, while some results in Chapter 6 on Perron-Frobenius theory are reo...

Graphs cospectral with a friendship graph or its complement

Directory of Open Access Journals (Sweden)

Alireza Abdollahi

2013-12-01

Full Text Available Let $n$ be any positive integer and let $F_n$ be the friendship (or Dutch windmill graph with $2n+1$ vertices and $3n$ edges. Here we study graphs with the same adjacency spectrum as the $F_n$. Two graphs are called cospectral if the eigenvalues multiset of their adjacency matrices are the same. Let $G$ be a graph cospectral with $F_n$. Here we prove that if $G$ has no cycle of length $4$ or $5$, then $Gcong F_n$. Moreover if $G$ is connected and planar then $Gcong F_n$.All but one of connected components of $G$ are isomorphic to $K_2$.The complement $overline{F_n}$ of the friendship graph is determined by its adjacency eigenvalues, that is, if $overline{F_n}$ is cospectral with a graph $H$, then $Hcong overline{F_n}$.

Spacetime Replication of Quantum Information Using (2 , 3) Quantum Secret Sharing and Teleportation

Science.gov (United States)

Wu, Yadong; Khalid, Abdullah; Davijani, Masoud; Sanders, Barry

The aim of this work is to construct a protocol to replicate quantum information in any valid configuration of causal diamonds and assess resources required to physically realize spacetime replication. We present a set of codes to replicate quantum information along with a scheme to realize these codes using continuous-variable quantum optics. We use our proposed experimental realizations to determine upper bounds on the quantum and classical resources required to simulate spacetime replication. For four causal diamonds, our implementation scheme is more efficient than the one proposed previously. Our codes are designed using a decomposition algorithm for complete directed graphs, (2 , 3) quantum secret sharing, quantum teleportation and entanglement swapping. These results show the simulation of spacetime replication of quantum information is feasible with existing experimental methods. Alberta Innovates, NSERC, China's 1000 Talent Plan and the Institute for Quantum Information and Matter, which is an NSF Physics Frontiers Center (NSF Grant PHY-1125565) with support of the Gordon and Betty Moore Foundation (GBMF-2644).

Simulating continuous-time Hamiltonian dynamics by way of a discrete-time quantum walk

International Nuclear Information System (INIS)

Schmitz, A.T.; Schwalm, W.A.

2016-01-01

Much effort has been made to connect the continuous-time and discrete-time quantum walks. We present a method for making that connection for a general graph Hamiltonian on a bigraph. Furthermore, such a scheme may be adapted for simulating discretized quantum models on a quantum computer. A coin operator is found for the discrete-time quantum walk which exhibits the same dynamics as the continuous-time evolution. Given the spectral decomposition of the graph Hamiltonian and certain restrictions, the discrete-time evolution is solved for explicitly and understood at or near important values of the parameters. Finally, this scheme is connected to past results for the 1D chain. - Highlights: • A discrete-time quantum walk is purposed which approximates a continuous-time quantum walk. • The purposed quantum walk could be used to simulate Hamiltonian dynamics on a quantum computer. • Given the spectra decomposition of the Hamiltonian, the quantum walk is solved explicitly. • The method is demonstrated and connected to previous work done on the 1D chain.

Solving the scalability issue in quantum-based refinement: Q|R#1.

Science.gov (United States)

Zheng, Min; Moriarty, Nigel W; Xu, Yanting; Reimers, Jeffrey R; Afonine, Pavel V; Waller, Mark P

2017-12-01

Accurately refining biomacromolecules using a quantum-chemical method is challenging because the cost of a quantum-chemical calculation scales approximately as n m , where n is the number of atoms and m (≥3) is based on the quantum method of choice. This fundamental problem means that quantum-chemical calculations become intractable when the size of the system requires more computational resources than are available. In the development of the software package called Q|R, this issue is referred to as Q|R#1. A divide-and-conquer approach has been developed that fragments the atomic model into small manageable pieces in order to solve Q|R#1. Firstly, the atomic model of a crystal structure is analyzed to detect noncovalent interactions between residues, and the results of the analysis are represented as an interaction graph. Secondly, a graph-clustering algorithm is used to partition the interaction graph into a set of clusters in such a way as to minimize disruption to the noncovalent interaction network. Thirdly, the environment surrounding each individual cluster is analyzed and any residue that is interacting with a particular cluster is assigned to the buffer region of that particular cluster. A fragment is defined as a cluster plus its buffer region. The gradients for all atoms from each of the fragments are computed, and only the gradients from each cluster are combined to create the total gradients. A quantum-based refinement is carried out using the total gradients as chemical restraints. In order to validate this interaction graph-based fragmentation approach in Q|R, the entire atomic model of an amyloid cross-β spine crystal structure (PDB entry 2oNA) was refined.

On the absence of absolutely continuous spectra for Schrodinger operators on radial tree graphs

Czech Academy of Sciences Publication Activity Database

Exner, Pavel; Lipovský, Jiří

2010-01-01

Roč. 51, č. 12 (2010), 122107/1-122107/19 ISSN 0022-2488 R&D Projects: GA MŠk LC06002 Institutional research plan: CEZ:AV0Z10480505 Keywords : QUANTUM GRAPHS * METRIC TREES Subject RIV: BA - General Mathematics Impact factor: 1.291, year: 2010

Hyperfunction quantum field theory

International Nuclear Information System (INIS)

Nagamachi, S.; Mugibayashi, N.

1976-01-01

The quantum field theory in terms of Fourier hyperfunctions is constructed. The test function space for hyperfunctions does not contain C infinitely functios with compact support. In spite of this defect the support concept of H-valued Fourier hyperfunctions allows to formulate the locality axiom for hyperfunction quantum field theory. (orig.) [de

Graph embedding with rich information through heterogeneous graph

KAUST Repository

Sun, Guolei

2017-11-12

Graph embedding, aiming to learn low-dimensional representations for nodes in graphs, has attracted increasing attention due to its critical application including node classification, link prediction and clustering in social network analysis. Most existing algorithms for graph embedding only rely on the topology information and fail to use the copious information in nodes as well as edges. As a result, their performance for many tasks may not be satisfactory. In this thesis, we proposed a novel and general framework for graph embedding with rich text information (GERI) through constructing a heterogeneous network, in which we integrate node and edge content information with graph topology. Specially, we designed a novel biased random walk to explore the constructed heterogeneous network with the notion of flexible neighborhood. Our sampling strategy can compromise between BFS and DFS local search on heterogeneous graph. To further improve our algorithm, we proposed semi-supervised GERI (SGERI), which learns graph embedding in an discriminative manner through heterogeneous network with label information. The efficacy of our method is demonstrated by extensive comparison experiments with 9 baselines over multi-label and multi-class classification on various datasets including Citeseer, Cora, DBLP and Wiki. It shows that GERI improves the Micro-F1 and Macro-F1 of node classification up to 10%, and SGERI improves GERI by 5% in Wiki.

Topics in graph theory graphs and their Cartesian product

CERN Document Server

Imrich, Wilfried; Rall, Douglas F

2008-01-01

From specialists in the field, you will learn about interesting connections and recent developments in the field of graph theory by looking in particular at Cartesian products-arguably the most important of the four standard graph products. Many new results in this area appear for the first time in print in this book. Written in an accessible way, this book can be used for personal study in advanced applications of graph theory or for an advanced graph theory course.

Study of Chromatic parameters of Line, Total, Middle graphs and Graph operators of Bipartite graph

Science.gov (United States)

Nagarathinam, R.; Parvathi, N.

2018-04-01

Chromatic parameters have been explored on the basis of graph coloring process in which a couple of adjacent nodes receives different colors. But the Grundy and b-coloring executes maximum colors under certain restrictions. In this paper, Chromatic, b-chromatic and Grundy number of some graph operators of bipartite graph has been investigat

Handbook of graph grammars and computing by graph transformation

CERN Document Server

Engels, G; Kreowski, H J; Rozenberg, G

1999-01-01

Graph grammars originated in the late 60s, motivated by considerations about pattern recognition and compiler construction. Since then, the list of areas which have interacted with the development of graph grammars has grown quite impressively. Besides the aforementioned areas, it includes software specification and development, VLSI layout schemes, database design, modeling of concurrent systems, massively parallel computer architectures, logic programming, computer animation, developmental biology, music composition, visual languages, and many others.The area of graph grammars and graph tran

Observations of the Ramsauer-Townsend effect in quaternionic quantum mechanics

Energy Technology Data Exchange (ETDEWEB)

Sobhani, Hadi [Damghan Branch, Islamic Azad University, Young Researchers and Elite Club, Damghan (Iran, Islamic Republic of); Hassanabadi, Hassan [Shahrood University of Technology, Physics Department (Iran, Islamic Republic of); Chung, Won Sang [Gyeongsang National University, Department of Physics and Research Institute of Natural Science, College of Natural Science, Jinju (Korea, Republic of)

2017-06-15

In this article, one of the well-known effects in quantum mechanics is addressed and also the extended form of quantum mechanics which is based on quaternions is presented. In the presence of this version of quantum mechanics the Ramsauer-Townsend effect has been investigated and the existence of this phenomenon is studied according to quaternionic calculations; results are presented by graphs. (orig.)

Continuous-variable quantum computing in optical time-frequency modes using quantum memories.

Science.gov (United States)

Humphreys, Peter C; Kolthammer, W Steven; Nunn, Joshua; Barbieri, Marco; Datta, Animesh; Walmsley, Ian A

2014-09-26

We develop a scheme for time-frequency encoded continuous-variable cluster-state quantum computing using quantum memories. In particular, we propose a method to produce, manipulate, and measure two-dimensional cluster states in a single spatial mode by exploiting the intrinsic time-frequency selectivity of Raman quantum memories. Time-frequency encoding enables the scheme to be extremely compact, requiring a number of memories that are a linear function of only the number of different frequencies in which the computational state is encoded, independent of its temporal duration. We therefore show that quantum memories can be a powerful component for scalable photonic quantum information processing architectures.

A memory-efficient data structure representing exact-match overlap graphs with application for next-generation DNA assembly.

Science.gov (United States)

Dinh, Hieu; Rajasekaran, Sanguthevar

2011-07-15

Exact-match overlap graphs have been broadly used in the context of DNA assembly and the shortest super string problem where the number of strings n ranges from thousands to billions. The length ℓ of the strings is from 25 to 1000, depending on the DNA sequencing technologies. However, many DNA assemblers using overlap graphs suffer from the need for too much time and space in constructing the graphs. It is nearly impossible for these DNA assemblers to handle the huge amount of data produced by the next-generation sequencing technologies where the number n of strings could be several billions. If the overlap graph is explicitly stored, it would require Ω(n(2)) memory, which could be prohibitive in practice when n is greater than a hundred million. In this article, we propose a novel data structure using which the overlap graph can be compactly stored. This data structure requires only linear time to construct and and linear memory to store. For a given set of input strings (also called reads), we can informally define an exact-match overlap graph as follows. Each read is represented as a node in the graph and there is an edge between two nodes if the corresponding reads overlap sufficiently. A formal description follows. The maximal exact-match overlap of two strings x and y, denoted by ov(max)(x, y), is the longest string which is a suffix of x and a prefix of y. The exact-match overlap graph of n given strings of length ℓ is an edge-weighted graph in which each vertex is associated with a string and there is an edge (x, y) of weight ω=ℓ-|ov(max)(x, y)| if and only if ω ≤ λ, where |ov(max)(x, y)| is the length of ov(max)(x, y) and λ is a given threshold. In this article, we show that the exact-match overlap graphs can be represented by a compact data structure that can be stored using at most (2λ-1)(2⌈logn⌉+⌈logλ⌉)n bits with a guarantee that the basic operation of accessing an edge takes O(log λ) time. We also propose two algorithms for

Gambler's ruin problem on Erdős-Rényi graphs

Science.gov (United States)

Néda, Zoltán; Davidova, Larissa; Újvári, Szeréna; Istrate, Gabriel

2017-02-01

A multiagent ruin-game is studied on Erdős-Rényi type graphs. Initially the players have the same wealth. At each time step a monopolist game is played on all active links (links that connect nodes with nonzero wealth). In such a game each player puts a unit wealth in the pot and the pot is won with equal probability by one of the players. The game ends when there are no connected players such that both of them have non-zero wealth. In order to characterize the final state for dense graphs a compact formula is given for the expected number of the remaining players with non-zero wealth and the wealth distribution among these players. Theoretical predictions are given for the expected duration of the ruin game. The dynamics of the number of active players is also investigated. Validity of the theoretical predictions is investigated by Monte Carlo experiments.

Centrosymmetric Graphs And A Lower Bound For Graph Energy Of Fullerenes

Directory of Open Access Journals (Sweden)

Katona Gyula Y.

2014-11-01

Full Text Available The energy of a molecular graph G is defined as the summation of the absolute values of the eigenvalues of adjacency matrix of a graph G. In this paper, an infinite class of fullerene graphs with 10n vertices, n ≥ 2, is considered. By proving centrosymmetricity of the adjacency matrix of these fullerene graphs, a lower bound for its energy is given. Our method is general and can be extended to other class of fullerene graphs.

Graphs and Homomorphisms

CERN Document Server

Hell, Pavol

2004-01-01

This is a book about graph homomorphisms. Graph theory is now an established discipline but the study of graph homomorphisms has only recently begun to gain wide acceptance and interest. The subject gives a useful perspective in areas such as graph reconstruction, products, fractional and circular colourings, and has applications in complexity theory, artificial intelligence, telecommunication, and, most recently, statistical physics.Based on the authors' lecture notes for graduate courses, this book can be used as a textbook for a second course in graph theory at 4th year or master's level an

Local unitary versus local Clifford equivalence of stabilizer and graph states

International Nuclear Information System (INIS)

Zeng, Bei; Chung, Hyeyoun; Cross, Andrew W.; Chuang, Isaac L.

2007-01-01

The equivalence of stabilizer states under local transformations is of fundamental interest in understanding properties and uses of entanglement. Two stabilizer states are equivalent under the usual stochastic local operations and classical communication criterion if and only if they are equivalent under local unitary (LU) operations. More surprisingly, under certain conditions, two LU-equivalent stabilizer states are also equivalent under local Clifford (LC) operations, as was shown by Van den Nest et al. [Phys. Rev. A 71, 062323 (2005)]. Here, we broaden the class of stabilizer states for which LU equivalence implies LC equivalence (LU LC) to include all stabilizer states represented by graphs with cycles of length neither 3 nor 4. To compare our result with Van den Nest et al.'s, we show that any stabilizer state of distance δ=2 is beyond their criterion. We then further prove that LU LC holds for a more general class of stabilizer states of δ=2. We also explicitly construct graphs representing δ>2 stabilizer states which are beyond their criterion: we identify all 58 graphs with up to 11 vertices and construct graphs with 2 m -1 (m≥4) vertices using quantum error-correcting codes which have non-Clifford transversal gates

Scalable effective-temperature reduction for quantum annealers via nested quantum annealing correction

Science.gov (United States)

Vinci, Walter; Lidar, Daniel A.

2018-02-01

Nested quantum annealing correction (NQAC) is an error-correcting scheme for quantum annealing that allows for the encoding of a logical qubit into an arbitrarily large number of physical qubits. The encoding replaces each logical qubit by a complete graph of degree C . The nesting level C represents the distance of the error-correcting code and controls the amount of protection against thermal and control errors. Theoretical mean-field analyses and empirical data obtained with a D-Wave Two quantum annealer (supporting up to 512 qubits) showed that NQAC has the potential to achieve a scalable effective-temperature reduction, Teff˜C-η , with 0 temperature of a quantum annealer. Such effective-temperature reduction is relevant for machine-learning applications. Since we demonstrate that NQAC achieves error correction via a reduction of the effective-temperature of the quantum annealing device, our results address the problem of the "temperature scaling law for quantum annealers," which requires the temperature of quantum annealers to be reduced as problems of larger sizes are attempted to be solved.

Compact Q-balls

Energy Technology Data Exchange (ETDEWEB)

Bazeia, D., E-mail: bazeia@fisica.ufpb.br [Departamento de Física, Universidade Federal da Paraíba, 58051-970 João Pessoa, PB (Brazil); Losano, L.; Marques, M.A. [Departamento de Física, Universidade Federal da Paraíba, 58051-970 João Pessoa, PB (Brazil); Menezes, R. [Departamento de Ciências Exatas, Universidade Federal da Paraíba, 58297-000 Rio Tinto, PB (Brazil); Departamento de Física, Universidade Federal de Campina Grande, 58109-970 Campina Grande, PB (Brazil); Rocha, R. da [Centro de Matemática, Computação e Cognição, Universidade Federal do ABC, 09210-580 Santo André (Brazil)

2016-07-10

In this work we deal with non-topological solutions of the Q-ball type in two space–time dimensions, in models described by a single complex scalar field that engenders global symmetry. The main novelty is the presence of stable Q-balls solutions that live in a compact interval of the real line and appear from a family of models controlled by two distinct parameters. We find analytical solutions and study their charge and energy, and show how to control the parameters to make the Q-balls classically and quantum mechanically stable.

Decomposing Oriented Graphs into Six Locally Irregular Oriented Graphs

DEFF Research Database (Denmark)

Bensmail, Julien; Renault, Gabriel

2016-01-01

An undirected graph G is locally irregular if every two of its adjacent vertices have distinct degrees. We say that G is decomposable into k locally irregular graphs if there exists a partition E1∪E2∪⋯∪Ek of the edge set E(G) such that each Ei induces a locally irregular graph. It was recently co...

Integrable lattice models and quantum groups

International Nuclear Information System (INIS)

Saleur, H.; Zuber, J.B.

1990-01-01

These lectures aim at introducing some basic algebraic concepts on lattice integrable models, in particular quantum groups, and to discuss some connections with knot theory and conformal field theories. The list of contents is: Vertex models and Yang-Baxter equation; Quantum sl(2) algebra and the Yang-Baxter equation; U q sl(2) as a symmetry of statistical mechanical models; Face models; Face models attached to graphs; Yang-Baxter equation, braid group and link polynomials

Non-heuristic reduction of the graph in graph-cut optimization

International Nuclear Information System (INIS)

Malgouyres, François; Lermé, Nicolas

2012-01-01

During the last ten years, graph cuts had a growing impact in shape optimization. In particular, they are commonly used in applications of shape optimization such as image processing, computer vision and computer graphics. Their success is due to their ability to efficiently solve (apparently) difficult shape optimization problems which typically involve the perimeter of the shape. Nevertheless, solving problems with a large number of variables remains computationally expensive and requires a high memory usage since underlying graphs sometimes involve billion of nodes and even more edges. Several strategies have been proposed in the literature to improve graph-cuts in this regards. In this paper, we give a formal statement which expresses that a simple and local test performed on every node before its construction permits to avoid the construction of useless nodes for the graphs typically encountered in image processing and vision. A useless node is such that the value of the maximum flow in the graph does not change when removing the node from the graph. Such a test therefore permits to limit the construction of the graph to a band of useful nodes surrounding the final cut.

Graph embedding with rich information through heterogeneous graph

KAUST Repository

Sun, Guolei

2017-01-01

Graph embedding, aiming to learn low-dimensional representations for nodes in graphs, has attracted increasing attention due to its critical application including node classification, link prediction and clustering in social network analysis. Most

QUANTUM: A Wolfram Mathematica add-on for Dirac Bra-Ket Notation, Non-Commutative Algebra, and Simulation of Quantum Computing Circuits

International Nuclear Information System (INIS)

Muñoz, J L Gómez; Delgado, F

2016-01-01

This paper introduces QUANTUM, a free library of commands of Wolfram Mathematica that can be used to perform calculations directly in Dirac braket and operator notation. Its development started several years ago, in order to study quantum random walks. Later, many other features were included, like operator and commutator algebra, simulation and graphing of quantum computing circuits, generation and solution of Heisenberg equations of motion, among others. To the best of our knowledge, QUANTUM remains a unique tool in its use of Dirac notation, because it is used both in the input and output of the calculations. This work depicts its usage and features in Quantum Computing and Quantum Hamilton Dynamics. (paper)

Quantum Cosmology

OpenAIRE

Page, Don N.

2006-01-01

A complete model of the universe needs at least three parts: (1) a complete set of physical variables and dynamical laws for them, (2) the correct solution of the dynamical laws, and (3) the connection with conscious experience. In quantum cosmology, item (2) is the quantum state of the cosmos. Hartle and Hawking have made the `no-boundary' proposal, that the wavefunction of the universe is given by a path integral over all compact Euclidean 4-dimensional geometries and matter fields that hav...

Ramsey numbers and adiabatic quantum computing.

Science.gov (United States)

Gaitan, Frank; Clark, Lane

2012-01-06

The graph-theoretic Ramsey numbers are notoriously difficult to calculate. In fact, for the two-color Ramsey numbers R(m,n) with m, n≥3, only nine are currently known. We present a quantum algorithm for the computation of the Ramsey numbers R(m,n). We show how the computation of R(m,n) can be mapped to a combinatorial optimization problem whose solution can be found using adiabatic quantum evolution. We numerically simulate this adiabatic quantum algorithm and show that it correctly determines the Ramsey numbers R(3,3) and R(2,s) for 5≤s≤7. We then discuss the algorithm's experimental implementation, and close by showing that Ramsey number computation belongs to the quantum complexity class quantum Merlin Arthur.

Anderson localization of ballooning modes, quantum chaos and the stability of compact quasiaxially symmetric stellarators

International Nuclear Information System (INIS)

Redi, M.H.; Johnson, J.L.; Klasky, S.; Canik, J.; Dewar, R.L.; Cooper, W.A.

2002-01-01

The radially local magnetohydrodynamic (MHD) ballooning stability of a compact, quasiaxially symmetric stellarator (QAS), is examined just above the ballooning beta limit with a method that can lead to estimates of global stability. Here MHD stability is analyzed through the calculation and examination of the ballooning mode eigenvalue isosurfaces in the 3-space (s,α,θ k ); s is the edge normalized toroidal flux, α is the field line variable, and θ k is the perpendicular wave vector or ballooning parameter. Broken symmetry, i.e., deviations from axisymmetry, in the stellarator magnetic field geometry causes localization of the ballooning mode eigenfunction, and gives rise to new types of nonsymmetric eigenvalue isosurfaces in both the stable and unstable spectrum. For eigenvalues far above the marginal point, isosurfaces are topologically spherical, indicative of strong 'quantum chaos'. The complexity of QAS marginal isosurfaces suggests that finite Larmor radius stabilization estimates will be difficult and that fully three-dimensional, high-n MHD computations are required to predict the beta limit

Graphing trillions of triangles.

Science.gov (United States)

Burkhardt, Paul

2017-07-01

The increasing size of Big Data is often heralded but how data are transformed and represented is also profoundly important to knowledge discovery, and this is exemplified in Big Graph analytics. Much attention has been placed on the scale of the input graph but the product of a graph algorithm can be many times larger than the input. This is true for many graph problems, such as listing all triangles in a graph. Enabling scalable graph exploration for Big Graphs requires new approaches to algorithms, architectures, and visual analytics. A brief tutorial is given to aid the argument for thoughtful representation of data in the context of graph analysis. Then a new algebraic method to reduce the arithmetic operations in counting and listing triangles in graphs is introduced. Additionally, a scalable triangle listing algorithm in the MapReduce model will be presented followed by a description of the experiments with that algorithm that led to the current largest and fastest triangle listing benchmarks to date. Finally, a method for identifying triangles in new visual graph exploration technologies is proposed.

Adaptive Graph Convolutional Neural Networks

OpenAIRE

Li, Ruoyu; Wang, Sheng; Zhu, Feiyun; Huang, Junzhou

2018-01-01

Graph Convolutional Neural Networks (Graph CNNs) are generalizations of classical CNNs to handle graph data such as molecular data, point could and social networks. Current filters in graph CNNs are built for fixed and shared graph structure. However, for most real data, the graph structures varies in both size and connectivity. The paper proposes a generalized and flexible graph CNN taking data of arbitrary graph structure as input. In that way a task-driven adaptive graph is learned for eac...

Magnetic monopole plasma phase in (2+1)d compact quantum electrodynamics with fermionic matter

International Nuclear Information System (INIS)

Armour, Wesley; Hands, Simon; Lucini, Biagio; Kogut, John B.; Strouthos, Costas; Vranas, Pavlos

2011-01-01

We present the first evidence from lattice simulations that the magnetic monopoles in three-dimensional compact quantum electrodynamics (cQED 3 ) with N f =2 and N f =4 four-component fermion flavors are in a plasma phase. The evidence is based mainly on the divergence of the monopole susceptibility (polarizability) with the lattice size at weak gauge couplings. A weak four-Fermi term added to the cQED 3 action enabled simulations with massless fermions. The exact chiral symmetry of the interaction terms forbids symmetry breaking lattice discretization counterterms to appear in the theory's effective action. It is also shown that the scenario of a monopole plasma does not depend on the strength of the four-Fermi coupling. Other observables such as the densities of isolated dipoles and monopoles and the so-called specific heat show that a crossover from a dense monopole plasma to a dilute monopole gas occurs at strong couplings. The implications of our results on the stability of U(1) spin liquids in two spatial dimensions are also discussed.

Asymptote Misconception on Graphing Functions: Does Graphing Software Resolve It?

Directory of Open Access Journals (Sweden)

Mehmet Fatih Öçal

2017-01-01

Full Text Available Graphing function is an important issue in mathematics education due to its use in various areas of mathematics and its potential roles for students to enhance learning mathematics. The use of some graphing software assists students’ learning during graphing functions. However, the display of graphs of functions that students sketched by hand may be relatively different when compared to the correct forms sketched using graphing software. The possible misleading effects of this situation brought a discussion of a misconception (asymptote misconception on graphing functions. The purpose of this study is two- fold. First of all, this study investigated whether using graphing software (GeoGebra in this case helps students to determine and resolve this misconception in calculus classrooms. Second, the reasons for this misconception are sought. The multiple case study was utilized in this study. University students in two calculus classrooms who received instructions with (35 students or without GeoGebra assisted instructions (32 students were compared according to whether they fell into this misconception on graphing basic functions (1/x, lnx, ex. In addition, students were interviewed to reveal the reasons behind this misconception. Data were analyzed by means of descriptive and content analysis methods. The findings indicated that those who received GeoGebra assisted instruction were better in resolving it. In addition, the reasons behind this misconception were found to be teacher-based, exam-based and some other factors.

High Dimensional Spectral Graph Theory and Non-backtracking Random Walks on Graphs

Science.gov (United States)

Kempton, Mark

This thesis has two primary areas of focus. First we study connection graphs, which are weighted graphs in which each edge is associated with a d-dimensional rotation matrix for some fixed dimension d, in addition to a scalar weight. Second, we study non-backtracking random walks on graphs, which are random walks with the additional constraint that they cannot return to the immediately previous state at any given step. Our work in connection graphs is centered on the notion of consistency, that is, the product of rotations moving from one vertex to another is independent of the path taken, and a generalization called epsilon-consistency. We present higher dimensional versions of the combinatorial Laplacian matrix and normalized Laplacian matrix from spectral graph theory, and give results characterizing the consistency of a connection graph in terms of the spectra of these matrices. We generalize several tools from classical spectral graph theory, such as PageRank and effective resistance, to apply to connection graphs. We use these tools to give algorithms for sparsification, clustering, and noise reduction on connection graphs. In non-backtracking random walks, we address the question raised by Alon et. al. concerning how the mixing rate of a non-backtracking random walk to its stationary distribution compares to the mixing rate for an ordinary random walk. Alon et. al. address this question for regular graphs. We take a different approach, and use a generalization of Ihara's Theorem to give a new proof of Alon's result for regular graphs, and to extend the result to biregular graphs. Finally, we give a non-backtracking version of Polya's Random Walk Theorem for 2-dimensional grids.

X-Graphs: Language and Algorithms for Heterogeneous Graph Streams

Science.gov (United States)

2017-09-01

are widely used by academia and industry. 15. SUBJECT TERMS Data Analytics, Graph Analytics, High-Performance Computing 16. SECURITY CLASSIFICATION...form the core of the DeepDive Knowledge Construction System. 2 INTRODUCTION The goal of the X-Graphs project was to develop computational techniques...memory multicore machine. Ringo is based on Snap.py and SNAP, and uses Python . Ringo now allows the integration of Delite DSL Framework Graph

On the sizes of expander graphs and minimum distances of graph codes

DEFF Research Database (Denmark)

Høholdt, Tom; Justesen, Jørn

2014-01-01

We give lower bounds for the minimum distances of graph codes based on expander graphs. The bounds depend only on the second eigenvalue of the graph and the parameters of the component codes. We also give an upper bound on the size of a degree regular graph with given second eigenvalue....

Similarity Measure of Graphs

Directory of Open Access Journals (Sweden)

Amine Labriji

2017-07-01

Full Text Available The topic of identifying the similarity of graphs was considered as highly recommended research field in the Web semantic, artificial intelligence, the shape recognition and information research. One of the fundamental problems of graph databases is finding similar graphs to a graph query. Existing approaches dealing with this problem are usually based on the nodes and arcs of the two graphs, regardless of parental semantic links. For instance, a common connection is not identified as being part of the similarity of two graphs in cases like two graphs without common concepts, the measure of similarity based on the union of two graphs, or the one based on the notion of maximum common sub-graph (SCM, or the distance of edition of graphs. This leads to an inadequate situation in the context of information research. To overcome this problem, we suggest a new measure of similarity between graphs, based on the similarity measure of Wu and Palmer. We have shown that this new measure satisfies the properties of a measure of similarities and we applied this new measure on examples. The results show that our measure provides a run time with a gain of time compared to existing approaches. In addition, we compared the relevance of the similarity values obtained, it appears that this new graphs measure is advantageous and  offers a contribution to solving the problem mentioned above.

Notes on the quantum tetrahedron

CERN Document Server

Coquereaux, Robert

2002-01-01

This is a set of notes describing several aspects of the space of paths on ADE Dynkin diagrams, with a particular attention paid to the graph E6. Many results originally due to A. Ocneanu are here described in a very elementary way (manipulation of square or rectangular matrices). We define the concept of essential matrices for a graph and describe their module properties with respect to right and left actions of fusion algebras. In the case of the graph E6, essential matrices build up a right module with respect to its fusion algebra but a left module with respect to the fusion algebra of A11. We present two original results: 1) We show how to recover the Ocneanu graph of quantum symmetries of the Dynkin diagram E6 from the natural multiplication defined in the tensor square of its fusion algebra (the tensor product should be taken over a particular subalgebra); this is the Cayley graph for the two generators of the twelve dimensional algebra (E6 \\otimes_A3 E6); here A3 and E6 refer to the commutative fusion...

Spectra of Graphs

NARCIS (Netherlands)

Brouwer, A.E.; Haemers, W.H.

2012-01-01

This book gives an elementary treatment of the basic material about graph spectra, both for ordinary, and Laplace and Seidel spectra. The text progresses systematically, by covering standard topics before presenting some new material on trees, strongly regular graphs, two-graphs, association

Quantum red-green-blue image steganography

Science.gov (United States)

Heidari, Shahrokh; Pourarian, Mohammad Rasoul; Gheibi, Reza; Naseri, Mosayeb; Houshmand, Monireh

One of the most considering matters in the field of quantum information processing is quantum data hiding including quantum steganography and quantum watermarking. This field is an efficient tool for protecting any kind of digital data. In this paper, three quantum color images steganography algorithms are investigated based on Least Significant Bit (LSB). The first algorithm employs only one of the image’s channels to cover secret data. The second procedure is based on LSB XORing technique, and the last algorithm utilizes two channels to cover the color image for hiding secret quantum data. The performances of the proposed schemes are analyzed by using software simulations in MATLAB environment. The analysis of PSNR, BER and Histogram graphs indicate that the presented schemes exhibit acceptable performances and also theoretical analysis demonstrates that the networks complexity of the approaches scales squarely.

On middle cube graphs

Directory of Open Access Journals (Sweden)

C. Dalfo

2015-10-01

Full Text Available We study a family of graphs related to the $n$-cube. The middle cube graph of parameter k is the subgraph of $Q_{2k-1}$ induced by the set of vertices whose binary representation has either $k-1$ or $k$ number of ones. The middle cube graphs can be obtained from the well-known odd graphs by doubling their vertex set. Here we study some of the properties of the middle cube graphs in the light of the theory of distance-regular graphs. In particular, we completely determine their spectra (eigenvalues and their multiplicities, and associated eigenvectors.

Graph visualization (Invited talk)

NARCIS (Netherlands)

Wijk, van J.J.; Kreveld, van M.J.; Speckmann, B.

2012-01-01

Black and white node link diagrams are the classic method to depict graphs, but these often fall short to give insight in large graphs or when attributes of nodes and edges play an important role. Graph visualization aims obtaining insight in such graphs using interactive graphical representations.

Adventures in graph theory

CERN Document Server

Joyner, W David

2017-01-01

This textbook acts as a pathway to higher mathematics by seeking and illuminating the connections between graph theory and diverse fields of mathematics, such as calculus on manifolds, group theory, algebraic curves, Fourier analysis, cryptography and other areas of combinatorics. An overview of graph theory definitions and polynomial invariants for graphs prepares the reader for the subsequent dive into the applications of graph theory. To pique the reader’s interest in areas of possible exploration, recent results in mathematics appear throughout the book, accompanied with examples of related graphs, how they arise, and what their valuable uses are. The consequences of graph theory covered by the authors are complicated and far-reaching, so topics are always exhibited in a user-friendly manner with copious graphs, exercises, and Sage code for the computation of equations. Samples of the book’s source code can be found at github.com/springer-math/adventures-in-graph-theory. The text is geared towards ad...

Distance-regular graphs

NARCIS (Netherlands)

van Dam, Edwin R.; Koolen, Jack H.; Tanaka, Hajime

2016-01-01

This is a survey of distance-regular graphs. We present an introduction to distance-regular graphs for the reader who is unfamiliar with the subject, and then give an overview of some developments in the area of distance-regular graphs since the monograph 'BCN'[Brouwer, A.E., Cohen, A.M., Neumaier,

Fractional quantum mechanics on networks: Long-range dynamics and quantum transport.

Science.gov (United States)

Riascos, A P; Mateos, José L

2015-11-01

In this paper we study the quantum transport on networks with a temporal evolution governed by the fractional Schrödinger equation. We generalize the dynamics based on continuous-time quantum walks, with transitions to nearest neighbors on the network, to the fractional case that allows long-range displacements. By using the fractional Laplacian matrix of a network, we establish a formalism that combines a long-range dynamics with the quantum superposition of states; this general approach applies to any type of connected undirected networks, including regular, random, and complex networks, and can be implemented from the spectral properties of the Laplacian matrix. We study the fractional dynamics and its capacity to explore the network by means of the transition probability, the average probability of return, and global quantities that characterize the efficiency of this quantum process. As a particular case, we explore analytically these quantities for circulant networks such as rings, interacting cycles, and complete graphs.

On the strong metric dimension of generalized butterfly graph, starbarbell graph, and {C}_{m}\\odot {P}_{n} graph

Science.gov (United States)

Yunia Mayasari, Ratih; Atmojo Kusmayadi, Tri

2018-04-01

Let G be a connected graph with vertex set V(G) and edge set E(G). For every pair of vertices u,v\\in V(G), the interval I[u, v] between u and v to be the collection of all vertices that belong to some shortest u ‑ v path. A vertex s\\in V(G) strongly resolves two vertices u and v if u belongs to a shortest v ‑ s path or v belongs to a shortest u ‑ s path. A vertex set S of G is a strong resolving set of G if every two distinct vertices of G are strongly resolved by some vertex of S. The strong metric basis of G is a strong resolving set with minimal cardinality. The strong metric dimension sdim(G) of a graph G is defined as the cardinality of strong metric basis. In this paper we determine the strong metric dimension of a generalized butterfly graph, starbarbell graph, and {C}mȯ {P}n graph. We obtain the strong metric dimension of generalized butterfly graph is sdim(BFn ) = 2n ‑ 2. The strong metric dimension of starbarbell graph is sdim(S{B}{m1,{m}2,\\ldots,{m}n})={\\sum }i=1n({m}i-1)-1. The strong metric dimension of {C}mȯ {P}n graph are sdim({C}mȯ {P}n)=2m-1 for m > 3 and n = 2, and sdim({C}mȯ {P}n)=2m-2 for m > 3 and n > 2.

Subgraph detection using graph signals

KAUST Repository

Chepuri, Sundeep Prabhakar

2017-03-06

In this paper we develop statistical detection theory for graph signals. In particular, given two graphs, namely, a background graph that represents an usual activity and an alternative graph that represents some unusual activity, we are interested in answering the following question: To which of the two graphs does the observed graph signal fit the best? To begin with, we assume both the graphs are known, and derive an optimal Neyman-Pearson detector. Next, we derive a suboptimal detector for the case when the alternative graph is not known. The developed theory is illustrated with numerical experiments.

Subgraph detection using graph signals

KAUST Repository

Chepuri, Sundeep Prabhakar; Leus, Geert

2017-01-01

In this paper we develop statistical detection theory for graph signals. In particular, given two graphs, namely, a background graph that represents an usual activity and an alternative graph that represents some unusual activity, we are interested in answering the following question: To which of the two graphs does the observed graph signal fit the best? To begin with, we assume both the graphs are known, and derive an optimal Neyman-Pearson detector. Next, we derive a suboptimal detector for the case when the alternative graph is not known. The developed theory is illustrated with numerical experiments.

Quantum privacy and Schur product channels

Science.gov (United States)

Levick, Jeremy; Kribs, David W.; Pereira, Rajesh

2017-12-01

We investigate the quantum privacy properties of an important class of quantum channels, by making use of a connection with Schur product matrix operations and associated correlation matrix structures. For channels implemented by mutually commuting unitaries, which cannot privatise qubits encoded directly into subspaces, we nevertheless identify private algebras and subsystems that can be privatised by the channels. We also obtain further results by combining our analysis with tools from the theory of quasi-orthogonal operator algebras and graph theory.

Graph spectrum

NARCIS (Netherlands)

Brouwer, A.E.; Haemers, W.H.; Brouwer, A.E.; Haemers, W.H.

2012-01-01

This chapter presents some simple results on graph spectra.We assume the reader is familiar with elementary linear algebra and graph theory. Throughout, J will denote the all-1 matrix, and 1 is the all-1 vector.

Locality for quantum systems on graphs depends on the number field

Science.gov (United States)

Hall, H. Tracy; Severini, Simone

2013-07-01

Adapting a definition of Aaronson and Ambainis (2005 Theory Comput. 1 47-79), we call a quantum dynamics on a digraph saturated Z-local if the nonzero transition amplitudes specifying the unitary evolution are in exact correspondence with the directed edges (including loops) of the digraph. This idea appears recurrently in a variety of contexts including angular momentum, quantum chaos, and combinatorial matrix theory. Complete characterization of the digraph properties that allow such a process to exist is a long-standing open question that can also be formulated in terms of minimum rank problems. We prove that saturated Z-local dynamics involving complex amplitudes occur on a proper superset of the digraphs that allow restriction to the real numbers or, even further, the rationals. Consequently, among these fields, complex numbers guarantee the largest possible choice of topologies supporting a discrete quantum evolution. A similar construction separates complex numbers from the skew field of quaternions. The result proposes a concrete ground for distinguishing between complex and quaternionic quantum mechanics.

Locality for quantum systems on graphs depends on the number field

International Nuclear Information System (INIS)

Hall, H Tracy; Severini, Simone

2013-01-01

Adapting a definition of Aaronson and Ambainis (2005 Theory Comput. 1 47–79), we call a quantum dynamics on a digraph saturated Z-local if the nonzero transition amplitudes specifying the unitary evolution are in exact correspondence with the directed edges (including loops) of the digraph. This idea appears recurrently in a variety of contexts including angular momentum, quantum chaos, and combinatorial matrix theory. Complete characterization of the digraph properties that allow such a process to exist is a long-standing open question that can also be formulated in terms of minimum rank problems. We prove that saturated Z-local dynamics involving complex amplitudes occur on a proper superset of the digraphs that allow restriction to the real numbers or, even further, the rationals. Consequently, among these fields, complex numbers guarantee the largest possible choice of topologies supporting a discrete quantum evolution. A similar construction separates complex numbers from the skew field of quaternions. The result proposes a concrete ground for distinguishing between complex and quaternionic quantum mechanics. (paper)

On the photonic implementation of universal quantum gates, bell states preparation circuit and quantum LDPC encoders and decoders based on directional couplers and HNLF.

Science.gov (United States)

Djordjevic, Ivan B

2010-04-12

The Bell states preparation circuit is a basic circuit required in quantum teleportation. We describe how to implement it in all-fiber technology. The basic building blocks for its implementation are directional couplers and highly nonlinear optical fiber (HNLF). Because the quantum information processing is based on delicate superposition states, it is sensitive to quantum errors. In order to enable fault-tolerant quantum computing the use of quantum error correction is unavoidable. We show how to implement in all-fiber technology encoders and decoders for sparse-graph quantum codes, and provide an illustrative example to demonstrate this implementation. We also show that arbitrary set of universal quantum gates can be implemented based on directional couplers and HNLFs.

Stepping out of homogeneity in loop quantum cosmology

International Nuclear Information System (INIS)

Rovelli, Carlo; Vidotto, Francesca

2008-01-01

We explore the extension of quantum cosmology outside the homogeneous approximation using the formalism of loop quantum gravity. We introduce a model where some of the inhomogeneous degrees of freedom are present, providing a tool for describing general fluctuations of quantum geometry near the initial singularity. We show that the dynamical structure of the model reduces to that of loop quantum cosmology in the Born-Oppenheimer approximation. This result corroborates the assumptions that ground loop cosmology sheds some light on the physical and mathematical relation between loop cosmology and full loop quantum gravity, and on the nature of the cosmological approximation. Finally, we show that the non-graph-changing Hamiltonian constraint considered in the context of algebraic quantum gravity provides a viable effective dynamics within this approximation

Quantum Groups, Property (T), and Weak Mixing

Science.gov (United States)

Brannan, Michael; Kerr, David

2018-06-01

For second countable discrete quantum groups, and more generally second countable locally compact quantum groups with trivial scaling group, we show that property (T) is equivalent to every weakly mixing unitary representation not having almost invariant vectors. This is a generalization of a theorem of Bekka and Valette from the group setting and was previously established in the case of low dual by Daws, Skalski, and Viselter. Our approach uses spectral techniques and is completely different from those of Bekka-Valette and Daws-Skalski-Viselter. By a separate argument we furthermore extend the result to second countable nonunimodular locally compact quantum groups, which are shown in particular not to have property (T), generalizing a theorem of Fima from the discrete setting. We also obtain quantum group versions of characterizations of property (T) of Kerr and Pichot in terms of the Baire category theory of weak mixing representations and of Connes and Weiss in terms of the prevalence of strongly ergodic actions.

Pragmatic Graph Rewriting Modifications

OpenAIRE

Rodgers, Peter; Vidal, Natalia

1999-01-01

We present new pragmatic constructs for easing programming in visual graph rewriting programming languages. The first is a modification to the rewriting process for nodes the host graph, where nodes specified as 'Once Only' in the LHS of a rewrite match at most once with a corresponding node in the host graph. This reduces the previously common use of tags to indicate the progress of matching in the graph. The second modification controls the application of LHS graphs, where those specified a...

Simplicial complexes of graphs

CERN Document Server

Jonsson, Jakob

2008-01-01

A graph complex is a finite family of graphs closed under deletion of edges. Graph complexes show up naturally in many different areas of mathematics, including commutative algebra, geometry, and knot theory. Identifying each graph with its edge set, one may view a graph complex as a simplicial complex and hence interpret it as a geometric object. This volume examines topological properties of graph complexes, focusing on homotopy type and homology. Many of the proofs are based on Robin Forman's discrete version of Morse theory. As a byproduct, this volume also provides a loosely defined toolbox for attacking problems in topological combinatorics via discrete Morse theory. In terms of simplicity and power, arguably the most efficient tool is Forman's divide and conquer approach via decision trees; it is successfully applied to a large number of graph and digraph complexes.

The STAPL Parallel Graph Library

KAUST Repository

Harshvardhan,

2013-01-01

This paper describes the stapl Parallel Graph Library, a high-level framework that abstracts the user from data-distribution and parallelism details and allows them to concentrate on parallel graph algorithm development. It includes a customizable distributed graph container and a collection of commonly used parallel graph algorithms. The library introduces pGraph pViews that separate algorithm design from the container implementation. It supports three graph processing algorithmic paradigms, level-synchronous, asynchronous and coarse-grained, and provides common graph algorithms based on them. Experimental results demonstrate improved scalability in performance and data size over existing graph libraries on more than 16,000 cores and on internet-scale graphs containing over 16 billion vertices and 250 billion edges. © Springer-Verlag Berlin Heidelberg 2013.

Group field theories for all loop quantum gravity

Science.gov (United States)

Oriti, Daniele; Ryan, James P.; Thürigen, Johannes

2015-02-01

Group field theories represent a second quantized reformulation of the loop quantum gravity state space and a completion of the spin foam formalism. States of the canonical theory, in the traditional continuum setting, have support on graphs of arbitrary valence. On the other hand, group field theories have usually been defined in a simplicial context, thus dealing with a restricted set of graphs. In this paper, we generalize the combinatorics of group field theories to cover all the loop quantum gravity state space. As an explicit example, we describe the group field theory formulation of the KKL spin foam model, as well as a particular modified version. We show that the use of tensor model tools allows for the most effective construction. In order to clarify the mathematical basis of our construction and of the formalisms with which we deal, we also give an exhaustive description of the combinatorial structures entering spin foam models and group field theories, both at the level of the boundary states and of the quantum amplitudes.

Topic Model for Graph Mining.

Science.gov (United States)

Xuan, Junyu; Lu, Jie; Zhang, Guangquan; Luo, Xiangfeng

2015-12-01

Graph mining has been a popular research area because of its numerous application scenarios. Many unstructured and structured data can be represented as graphs, such as, documents, chemical molecular structures, and images. However, an issue in relation to current research on graphs is that they cannot adequately discover the topics hidden in graph-structured data which can be beneficial for both the unsupervised learning and supervised learning of the graphs. Although topic models have proved to be very successful in discovering latent topics, the standard topic models cannot be directly applied to graph-structured data due to the "bag-of-word" assumption. In this paper, an innovative graph topic model (GTM) is proposed to address this issue, which uses Bernoulli distributions to model the edges between nodes in a graph. It can, therefore, make the edges in a graph contribute to latent topic discovery and further improve the accuracy of the supervised and unsupervised learning of graphs. The experimental results on two different types of graph datasets show that the proposed GTM outperforms the latent Dirichlet allocation on classification by using the unveiled topics of these two models to represent graphs.

Modern graph theory

CERN Document Server

Bollobás, Béla

1998-01-01

The time has now come when graph theory should be part of the education of every serious student of mathematics and computer science, both for its own sake and to enhance the appreciation of mathematics as a whole. This book is an in-depth account of graph theory, written with such a student in mind; it reflects the current state of the subject and emphasizes connections with other branches of pure mathematics. The volume grew out of the author's earlier book, Graph Theory -- An Introductory Course, but its length is well over twice that of its predecessor, allowing it to reveal many exciting new developments in the subject. Recognizing that graph theory is one of several courses competing for the attention of a student, the book contains extensive descriptive passages designed to convey the flavor of the subject and to arouse interest. In addition to a modern treatment of the classical areas of graph theory such as coloring, matching, extremal theory, and algebraic graph theory, the book presents a detailed ...

A graph edit dictionary for correcting errors in roof topology graphs reconstructed from point clouds

Science.gov (United States)

Xiong, B.; Oude Elberink, S.; Vosselman, G.

2014-07-01

In the task of 3D building model reconstruction from point clouds we face the problem of recovering a roof topology graph in the presence of noise, small roof faces and low point densities. Errors in roof topology graphs will seriously affect the final modelling results. The aim of this research is to automatically correct these errors. We define the graph correction as a graph-to-graph problem, similar to the spelling correction problem (also called the string-to-string problem). The graph correction is more complex than string correction, as the graphs are 2D while strings are only 1D. We design a strategy based on a dictionary of graph edit operations to automatically identify and correct the errors in the input graph. For each type of error the graph edit dictionary stores a representative erroneous subgraph as well as the corrected version. As an erroneous roof topology graph may contain several errors, a heuristic search is applied to find the optimum sequence of graph edits to correct the errors one by one. The graph edit dictionary can be expanded to include entries needed to cope with errors that were previously not encountered. Experiments show that the dictionary with only fifteen entries already properly corrects one quarter of erroneous graphs in about 4500 buildings, and even half of the erroneous graphs in one test area, achieving as high as a 95% acceptance rate of the reconstructed models.

ASCR Workshop on Quantum Computing for Science

Energy Technology Data Exchange (ETDEWEB)

Aspuru-Guzik, Alan [Sandia National Lab. (SNL-NM), Albuquerque, NM (United States); Van Dam, Wim [Sandia National Lab. (SNL-NM), Albuquerque, NM (United States); Farhi, Edward [Sandia National Lab. (SNL-NM), Albuquerque, NM (United States); Gaitan, Frank [Sandia National Lab. (SNL-NM), Albuquerque, NM (United States); Humble, Travis [Sandia National Lab. (SNL-NM), Albuquerque, NM (United States); Jordan, Stephen [Sandia National Lab. (SNL-NM), Albuquerque, NM (United States); Landahl, Andrew J [Sandia National Lab. (SNL-NM), Albuquerque, NM (United States); Love, Peter [Sandia National Lab. (SNL-NM), Albuquerque, NM (United States); Lucas, Robert [Sandia National Lab. (SNL-NM), Albuquerque, NM (United States); Preskill, John [Sandia National Lab. (SNL-NM), Albuquerque, NM (United States); Muller, Richard P. [Sandia National Lab. (SNL-NM), Albuquerque, NM (United States); Svore, Krysta [Sandia National Lab. (SNL-NM), Albuquerque, NM (United States); Wiebe, Nathan [Sandia National Lab. (SNL-NM), Albuquerque, NM (United States); Williams, Carl [Sandia National Lab. (SNL-NM), Albuquerque, NM (United States)

2015-06-01

This report details the findings of the DOE ASCR Workshop on Quantum Computing for Science that was organized to assess the viability of quantum computing technologies to meet the computational requirements of the DOE’s science and energy mission, and to identify the potential impact of quantum technologies. The workshop was held on February 17-18, 2015, in Bethesda, MD, to solicit input from members of the quantum computing community. The workshop considered models of quantum computation and programming environments, physical science applications relevant to DOE's science mission as well as quantum simulation, and applied mathematics topics including potential quantum algorithms for linear algebra, graph theory, and machine learning. This report summarizes these perspectives into an outlook on the opportunities for quantum computing to impact problems relevant to the DOE’s mission as well as the additional research required to bring quantum computing to the point where it can have such impact.

Exponential energy growth due to slow parameter oscillations in quantum mechanical systems.

Science.gov (United States)

Turaev, Dmitry

2016-05-01

It is shown that a periodic emergence and destruction of an additional quantum number leads to an exponential growth of energy of a quantum mechanical system subjected to a slow periodic variation of parameters. The main example is given by systems (e.g., quantum billiards and quantum graphs) with periodically divided configuration space. In special cases, the process can also lead to a long period of cooling that precedes the acceleration, and to the desertion of the states with a particular value of the quantum number.

Graph Generator Survey

Energy Technology Data Exchange (ETDEWEB)

Lothian, Joshua [Oak Ridge National Lab. (ORNL), Oak Ridge, TN (United States); Powers, Sarah S. [Oak Ridge National Lab. (ORNL), Oak Ridge, TN (United States); Sullivan, Blair D. [Oak Ridge National Lab. (ORNL), Oak Ridge, TN (United States); Baker, Matthew B. [Oak Ridge National Lab. (ORNL), Oak Ridge, TN (United States); Schrock, Jonathan [Oak Ridge National Lab. (ORNL), Oak Ridge, TN (United States); Poole, Stephen W. [Oak Ridge National Lab. (ORNL), Oak Ridge, TN (United States)

2013-10-01

The benchmarking effort within the Extreme Scale Systems Center at Oak Ridge National Laboratory seeks to provide High Performance Computing benchmarks and test suites of interest to the DoD sponsor. The work described in this report is a part of the effort focusing on graph generation. A previously developed benchmark, SystemBurn, allowed the emulation of different application behavior profiles within a single framework. To complement this effort, similar capabilities are desired for graph-centric problems. This report examines existing synthetic graph generator implementations in preparation for further study on the properties of their generated synthetic graphs.

Functions and graphs

CERN Document Server

Gelfand, I M; Shnol, E E

1969-01-01

The second in a series of systematic studies by a celebrated mathematician I. M. Gelfand and colleagues, this volume presents students with a well-illustrated sequence of problems and exercises designed to illuminate the properties of functions and graphs. Since readers do not have the benefit of a blackboard on which a teacher constructs a graph, the authors abandoned the customary use of diagrams in which only the final form of the graph appears; instead, the book's margins feature step-by-step diagrams for the complete construction of each graph. The first part of the book employs simple fu

Loose Graph Simulations

DEFF Research Database (Denmark)

Mansutti, Alessio; Miculan, Marino; Peressotti, Marco

2017-01-01

We introduce loose graph simulations (LGS), a new notion about labelled graphs which subsumes in an intuitive and natural way subgraph isomorphism (SGI), regular language pattern matching (RLPM) and graph simulation (GS). Being a unification of all these notions, LGS allows us to express directly...... also problems which are “mixed” instances of previous ones, and hence which would not fit easily in any of them. After the definition and some examples, we show that the problem of finding loose graph simulations is NP-complete, we provide formal translation of SGI, RLPM, and GS into LGSs, and we give...

Quantum quasi-cyclic low-density parity-check error-correcting codes

International Nuclear Information System (INIS)

Yuan, Li; Gui-Hua, Zeng; Lee, Moon Ho

2009-01-01

In this paper, we propose the approach of employing circulant permutation matrices to construct quantum quasicyclic (QC) low-density parity-check (LDPC) codes. Using the proposed approach one may construct some new quantum codes with various lengths and rates of no cycles-length 4 in their Tanner graphs. In addition, these constructed codes have the advantages of simple implementation and low-complexity encoding. Finally, the decoding approach for the proposed quantum QC LDPC is investigated. (general)

Universal quantum computation by scattering in the Fermi–Hubbard model

International Nuclear Information System (INIS)

Bao, Ning; Hayden, Patrick; Salton, Grant; Thomas, Nathaniel

2015-01-01

The Hubbard model may be the simplest model of particles interacting on a lattice, but simulation of its dynamics remains beyond the reach of current numerical methods. In this article, we show that general quantum computations can be encoded into the physics of wave packets propagating through a planar graph, with scattering interactions governed by the fermionic Hubbard model. Therefore, simulating the model on planar graphs is as hard as simulating quantum computation. We give two different arguments, demonstrating that the simulation is difficult both for wave packets prepared as excitations of the fermionic vacuum, and for hole wave packets at filling fraction one-half in the limit of strong coupling. In the latter case, which is described by the t-J model, there is only reflection and no transmission in the scattering events, as would be the case for classical hard spheres. In that sense, the construction provides a quantum mechanical analog of the Fredkin–Toffoli billiard ball computer. (paper)

Practical free space quantum cryptography

International Nuclear Information System (INIS)

Schmitt-Manderbach, T.; Weier, H.; Regner, N.; Kurtsiefer, C.; Weinfurter, H.

2005-01-01

Full text: Quantum cryptography, the secure key distribution between two parties, is the first practical application of quantum information technology. By encoding digital information into different polarization states of single photons, a string of key bits can be established between two parties, where laws of quantum mechanics ensure that a possible eavesdropper has negligible knowledge of. Having shown the feasibility of a long distance quantum key distribution scheme, the emphasis of this work is to incorporate the previously developed compact sender and receiver modules into a quantum cryptography system suitable for every-day use in metropolitan areas. The permanent installation with automatic alignment allows to investigate in detail the sensitivity of the free space optical link to weather conditions and air turbulences commonly encountered in urban areas. We report on a successful free space quantum cryptography experiment over a distance of 500 m between the rooftops of two university buildings using the BB84 protocol. The obtained bit error rates in first runs of this experiment using faint coherent pulses with an average photon number ranging from 0.1 to 1.0 was measured to be below 3 percent for experiments carried out during night, leading to average raw key rates (before error correction and privacy amplification) of 50 kBits per second. Thanks to its simplicity of implementation, our experiment brings free space quantum key distribution a big step closer to practical usability in metropolitan networks and on a level with fibre-based quantum cryptography that up to now offers the only ready-to-use systems available. Compact and automated free space hardware is also a prerequisite for a possible earth-satellite quantum key distribution system in order to break the distance limit of about 100 km of current quantum cryptography schemes. (author)

Bicovariant quantum algebras and quantum Lie algebras

International Nuclear Information System (INIS)

Schupp, P.; Watts, P.; Zumino, B.

1993-01-01

A bicovariant calculus of differential operators on a quantum group is constructed in a natural way, using invariant maps from Fun(G q ) to U q g, given by elements of the pure braid group. These operators - the 'reflection matrix' Y= triple bond L + SL - being a special case - generate algebras that linearly close under adjoint actions, i.e. they form generalized Lie algebras. We establish the connection between the Hopf algebra formulation of the calculus and a formulation in compact matrix form which is quite powerful for actual computations and as applications we find the quantum determinant and an orthogonality relation for Y in SO q (N). (orig.)

Combinatorial and geometric aspects of Feynman graphs and Feynman integrals

Energy Technology Data Exchange (ETDEWEB)

Bergbauer, Christoph

2009-06-11

The integrals associated to Feynman graphs must have been a source of frustration for particle physicists ever since. Indeed there is a delicate difference between being able to draw a Feynman graph and being able to compute the associated Feynman integral. Although perturbation theory has brought enormous breakthroughs, many physicists turned to more abstract developments in quantum field theory, looked for other ways to produce perturbational results, or left the field entirely. Nonetheless there is a significant number of physicists, computational and theoretical, who pursue the quest for concepts and algorithms to compute and understand those integrals to higher and higher orders. Their motivation is to help test the validity of the underlying physical theory. For a mathematician, Feynman graphs and their integrals provide a rich subject in their own right, independent of their computability. It was only recently though that the work of Bloch, Esnault and Kreimer has brought a growing interest of mathematicians from various disciplines to the subject. In fact it opened up a completely new direction of research: a motivic interpretation of Feynman graphs that unites their combinatorial, geometric and arithmetic aspects. This idea had been in the air for a while, based on computational results of Broadhurst and Kreimer, and on a theorem of Belkale and Brosnan related to a conjecture of Kontsevich about the generality of the underlying motives. A prerequisite for the motivic approach is a profound understanding of renormalization that was established less recently in a modern language by Connes and Kreimer. This dissertation studies the renormalization of Feynman graphs in position space using an adapted resolution of singularities, and makes two other contributions of mostly combinatorial nature to the subject. I hope this may serve as a reference for somebody who feels comfortable with the traditional position space literature and looks for a transition to the

Combinatorial and geometric aspects of Feynman graphs and Feynman integrals

International Nuclear Information System (INIS)

Bergbauer, Christoph

2009-01-01

The integrals associated to Feynman graphs must have been a source of frustration for particle physicists ever since. Indeed there is a delicate difference between being able to draw a Feynman graph and being able to compute the associated Feynman integral. Although perturbation theory has brought enormous breakthroughs, many physicists turned to more abstract developments in quantum field theory, looked for other ways to produce perturbational results, or left the field entirely. Nonetheless there is a significant number of physicists, computational and theoretical, who pursue the quest for concepts and algorithms to compute and understand those integrals to higher and higher orders. Their motivation is to help test the validity of the underlying physical theory. For a mathematician, Feynman graphs and their integrals provide a rich subject in their own right, independent of their computability. It was only recently though that the work of Bloch, Esnault and Kreimer has brought a growing interest of mathematicians from various disciplines to the subject. In fact it opened up a completely new direction of research: a motivic interpretation of Feynman graphs that unites their combinatorial, geometric and arithmetic aspects. This idea had been in the air for a while, based on computational results of Broadhurst and Kreimer, and on a theorem of Belkale and Brosnan related to a conjecture of Kontsevich about the generality of the underlying motives. A prerequisite for the motivic approach is a profound understanding of renormalization that was established less recently in a modern language by Connes and Kreimer. This dissertation studies the renormalization of Feynman graphs in position space using an adapted resolution of singularities, and makes two other contributions of mostly combinatorial nature to the subject. I hope this may serve as a reference for somebody who feels comfortable with the traditional position space literature and looks for a transition to the

Autoregressive Moving Average Graph Filtering

OpenAIRE

Isufi, Elvin; Loukas, Andreas; Simonetto, Andrea; Leus, Geert

2016-01-01

One of the cornerstones of the field of signal processing on graphs are graph filters, direct analogues of classical filters, but intended for signals defined on graphs. This work brings forth new insights on the distributed graph filtering problem. We design a family of autoregressive moving average (ARMA) recursions, which (i) are able to approximate any desired graph frequency response, and (ii) give exact solutions for tasks such as graph signal denoising and interpolation. The design phi...

Phase Transitions for Quantum XY-Model on the Cayley Tree of Order Three in Quantum Markov Chain Scheme

International Nuclear Information System (INIS)

Mukhamedov, Farrukh; Saburov, Mansoor

2010-06-01

In the present paper we study forward Quantum Markov Chains (QMC) defined on a Cayley tree. Using the tree structure of graphs, we give a construction of quantum Markov chains on a Cayley tree. By means of such constructions we prove the existence of a phase transition for the XY-model on a Cayley tree of order three in QMC scheme. By the phase transition we mean the existence of two distinct QMC for the given family of interaction operators {K }. (author)

Performing quantum computing experiments in the cloud

Science.gov (United States)

Devitt, Simon J.

2016-09-01

Quantum computing technology has reached a second renaissance in the past five years. Increased interest from both the private and public sector combined with extraordinary theoretical and experimental progress has solidified this technology as a major advancement in the 21st century. As anticipated my many, some of the first realizations of quantum computing technology has occured over the cloud, with users logging onto dedicated hardware over the classical internet. Recently, IBM has released the Quantum Experience, which allows users to access a five-qubit quantum processor. In this paper we take advantage of this online availability of actual quantum hardware and present four quantum information experiments. We utilize the IBM chip to realize protocols in quantum error correction, quantum arithmetic, quantum graph theory, and fault-tolerant quantum computation by accessing the device remotely through the cloud. While the results are subject to significant noise, the correct results are returned from the chip. This demonstrates the power of experimental groups opening up their technology to a wider audience and will hopefully allow for the next stage of development in quantum information technology.

On cyclic orthogonal double covers of circulant graphs by special infinite graphs

Directory of Open Access Journals (Sweden)

R. El-Shanawany

2017-12-01

Full Text Available In this article, a technique to construct cyclic orthogonal double covers (CODCs of regular circulant graphs by certain infinite graph classes such as complete bipartite and tripartite graphs and disjoint union of butterfly and K1,2n−10 is introduced.

Holonomy loops, spectral triples and quantum gravity

DEFF Research Database (Denmark)

Johannes, Aastrup; Grimstrup, Jesper Møller; Nest, Ryszard

2009-01-01

We review the motivation, construction and physical interpretation of a semi-finite spectral triple obtained through a rearrangement of central elements of loop quantum gravity. The triple is based on a countable set of oriented graphs and the algebra consists of generalized holonomy loops...

Fundamentals of algebraic graph transformation

CERN Document Server

Ehrig, Hartmut; Prange, Ulrike; Taentzer, Gabriele

2006-01-01

Graphs are widely used to represent structural information in the form of objects and connections between them. Graph transformation is the rule-based manipulation of graphs, an increasingly important concept in computer science and related fields. This is the first textbook treatment of the algebraic approach to graph transformation, based on algebraic structures and category theory. Part I is an introduction to the classical case of graph and typed graph transformation. In Part II basic and advanced results are first shown for an abstract form of replacement systems, so-called adhesive high-level replacement systems based on category theory, and are then instantiated to several forms of graph and Petri net transformation systems. Part III develops typed attributed graph transformation, a technique of key relevance in the modeling of visual languages and in model transformation. Part IV contains a practical case study on model transformation and a presentation of the AGG (attributed graph grammar) tool envir...

Quantum independent increment processes

CERN Document Server

Franz, Uwe

2005-01-01

This volume is the first of two volumes containing the revised and completed notes lectures given at the school "Quantum Independent Increment Processes: Structure and Applications to Physics". This school was held at the Alfried-Krupp-Wissenschaftskolleg in Greifswald during the period March 9 – 22, 2003, and supported by the Volkswagen Foundation. The school gave an introduction to current research on quantum independent increment processes aimed at graduate students and non-specialists working in classical and quantum probability, operator algebras, and mathematical physics. The present first volume contains the following lectures: "Lévy Processes in Euclidean Spaces and Groups" by David Applebaum, "Locally Compact Quantum Groups" by Johan Kustermans, "Quantum Stochastic Analysis" by J. Martin Lindsay, and "Dilations, Cocycles and Product Systems" by B.V. Rajarama Bhat.

Graph-based modelling in engineering

CERN Document Server

Rysiński, Jacek

2017-01-01

This book presents versatile, modern and creative applications of graph theory in mechanical engineering, robotics and computer networks. Topics related to mechanical engineering include e.g. machine and mechanism science, mechatronics, robotics, gearing and transmissions, design theory and production processes. The graphs treated are simple graphs, weighted and mixed graphs, bond graphs, Petri nets, logical trees etc. The authors represent several countries in Europe and America, and their contributions show how different, elegant, useful and fruitful the utilization of graphs in modelling of engineering systems can be. .

Chemical graph-theoretic cluster expansions

International Nuclear Information System (INIS)

Klein, D.J.

1986-01-01

A general computationally amenable chemico-graph-theoretic cluster expansion method is suggested as a paradigm for incorporation of chemical structure concepts in a systematic manner. The cluster expansion approach is presented in a formalism general enough to cover a variety of empirical, semiempirical, and even ab initio applications. Formally such approaches for the utilization of chemical structure-related concepts may be viewed as discrete analogues of Taylor series expansions. The efficacy of the chemical structure concepts then is simply bound up in the rate of convergence of the cluster expansions. In many empirical applications, e.g., boiling points, chromatographic separation coefficients, and biological activities, this rate of convergence has been observed to be quite rapid. More note will be made here of quantum chemical applications. Relations to questions concerning size extensivity of energies and size consistency of wave functions are addressed

BootGraph: probabilistic fiber tractography using bootstrap algorithms and graph theory.

Science.gov (United States)

Vorburger, Robert S; Reischauer, Carolin; Boesiger, Peter

2013-02-01

Bootstrap methods have recently been introduced to diffusion-weighted magnetic resonance imaging to estimate the measurement uncertainty of ensuing diffusion parameters directly from the acquired data without the necessity to assume a noise model. These methods have been previously combined with deterministic streamline tractography algorithms to allow for the assessment of connection probabilities in the human brain. Thereby, the local noise induced disturbance in the diffusion data is accumulated additively due to the incremental progression of streamline tractography algorithms. Graph based approaches have been proposed to overcome this drawback of streamline techniques. For this reason, the bootstrap method is in the present work incorporated into a graph setup to derive a new probabilistic fiber tractography method, called BootGraph. The acquired data set is thereby converted into a weighted, undirected graph by defining a vertex in each voxel and edges between adjacent vertices. By means of the cone of uncertainty, which is derived using the wild bootstrap, a weight is thereafter assigned to each edge. Two path finding algorithms are subsequently applied to derive connection probabilities. While the first algorithm is based on the shortest path approach, the second algorithm takes all existing paths between two vertices into consideration. Tracking results are compared to an established algorithm based on the bootstrap method in combination with streamline fiber tractography and to another graph based algorithm. The BootGraph shows a very good performance in crossing situations with respect to false negatives and permits incorporating additional constraints, such as a curvature threshold. By inheriting the advantages of the bootstrap method and graph theory, the BootGraph method provides a computationally efficient and flexible probabilistic tractography setup to compute connection probability maps and virtual fiber pathways without the drawbacks of

Quantum Teamwork for Unconditional Multiparty Communication with Gaussian States

Science.gov (United States)

Zhang, Jing; Adesso, Gerardo; Xie, Changde; Peng, Kunchi

2009-08-01

We demonstrate the capability of continuous variable Gaussian states to communicate multipartite quantum information. A quantum teamwork protocol is presented according to which an arbitrary possibly entangled multimode state can be faithfully teleported between two teams each comprising many cooperative users. We prove that N-mode Gaussian weighted graph states exist for arbitrary N that enable unconditional quantum teamwork implementations for any arrangement of the teams. These perfect continuous variable maximally multipartite entangled resources are typical among pure Gaussian states and are unaffected by the entanglement frustration occurring in multiqubit states.

Quantum walks with entangled coins

International Nuclear Information System (INIS)

Venegas-Andraca, S E; Ball, J L; Burnett, K; Bose, S

2005-01-01

We present a mathematical formalism for the description of un- restricted quantum walks with entangled coins and one walker. The numerical behaviour of such walks is examined when using a Bell state as the initial coin state, with two different coin operators, two different shift operators, and one walker. We compare and contrast the performance of these quantum walks with that of a classical random walk consisting of one walker and two maximally correlated coins as well as quantum walks with coins sharing different degrees of entanglement. We illustrate that the behaviour of our walk with entangled coins can be very different in comparison to the usual quantum walk with a single coin. We also demonstrate that simply by changing the shift operator, we can generate widely different distributions. We also compare the behaviour of quantum walks with maximally entangled coins with that of quantum walks with non-entangled coins. Finally, we show that the use of different shift operators on two and three qubit coins leads to different position probability distributions in one- and two-dimensional graphs

Multifractal analysis of multiparticle emission data in the framework of visibility graph and sandbox algorithm

Science.gov (United States)

Mali, P.; Manna, S. K.; Mukhopadhyay, A.; Haldar, P. K.; Singh, G.

2018-03-01

Multiparticle emission data in nucleus-nucleus collisions are studied in a graph theoretical approach. The sandbox algorithm used to analyze complex networks is employed to characterize the multifractal properties of the visibility graphs associated with the pseudorapidity distribution of charged particles produced in high-energy heavy-ion collisions. Experimental data on 28Si+Ag/Br interaction at laboratory energy Elab = 14 . 5 A GeV, and 16O+Ag/Br and 32S+Ag/Br interactions both at Elab = 200 A GeV, are used in this analysis. We observe a scale free nature of the degree distributions of the visibility and horizontal visibility graphs associated with the event-wise pseudorapidity distributions. Equivalent event samples simulated by ultra-relativistic quantum molecular dynamics, produce degree distributions that are almost identical to the respective experiment. However, the multifractal variables obtained by using sandbox algorithm for the experiment to some extent differ from the respective simulated results.

Equipackable graphs

DEFF Research Database (Denmark)

Vestergaard, Preben Dahl; Hartnell, Bert L.

2006-01-01

There are many results dealing with the problem of decomposing a fixed graph into isomorphic subgraphs. There has also been work on characterizing graphs with the property that one can delete the edges of a number of edge disjoint copies of the subgraph and, regardless of how that is done, the gr...

Khovanov homology of graph-links

Energy Technology Data Exchange (ETDEWEB)

Nikonov, Igor M [M. V. Lomonosov Moscow State University, Faculty of Mechanics and Mathematics, Moscow (Russian Federation)

2012-08-31

Graph-links arise as the intersection graphs of turning chord diagrams of links. Speaking informally, graph-links provide a combinatorial description of links up to mutations. Many link invariants can be reformulated in the language of graph-links. Khovanov homology, a well-known and useful knot invariant, is defined for graph-links in this paper (in the case of the ground field of characteristic two). Bibliography: 14 titles.

Generalized connectivity of graphs

CERN Document Server

Li, Xueliang

2016-01-01

Noteworthy results, proof techniques, open problems and conjectures in generalized (edge-) connectivity are discussed in this book. Both theoretical and practical analyses for generalized (edge-) connectivity of graphs are provided. Topics covered in this book include: generalized (edge-) connectivity of graph classes, algorithms, computational complexity, sharp bounds, Nordhaus-Gaddum-type results, maximum generalized local connectivity, extremal problems, random graphs, multigraphs, relations with the Steiner tree packing problem and generalizations of connectivity. This book enables graduate students to understand and master a segment of graph theory and combinatorial optimization. Researchers in graph theory, combinatorics, combinatorial optimization, probability, computer science, discrete algorithms, complexity analysis, network design, and the information transferring models will find this book useful in their studies.

Extreme Violation of Local Realism in Quantum Hypergraph States.

Science.gov (United States)

Gachechiladze, Mariami; Budroni, Costantino; Gühne, Otfried

2016-02-19

Hypergraph states form a family of multiparticle quantum states that generalizes the well-known concept of Greenberger-Horne-Zeilinger states, cluster states, and more broadly graph states. We study the nonlocal properties of quantum hypergraph states. We demonstrate that the correlations in hypergraph states can be used to derive various types of nonlocality proofs, including Hardy-type arguments and Bell inequalities for genuine multiparticle nonlocality. Moreover, we show that hypergraph states allow for an exponentially increasing violation of local realism which is robust against loss of particles. Our results suggest that certain classes of hypergraph states are novel resources for quantum metrology and measurement-based quantum computation.

On two energy-like invariants of line graphs and related graph operations

Directory of Open Access Journals (Sweden)

Xiaodan Chen

2016-02-01

Full Text Available Abstract For a simple graph G of order n, let μ 1 ≥ μ 2 ≥ ⋯ ≥ μ n = 0 $\\mu_{1}\\geq\\mu_{2}\\geq\\cdots\\geq\\mu_{n}=0$ be its Laplacian eigenvalues, and let q 1 ≥ q 2 ≥ ⋯ ≥ q n ≥ 0 $q_{1}\\geq q_{2}\\geq\\cdots\\geq q_{n}\\geq0$ be its signless Laplacian eigenvalues. The Laplacian-energy-like invariant and incidence energy of G are defined as, respectively, LEL ( G = ∑ i = 1 n − 1 μ i and IE ( G = ∑ i = 1 n q i . $$\\mathit{LEL}(G=\\sum_{i=1}^{n-1}\\sqrt{ \\mu_{i}} \\quad\\mbox{and}\\quad \\mathit {IE}(G=\\sum_{i=1}^{n} \\sqrt{q_{i}}. $$ In this paper, we present some new upper and lower bounds on LEL and IE of line graph, subdivision graph, para-line graph and total graph of a regular graph, some of which improve previously known results. The main tools we use here are the Cauchy-Schwarz inequality and the Ozeki inequality.

Gravitationally compact objects as nucleation sites for first-order vacuum phase transitions

International Nuclear Information System (INIS)

Samuel, D.A.; Hiscock, W.A.

1992-01-01

A characteristic of first-order phase transitions is their ability to be initiated by nucleation sites. In this paper we consider the role that gravitationally compact objects may play as nucleation sites for first-order phase transitions within quantum fields. As the presence of nucleation sites may prevent the onset of supercooling, the existence of nucleation sites for phase transitions within quantum fields may play an important role in some inflationary models of the Universe, in which the Universe is required to exist in a supercooled state for a period of time. In this paper we calculate the Euclidean action for an O(3) bubble nucleating about a gravitationally compact object, taken to be a boson star for simplicity. The gravitational field of the boson star is taken to be a small perturbation on flat space, and the O(3) action is calculated to linear order as a perturbation on the O(4) action. The Euclidean bubble profile is found by solving the (Higgs) scalar field equation numerically; the thin-wall approximation is not used. The gravitationally compact objects are found to have the effect of reducing the Euclidean action of the nucleating bubble, as compared to the Euclidean action for the bubble in flat spacetime. The effect is strongest when the size of the gravitationally compact object is comparable to the size of the nucleating bubble. Further, the size of the decrease in action increases as the nucleating ''star'' is made more gravitationally compact. Thus, gravitationally compact objects may play the role of nucleation sites. However, their importance to the process of false-vacuum decay is strongly dependent upon their number density within the Universe

Toward a compact fibered squeezing parametric source.

Science.gov (United States)

Brieussel, Alexandre; Ott, Konstantin; Joos, Maxime; Treps, Nicolas; Fabre, Claude

2018-03-15

In this work, we investigate three different compact fibered systems generating vacuum squeezing that involve optical cavities limited by the end surface of a fiber and by a curved mirror and containing a thin parametric crystal. These systems have the advantage to couple squeezed states directly to a fiber, allowing the user to benefit from the flexibility of fibers in the use of squeezing. Three types of fibers are investigated: standard single-mode fibers, photonic-crystal large-mode-area single-mode fibers, and short multimode fibers taped to a single-mode fiber. The observed squeezing is modest (-0.56  dB, -0.9  dB, -1  dB), but these experiments open the way for miniaturized squeezing devices that could be a very interesting advantage in scaling up quantum systems for quantum processing, opening new perspectives in the domain of integrated quantum optics.

Price Competition on Graphs

OpenAIRE

Adriaan R. Soetevent

2010-01-01

This paper extends Hotelling's model of price competition with quadratic transportation costs from a line to graphs. I propose an algorithm to calculate firm-level demand for any given graph, conditional on prices and firm locations. One feature of graph models of price competition is that spatial discontinuities in firm-level demand may occur. I show that the existence result of D'Aspremont et al. (1979) does not extend to simple star graphs. I conjecture that this non-existence result holds...

Price Competition on Graphs

OpenAIRE

Pim Heijnen; Adriaan Soetevent

2014-01-01

This paper extends Hotelling's model of price competition with quadratic transportation costs from a line to graphs. We derive an algorithm to calculate firm-level demand for any given graph, conditional on prices and firm locations. These graph models of price competition may lead to spatial discontinuities in firm-level demand. We show that the existence result of D'Aspremont et al. (1979) does not extend to simple star graphs and conjecture that this non-existence result holds more general...

Skew-adjacency matrices of graphs

NARCIS (Netherlands)

Cavers, M.; Cioaba, S.M.; Fallat, S.; Gregory, D.A.; Haemers, W.H.; Kirkland, S.J.; McDonald, J.J.; Tsatsomeros, M.

2012-01-01

The spectra of the skew-adjacency matrices of a graph are considered as a possible way to distinguish adjacency cospectral graphs. This leads to the following topics: graphs whose skew-adjacency matrices are all cospectral; relations between the matchings polynomial of a graph and the characteristic

Graph theory

CERN Document Server

Diestel, Reinhard

2017-01-01

This standard textbook of modern graph theory, now in its fifth edition, combines the authority of a classic with the engaging freshness of style that is the hallmark of active mathematics. It covers the core material of the subject with concise yet reliably complete proofs, while offering glimpses of more advanced methods in each field by one or two deeper results, again with proofs given in full detail. The book can be used as a reliable text for an introductory course, as a graduate text, and for self-study. From the reviews: “This outstanding book cannot be substituted with any other book on the present textbook market. It has every chance of becoming the standard textbook for graph theory.”Acta Scientiarum Mathematiciarum “Deep, clear, wonderful. This is a serious book about the heart of graph theory. It has depth and integrity. ”Persi Diaconis & Ron Graham, SIAM Review “The book has received a very enthusiastic reception, which it amply deserves. A masterly elucidation of modern graph theo...

Acyclicity in edge-colored graphs

DEFF Research Database (Denmark)

Gutin, Gregory; Jones, Mark; Sheng, Bin

2017-01-01

A walk W in edge-colored graphs is called properly colored (PC) if every pair of consecutive edges in W is of different color. We introduce and study five types of PC acyclicity in edge-colored graphs such that graphs of PC acyclicity of type i is a proper superset of graphs of acyclicity of type i......+1, i=1,2,3,4. The first three types are equivalent to the absence of PC cycles, PC closed trails, and PC closed walks, respectively. While graphs of types 1, 2 and 3 can be recognized in polynomial time, the problem of recognizing graphs of type 4 is, somewhat surprisingly, NP-hard even for 2-edge-colored...... graphs (i.e., when only two colors are used). The same problem with respect to type 5 is polynomial-time solvable for all edge-colored graphs. Using the five types, we investigate the border between intractability and tractability for the problems of finding the maximum number of internally vertex...

Graph Sampling for Covariance Estimation

KAUST Repository

Chepuri, Sundeep Prabhakar

2017-04-25

In this paper the focus is on subsampling as well as reconstructing the second-order statistics of signals residing on nodes of arbitrary undirected graphs. Second-order stationary graph signals may be obtained by graph filtering zero-mean white noise and they admit a well-defined power spectrum whose shape is determined by the frequency response of the graph filter. Estimating the graph power spectrum forms an important component of stationary graph signal processing and related inference tasks such as Wiener prediction or inpainting on graphs. The central result of this paper is that by sampling a significantly smaller subset of vertices and using simple least squares, we can reconstruct the second-order statistics of the graph signal from the subsampled observations, and more importantly, without any spectral priors. To this end, both a nonparametric approach as well as parametric approaches including moving average and autoregressive models for the graph power spectrum are considered. The results specialize for undirected circulant graphs in that the graph nodes leading to the best compression rates are given by the so-called minimal sparse rulers. A near-optimal greedy algorithm is developed to design the subsampling scheme for the non-parametric and the moving average models, whereas a particular subsampling scheme that allows linear estimation for the autoregressive model is proposed. Numerical experiments on synthetic as well as real datasets related to climatology and processing handwritten digits are provided to demonstrate the developed theory.

Price competition on graphs

NARCIS (Netherlands)

Soetevent, A.R.

2010-01-01

This paper extends Hotelling's model of price competition with quadratic transportation costs from a line to graphs. I propose an algorithm to calculate firm-level demand for any given graph, conditional on prices and firm locations. One feature of graph models of price competition is that spatial

Graphing the order of the sexes: constructing, recalling, interpreting, and putting the self in gender difference graphs.

Science.gov (United States)

Hegarty, Peter; Lemieux, Anthony F; McQueen, Grant

2010-03-01

Graphs seem to connote facts more than words or tables do. Consequently, they seem unlikely places to spot implicit sexism at work. Yet, in 6 studies (N = 741), women and men constructed (Study 1) and recalled (Study 2) gender difference graphs with men's data first, and graphed powerful groups (Study 3) and individuals (Study 4) ahead of weaker ones. Participants who interpreted graph order as evidence of author "bias" inferred that the author graphed his or her own gender group first (Study 5). Women's, but not men's, preferences to graph men first were mitigated when participants graphed a difference between themselves and an opposite-sex friend prior to graphing gender differences (Study 6). Graph production and comprehension are affected by beliefs and suppositions about the groups represented in graphs to a greater degree than cognitive models of graph comprehension or realist models of scientific thinking have yet acknowledged.

Collective Rationality in Graph Aggregation

NARCIS (Netherlands)

Endriss, U.; Grandi, U.; Schaub, T.; Friedrich, G.; O'Sullivan, B.

2014-01-01

Suppose a number of agents each provide us with a directed graph over a common set of vertices. Graph aggregation is the problem of computing a single “collective” graph that best represents the information inherent in this profile of individual graphs. We consider this aggregation problem from the

GoFFish: A Sub-Graph Centric Framework for Large-Scale Graph Analytics1

Energy Technology Data Exchange (ETDEWEB)

Simmhan, Yogesh; Kumbhare, Alok; Wickramaarachchi, Charith; Nagarkar, Soonil; Ravi, Santosh; Raghavendra, Cauligi; Prasanna, Viktor

2014-08-25

Large scale graph processing is a major research area for Big Data exploration. Vertex centric programming models like Pregel are gaining traction due to their simple abstraction that allows for scalable execution on distributed systems naturally. However, there are limitations to this approach which cause vertex centric algorithms to under-perform due to poor compute to communication overhead ratio and slow convergence of iterative superstep. In this paper we introduce GoFFish a scalable sub-graph centric framework co-designed with a distributed persistent graph storage for large scale graph analytics on commodity clusters. We introduce a sub-graph centric programming abstraction that combines the scalability of a vertex centric approach with the flexibility of shared memory sub-graph computation. We map Connected Components, SSSP and PageRank algorithms to this model to illustrate its flexibility. Further, we empirically analyze GoFFish using several real world graphs and demonstrate its significant performance improvement, orders of magnitude in some cases, compared to Apache Giraph, the leading open source vertex centric implementation. We map Connected Components, SSSP and PageRank algorithms to this model to illustrate its flexibility. Further, we empirically analyze GoFFish using several real world graphs and demonstrate its significant performance improvement, orders of magnitude in some cases, compared to Apache Giraph, the leading open source vertex centric implementation.

Quantum group symmetry of classical and noncommutative geometry

Indian Academy of Sciences (India)

Debashish Goswami

2016-07-01

Jul 1, 2016 ... universal enveloping algebra U(L) of a Lie algebra L, (iv) ... Kustermans defined locally compact quantum groups too. .... There are other versions of quantum isometries formulated by me ..... classical connected spaces when either the space is ..... Etingof-Walton's paper, we have : (i) M0 is open and dense,.

Graph Theory. 1. Fragmentation of Structural Graphs

Directory of Open Access Journals (Sweden)

Lorentz JÄNTSCHI

2002-12-01

Full Text Available The investigation of structural graphs has many fields of applications in engineering, especially in applied sciences like as applied chemistry and physics, computer sciences and automation, electronics and telecommunication. The main subject of the paper is to express fragmentation criteria in graph using a new method of investigation: terminal paths. Using terminal paths are defined most of the fragmentation criteria that are in use in molecular topology, but the fields of applications are more generally than that, as I mentioned before. Graphical examples of fragmentation are given for every fragmentation criteria. Note that all fragmentation is made with a computer program that implements a routine for every criterion.[1] A web routine for tracing all terminal paths in graph can be found at the address: http://vl.academicdirect.ro/molecular_topology/tpaths/ [1] M. V. Diudea, I. Gutman, L. Jäntschi, Molecular Topology, Nova Science, Commack, New York, 2001, 2002.

Compact and highly stable quantum dots through optimized aqueous phase transfer

Science.gov (United States)

Tamang, Sudarsan; Beaune, Grégory; Poillot, Cathy; De Waard, Michel; Texier-Nogues, Isabelle; Reiss, Peter

2011-03-01

A large number of different approaches for the aqueous phase transfer of quantum dots have been proposed. Surface ligand exchange with small hydrophilic thiols, such as L-cysteine, yields the lowest particle hydrodynamic diameter. However, cysteine is prone to dimer formation, which limits colloidal stability. We demonstrate that precise pH control during aqueous phase transfer dramatically increases the colloidal stability of InP/ZnS quantum dots. Various bifunctional thiols have been applied. The formation of disulfides, strongly diminishing the fluorescence QY has been prevented through addition of appropriate reducing agents. Bright InP/ZnS quantum dots with a hydrodynamic diameter <10 nm and long-term stability have been obtained. Finally we present in vitro studies of the quantum dots functionalized with the cell-penetrating peptide maurocalcine.

Introductory graph theory

CERN Document Server

Chartrand, Gary

1984-01-01

Graph theory is used today in the physical sciences, social sciences, computer science, and other areas. Introductory Graph Theory presents a nontechnical introduction to this exciting field in a clear, lively, and informative style. Author Gary Chartrand covers the important elementary topics of graph theory and its applications. In addition, he presents a large variety of proofs designed to strengthen mathematical techniques and offers challenging opportunities to have fun with mathematics. Ten major topics - profusely illustrated - include: Mathematical Models, Elementary Concepts of Grap

Compact quantum dot-antibody conjugates for FRET immunoassays with subnanomolar detection limits

Science.gov (United States)

Mattera, Lucia; Bhuckory, Shashi; Wegner, K. David; Qiu, Xue; Agnese, Fabio; Lincheneau, Christophe; Senden, Tim; Djurado, David; Charbonnière, Loïc J.; Hildebrandt, Niko; Reiss, Peter

2016-05-01

A novel two-step approach for quantum dot (QD) functionalization and bioconjugation is presented, which yields ultra-compact, stable, and highly luminescent antibody-QD conjugates suitable for use in FRET immunoassays. Hydrophobic InPZnS/ZnSe/ZnS (emission wavelength: 530 nm), CdSe/ZnS (605 nm), and CdSeTe/ZnS (705 nm) QDs were surface functionalized with zwitterionic penicillamine, enabling aqueous phase transfer under conservation of the photoluminescence properties. Post-functionalization with a heterobifunctional crosslinker, containing a lipoic acid group and a maleimide function, enabled the subsequent coupling to sulfhydryl groups of proteins. This was demonstrated by QD conjugation with fragmented antibodies (F(ab)). The obtained F(ab)-QD conjugates range among the smallest antibody-functionalized nanoprobes ever reported, with a hydrodynamic diameter coating for FRET could be demonstrated by an 6.2 and 2.5 fold improvement of the limit of detection (LOD) for PSA compared to commercially available hydrophilic QDs emitting at 605 and 705 nm, respectively. While the commercial QDs contain identical inorganic cores responsible for their fluorescence, they are coated with a comparably thick amphiphilic polymer layer leading to much larger hydrodynamic diameters (>26 nm without biomolecules). The LODs of 0.8 and 3.7 ng mL-1 obtained in 50 μL serum samples are below the clinical cut-off level of PSA (4 ng mL-1) and demonstrate their direct applicability in clinical diagnostics.A novel two-step approach for quantum dot (QD) functionalization and bioconjugation is presented, which yields ultra-compact, stable, and highly luminescent antibody-QD conjugates suitable for use in FRET immunoassays. Hydrophobic InPZnS/ZnSe/ZnS (emission wavelength: 530 nm), CdSe/ZnS (605 nm), and CdSeTe/ZnS (705 nm) QDs were surface functionalized with zwitterionic penicillamine, enabling aqueous phase transfer under conservation of the photoluminescence properties. Post

Creating more effective graphs

CERN Document Server

Robbins, Naomi B

2012-01-01

A succinct and highly readable guide to creating effective graphs The right graph can be a powerful tool for communicating information, improving a presentation, or conveying your point in print. If your professional endeavors call for you to present data graphically, here's a book that can help you do it more effectively. Creating More Effective Graphs gives you the basic knowledge and techniques required to choose and create appropriate graphs for a broad range of applications. Using real-world examples everyone can relate to, the author draws on her years of experience in gr

Graph Compression by BFS

Directory of Open Access Journals (Sweden)

Alberto Apostolico

2009-08-01

Full Text Available The Web Graph is a large-scale graph that does not fit in main memory, so that lossless compression methods have been proposed for it. This paper introduces a compression scheme that combines efficient storage with fast retrieval for the information in a node. The scheme exploits the properties of the Web Graph without assuming an ordering of the URLs, so that it may be applied to more general graphs. Tests on some datasets of use achieve space savings of about 10% over existing methods.

Graphing Inequalities, Connecting Meaning

Science.gov (United States)

Switzer, J. Matt

2014-01-01

Students often have difficulty with graphing inequalities (see Filloy, Rojano, and Rubio 2002; Drijvers 2002), and J. Matt Switzer's students were no exception. Although students can produce graphs for simple inequalities, they often struggle when the format of the inequality is unfamiliar. Even when producing a correct graph of an…

Fuzzy Graph Language Recognizability

OpenAIRE

Kalampakas , Antonios; Spartalis , Stefanos; Iliadis , Lazaros

2012-01-01

Part 5: Fuzzy Logic; International audience; Fuzzy graph language recognizability is introduced along the lines of the established theory of syntactic graph language recognizability by virtue of the algebraic structure of magmoids. The main closure properties of the corresponding class are investigated and several interesting examples of fuzzy graph languages are examined.

Quantitative graph theory mathematical foundations and applications

CERN Document Server

Dehmer, Matthias

2014-01-01

The first book devoted exclusively to quantitative graph theory, Quantitative Graph Theory: Mathematical Foundations and Applications presents and demonstrates existing and novel methods for analyzing graphs quantitatively. Incorporating interdisciplinary knowledge from graph theory, information theory, measurement theory, and statistical techniques, this book covers a wide range of quantitative-graph theoretical concepts and methods, including those pertaining to real and random graphs such as:Comparative approaches (graph similarity or distance)Graph measures to characterize graphs quantitat

Dynamic Representations of Sparse Graphs

DEFF Research Database (Denmark)

Brodal, Gerth Stølting; Fagerberg, Rolf

1999-01-01

We present a linear space data structure for maintaining graphs with bounded arboricity—a large class of sparse graphs containing e.g. planar graphs and graphs of bounded treewidth—under edge insertions, edge deletions, and adjacency queries. The data structure supports adjacency queries in worst...... case O(c) time, and edge insertions and edge deletions in amortized O(1) and O(c+log n) time, respectively, where n is the number of nodes in the graph, and c is the bound on the arboricity....

When quantum optics meets topology

Science.gov (United States)

Amo, Alberto

2018-02-01

Routing photons at the micrometer scale remains one of the greatest challenges of integrated quantum optics. The main difficulty is the scattering losses at bends and splitters in the photonic circuit. Current approaches imply elaborate designs, quite sensitive to fabrication details (1). Inspired by the physics underlying the one-way transport of electrons in topological insulators, on page 666 of this issue, Barik et al. (2) report a topological photonic crystal in which single photons are emitted and routed through bends with negligible loss. The marriage between quantum optics and topology promises new opportunities for compact quantum optics gating and manipulation.

Multiple graph regularized protein domain ranking.

Science.gov (United States)

Wang, Jim Jing-Yan; Bensmail, Halima; Gao, Xin

2012-11-19

Protein domain ranking is a fundamental task in structural biology. Most protein domain ranking methods rely on the pairwise comparison of protein domains while neglecting the global manifold structure of the protein domain database. Recently, graph regularized ranking that exploits the global structure of the graph defined by the pairwise similarities has been proposed. However, the existing graph regularized ranking methods are very sensitive to the choice of the graph model and parameters, and this remains a difficult problem for most of the protein domain ranking methods. To tackle this problem, we have developed the Multiple Graph regularized Ranking algorithm, MultiG-Rank. Instead of using a single graph to regularize the ranking scores, MultiG-Rank approximates the intrinsic manifold of protein domain distribution by combining multiple initial graphs for the regularization. Graph weights are learned with ranking scores jointly and automatically, by alternately minimizing an objective function in an iterative algorithm. Experimental results on a subset of the ASTRAL SCOP protein domain database demonstrate that MultiG-Rank achieves a better ranking performance than single graph regularized ranking methods and pairwise similarity based ranking methods. The problem of graph model and parameter selection in graph regularized protein domain ranking can be solved effectively by combining multiple graphs. This aspect of generalization introduces a new frontier in applying multiple graphs to solving protein domain ranking applications.

Acyclicity in edge-colored graphs

DEFF Research Database (Denmark)

Gutin, Gregory; Jones, Mark; Sheng, Bin

2017-01-01

A walk W in edge-colored graphs is called properly colored (PC) if every pair of consecutive edges in W is of different color. We introduce and study five types of PC acyclicity in edge-colored graphs such that graphs of PC acyclicity of type i is a proper superset of graphs of acyclicity of type...

ON BIPOLAR SINGLE VALUED NEUTROSOPHIC GRAPHS

OpenAIRE

Said Broumi; Mohamed Talea; Assia Bakali; Florentin Smarandache

2016-01-01

In this article, we combine the concept of bipolar neutrosophic set and graph theory. We introduce the notions of bipolar single valued neutrosophic graphs, strong bipolar single valued neutrosophic graphs, complete bipolar single valued neutrosophic graphs, regular bipolar single valued neutrosophic graphs and investigate some of their related properties.

Universal quantum gates on electron-spin qubits with quantum dots inside single-side optical microcavities.

Science.gov (United States)

Wei, Hai-Rui; Deng, Fu-Guo

2014-01-13

We present some compact quantum circuits for a deterministic quantum computing on electron-spin qubits assisted by quantum dots inside single-side optical microcavities, including the CNOT, Toffoli, and Fredkin gates. They are constructed by exploiting the giant optical Faraday rotation induced by a single-electron spin in a quantum dot inside a single-side optical microcavity as a result of cavity quantum electrodynamics. Our universal quantum gates have some advantages. First, all the gates are accomplished with a success probability of 100% in principle. Second, our schemes require no additional electron-spin qubits and they are achieved by some input-output processes of a single photon. Third, our circuits for these gates are simple and economic. Moreover, our devices for these gates work in both the weak coupling and the strong coupling regimes, and they are feasible in experiment.

Modular architectures for quantum networks

Science.gov (United States)

Pirker, A.; Wallnöfer, J.; Dür, W.

2018-05-01

We consider the problem of generating multipartite entangled states in a quantum network upon request. We follow a top-down approach, where the required entanglement is initially present in the network in form of network states shared between network devices, and then manipulated in such a way that the desired target state is generated. This minimizes generation times, and allows for network structures that are in principle independent of physical links. We present a modular and flexible architecture, where a multi-layer network consists of devices of varying complexity, including quantum network routers, switches and clients, that share certain resource states. We concentrate on the generation of graph states among clients, which are resources for numerous distributed quantum tasks. We assume minimal functionality for clients, i.e. they do not participate in the complex and distributed generation process of the target state. We present architectures based on shared multipartite entangled Greenberger–Horne–Zeilinger states of different size, and fully connected decorated graph states, respectively. We compare the features of these architectures to an approach that is based on bipartite entanglement, and identify advantages of the multipartite approach in terms of memory requirements and complexity of state manipulation. The architectures can handle parallel requests, and are designed in such a way that the network state can be dynamically extended if new clients or devices join the network. For generation or dynamical extension of the network states, we propose a quantum network configuration protocol, where entanglement purification is used to establish high fidelity states. The latter also allows one to show that the entanglement generated among clients is private, i.e. the network is secure.

Practical graph mining with R

CERN Document Server

Hendrix, William; Jenkins, John; Padmanabhan, Kanchana; Chakraborty, Arpan

2014-01-01

Practical Graph Mining with R presents a "do-it-yourself" approach to extracting interesting patterns from graph data. It covers many basic and advanced techniques for the identification of anomalous or frequently recurring patterns in a graph, the discovery of groups or clusters of nodes that share common patterns of attributes and relationships, the extraction of patterns that distinguish one category of graphs from another, and the use of those patterns to predict the category of new graphs. Hands-On Application of Graph Data Mining Each chapter in the book focuses on a graph mining task, such as link analysis, cluster analysis, and classification. Through applications using real data sets, the book demonstrates how computational techniques can help solve real-world problems. The applications covered include network intrusion detection, tumor cell diagnostics, face recognition, predictive toxicology, mining metabolic and protein-protein interaction networks, and community detection in social networks. De...

Adiabatic quantum algorithm for search engine ranking.

Science.gov (United States)

Garnerone, Silvano; Zanardi, Paolo; Lidar, Daniel A

2012-06-08

We propose an adiabatic quantum algorithm for generating a quantum pure state encoding of the PageRank vector, the most widely used tool in ranking the relative importance of internet pages. We present extensive numerical simulations which provide evidence that this algorithm can prepare the quantum PageRank state in a time which, on average, scales polylogarithmically in the number of web pages. We argue that the main topological feature of the underlying web graph allowing for such a scaling is the out-degree distribution. The top-ranked log(n) entries of the quantum PageRank state can then be estimated with a polynomial quantum speed-up. Moreover, the quantum PageRank state can be used in "q-sampling" protocols for testing properties of distributions, which require exponentially fewer measurements than all classical schemes designed for the same task. This can be used to decide whether to run a classical update of the PageRank.

Design of a Super-Pixel-Based Quantum Secure Authentication Demonstrator

NARCIS (Netherlands)

Toebes, Chris; Tentrup, Tristan B.H.; Pinkse, Pepijn W.H.

2017-01-01

Quantum Secure Authentication (QSA) is a method recently developed to authenticate a multiple-scattering key [1]. Previous implementations only showed proof-of-principle setups. We present a design of a compact and robust demonstration device for Quantum Secure Authentication. The challenge and

A seminar on graph theory

CERN Document Server

Harary, Frank

2015-01-01

Presented in 1962-63 by experts at University College, London, these lectures offer a variety of perspectives on graph theory. Although the opening chapters form a coherent body of graph theoretic concepts, this volume is not a text on the subject but rather an introduction to the extensive literature of graph theory. The seminar's topics are geared toward advanced undergraduate students of mathematics.Lectures by this volume's editor, Frank Harary, include ""Some Theorems and Concepts of Graph Theory,"" ""Topological Concepts in Graph Theory,"" ""Graphical Reconstruction,"" and other introduc

Compact XFEL and AMO sciences: SACLA and SCSS

International Nuclear Information System (INIS)

Yabashi, M; Tanaka, H; Tanaka, T; Tomizawa, H; Nagasono, M; Ishikawa, T; Harries, J R; Hikosaka, Y; Hishikawa, A; Nagaya, K; Saito, N; Shigemasa, E; Yamanouchi, K; Ueda, K; Togashi, T

2013-01-01

The concept, design and performance of Japan's compact free-electron laser (FEL) facilities, the SPring-8 Compact SASE Source test accelerator (SCSS) and SPring-8 Angstrom Compact free electron LAser (SACLA), and their applications in mainly atomic, molecular and optical science are reviewed. At SCSS, intense, ultrafast FEL pulses at extreme ultraviolet (EUV) wavelengths have been utilized for investigating various multi-photon processes in atoms, molecules and clusters by means of ion and electron spectroscopy. The quantum optical effect superfluorescence has been observed with EUV excitation. A pump–probe technique combining FEL pulses with near infrared laser pulses has been realized to study the ultrafast dynamics of atoms, molecules and clusters in the sub-picosecond regime. At SACLA, deep inner-shell multi-photon ionization by intense x-ray FEL pulses has been investigated. The development of seeded FEL sources for producing transversely and temporally coherent light, as well as the expected impact on advanced science are discussed. (invited paper)

Frequency locking of compact laser-diode modules at 633 nm

Science.gov (United States)

Nölleke, Christian; Leisching, Patrick; Blume, Gunnar; Jedrzejczyk, Daniel; Pohl, Johannes; Feise, David; Sahm, Alexander; Paschke, Katrin

2018-02-01

This work reports on a compact diode-laser module emitting at 633 nm. The emission frequency can be tuned with temperature and current, while optical feedback of an internal DBR grating ensures single-mode operation. The laser diode is integrated into a micro-fabricated package, which includes optics for beam shaping, a miniaturized optical isolator, and a vapor cell as frequency reference. The achieved absolute frequency stability is below 10-8 , while the output power can be more than 10 mW. This compact absolute frequency-stabilized laser system can replace gas lasers and may be integrated in future quantum technology devices.

Uniform Single Valued Neutrosophic Graphs

Directory of Open Access Journals (Sweden)

S. Broumi

2017-09-01

Full Text Available In this paper, we propose a new concept named the uniform single valued neutrosophic graph. An illustrative example and some properties are examined. Next, we develop an algorithmic approach for computing the complement of the single valued neutrosophic graph. A numerical example is demonstrated for computing the complement of single valued neutrosophic graphs and uniform single valued neutrosophic graph.

Extremal graph theory

CERN Document Server

Bollobas, Bela

2004-01-01

The ever-expanding field of extremal graph theory encompasses a diverse array of problem-solving methods, including applications to economics, computer science, and optimization theory. This volume, based on a series of lectures delivered to graduate students at the University of Cambridge, presents a concise yet comprehensive treatment of extremal graph theory.Unlike most graph theory treatises, this text features complete proofs for almost all of its results. Further insights into theory are provided by the numerous exercises of varying degrees of difficulty that accompany each chapter. A

Multiple graph regularized protein domain ranking

KAUST Repository

Wang, Jim Jing-Yan

2012-11-19

Background: Protein domain ranking is a fundamental task in structural biology. Most protein domain ranking methods rely on the pairwise comparison of protein domains while neglecting the global manifold structure of the protein domain database. Recently, graph regularized ranking that exploits the global structure of the graph defined by the pairwise similarities has been proposed. However, the existing graph regularized ranking methods are very sensitive to the choice of the graph model and parameters, and this remains a difficult problem for most of the protein domain ranking methods.Results: To tackle this problem, we have developed the Multiple Graph regularized Ranking algorithm, MultiG-Rank. Instead of using a single graph to regularize the ranking scores, MultiG-Rank approximates the intrinsic manifold of protein domain distribution by combining multiple initial graphs for the regularization. Graph weights are learned with ranking scores jointly and automatically, by alternately minimizing an objective function in an iterative algorithm. Experimental results on a subset of the ASTRAL SCOP protein domain database demonstrate that MultiG-Rank achieves a better ranking performance than single graph regularized ranking methods and pairwise similarity based ranking methods.Conclusion: The problem of graph model and parameter selection in graph regularized protein domain ranking can be solved effectively by combining multiple graphs. This aspect of generalization introduces a new frontier in applying multiple graphs to solving protein domain ranking applications. 2012 Wang et al; licensee BioMed Central Ltd.

Multiple graph regularized protein domain ranking

KAUST Repository

Wang, Jim Jing-Yan; Bensmail, Halima; Gao, Xin

2012-01-01

Background: Protein domain ranking is a fundamental task in structural biology. Most protein domain ranking methods rely on the pairwise comparison of protein domains while neglecting the global manifold structure of the protein domain database. Recently, graph regularized ranking that exploits the global structure of the graph defined by the pairwise similarities has been proposed. However, the existing graph regularized ranking methods are very sensitive to the choice of the graph model and parameters, and this remains a difficult problem for most of the protein domain ranking methods.Results: To tackle this problem, we have developed the Multiple Graph regularized Ranking algorithm, MultiG-Rank. Instead of using a single graph to regularize the ranking scores, MultiG-Rank approximates the intrinsic manifold of protein domain distribution by combining multiple initial graphs for the regularization. Graph weights are learned with ranking scores jointly and automatically, by alternately minimizing an objective function in an iterative algorithm. Experimental results on a subset of the ASTRAL SCOP protein domain database demonstrate that MultiG-Rank achieves a better ranking performance than single graph regularized ranking methods and pairwise similarity based ranking methods.Conclusion: The problem of graph model and parameter selection in graph regularized protein domain ranking can be solved effectively by combining multiple graphs. This aspect of generalization introduces a new frontier in applying multiple graphs to solving protein domain ranking applications. 2012 Wang et al; licensee BioMed Central Ltd.

Multiple graph regularized protein domain ranking

Directory of Open Access Journals (Sweden)

Wang Jim

2012-11-01

Full Text Available Abstract Background Protein domain ranking is a fundamental task in structural biology. Most protein domain ranking methods rely on the pairwise comparison of protein domains while neglecting the global manifold structure of the protein domain database. Recently, graph regularized ranking that exploits the global structure of the graph defined by the pairwise similarities has been proposed. However, the existing graph regularized ranking methods are very sensitive to the choice of the graph model and parameters, and this remains a difficult problem for most of the protein domain ranking methods. Results To tackle this problem, we have developed the Multiple Graph regularized Ranking algorithm, MultiG-Rank. Instead of using a single graph to regularize the ranking scores, MultiG-Rank approximates the intrinsic manifold of protein domain distribution by combining multiple initial graphs for the regularization. Graph weights are learned with ranking scores jointly and automatically, by alternately minimizing an objective function in an iterative algorithm. Experimental results on a subset of the ASTRAL SCOP protein domain database demonstrate that MultiG-Rank achieves a better ranking performance than single graph regularized ranking methods and pairwise similarity based ranking methods. Conclusion The problem of graph model and parameter selection in graph regularized protein domain ranking can be solved effectively by combining multiple graphs. This aspect of generalization introduces a new frontier in applying multiple graphs to solving protein domain ranking applications.

Canonical Labelling of Site Graphs

Directory of Open Access Journals (Sweden)

Nicolas Oury

2013-06-01

Full Text Available We investigate algorithms for canonical labelling of site graphs, i.e. graphs in which edges bind vertices on sites with locally unique names. We first show that the problem of canonical labelling of site graphs reduces to the problem of canonical labelling of graphs with edge colourings. We then present two canonical labelling algorithms based on edge enumeration, and a third based on an extension of Hopcroft's partition refinement algorithm. All run in quadratic worst case time individually. However, one of the edge enumeration algorithms runs in sub-quadratic time for graphs with "many" automorphisms, and the partition refinement algorithm runs in sub-quadratic time for graphs with "few" bisimulation equivalences. This suite of algorithms was chosen based on the expectation that graphs fall in one of those two categories. If that is the case, a combined algorithm runs in sub-quadratic worst case time. Whether this expectation is reasonable remains an interesting open problem.

Compact mode-locked diode laser system for high precision frequency comparisons in microgravity

Science.gov (United States)

Christopher, H.; Kovalchuk, E. V.; Wicht, A.; Erbert, G.; Tränkle, G.; Peters, A.

2017-11-01

Nowadays cold atom-based quantum sensors such as atom interferometers start leaving optical labs to put e.g. fundamental physics under test in space. One of such intriguing applications is the test of the Weak Equivalence Principle, the Universality of Free Fall (UFF), using different quantum objects such as rubidium (Rb) and potassium (K) ultra-cold quantum gases. The corresponding atom interferometers are implemented with light pulses from narrow linewidth lasers emitting near 767 nm (K) and 780 nm (Rb). To determine any relative acceleration of the K and Rb quantum ensembles during free fall, the frequency difference between the K and Rb lasers has to be measured very accurately by means of an optical frequency comb. Micro-gravity applications not only require good electro-optical characteristics but are also stringent in their demand for compactness, robustness and efficiency. For frequency comparison experiments the rather complex fiber laser-based frequency comb system may be replaced by one semiconductor laser chip and some passive components. Here we present an important step towards this direction, i.e. we report on the development of a compact mode-locked diode laser system designed to generate a highly stable frequency comb in the wavelength range of 780 nm.

Domination criticality in product graphs

Directory of Open Access Journals (Sweden)

M.R. Chithra

2015-07-01

Full Text Available A connected dominating set is an important notion and has many applications in routing and management of networks. Graph products have turned out to be a good model of interconnection networks. This motivated us to study the Cartesian product of graphs G with connected domination number, γc(G=2,3 and characterize such graphs. Also, we characterize the k−γ-vertex (edge critical graphs and k−γc-vertex (edge critical graphs for k=2,3 where γ denotes the domination number of G. We also discuss the vertex criticality in grids.

Graph Creation, Visualisation and Transformation

Directory of Open Access Journals (Sweden)

Maribel Fernández

2010-03-01

Full Text Available We describe a tool to create, edit, visualise and compute with interaction nets - a form of graph rewriting systems. The editor, called GraphPaper, allows users to create and edit graphs and their transformation rules using an intuitive user interface. The editor uses the functionalities of the TULIP system, which gives us access to a wealth of visualisation algorithms. Interaction nets are not only a formalism for the specification of graphs, but also a rewrite-based computation model. We discuss graph rewriting strategies and a language to express them in order to perform strategic interaction net rewriting.

Graph Colouring Algorithms

DEFF Research Database (Denmark)

Husfeldt, Thore

2015-01-01

This chapter presents an introduction to graph colouring algorithms. The focus is on vertex-colouring algorithms that work for general classes of graphs with worst-case performance guarantees in a sequential model of computation. The presentation aims to demonstrate the breadth of available...

The fascinating world of graph theory

CERN Document Server

Benjamin, Arthur; Zhang, Ping

2015-01-01

Graph theory goes back several centuries and revolves around the study of graphs-mathematical structures showing relations between objects. With applications in biology, computer science, transportation science, and other areas, graph theory encompasses some of the most beautiful formulas in mathematics-and some of its most famous problems. The Fascinating World of Graph Theory explores the questions and puzzles that have been studied, and often solved, through graph theory. This book looks at graph theory's development and the vibrant individuals responsible for the field's growth. Introducin

Classical dynamics on graphs

International Nuclear Information System (INIS)

Barra, F.; Gaspard, P.

2001-01-01

We consider the classical evolution of a particle on a graph by using a time-continuous Frobenius-Perron operator that generalizes previous propositions. In this way, the relaxation rates as well as the chaotic properties can be defined for the time-continuous classical dynamics on graphs. These properties are given as the zeros of some periodic-orbit zeta functions. We consider in detail the case of infinite periodic graphs where the particle undergoes a diffusion process. The infinite spatial extension is taken into account by Fourier transforms that decompose the observables and probability densities into sectors corresponding to different values of the wave number. The hydrodynamic modes of diffusion are studied by an eigenvalue problem of a Frobenius-Perron operator corresponding to a given sector. The diffusion coefficient is obtained from the hydrodynamic modes of diffusion and has the Green-Kubo form. Moreover, we study finite but large open graphs that converge to the infinite periodic graph when their size goes to infinity. The lifetime of the particle on the open graph is shown to correspond to the lifetime of a system that undergoes a diffusion process before it escapes

Groupies in multitype random graphs

OpenAIRE

Shang, Yilun

2016-01-01

A groupie in a graph is a vertex whose degree is not less than the average degree of its neighbors. Under some mild conditions, we show that the proportion of groupies is very close to 1/2 in multitype random graphs (such as stochastic block models), which include Erd?s-R?nyi random graphs, random bipartite, and multipartite graphs as special examples. Numerical examples are provided to illustrate the theoretical results.

Fixed point algebras for easy quantum groups

DEFF Research Database (Denmark)

Gabriel, Olivier; Weber, Moritz

2016-01-01

Compact matrix quantum groups act naturally on Cuntz algebras. The first author isolated certain conditions under which the fixed point algebras under this action are Kirchberg algebras. Hence they are completely determined by their K-groups. Building on prior work by the second author,we prove...... that free easy quantum groups satisfy these conditions and we compute the K-groups of their fixed point algebras in a general form. We then turn to examples such as the quantum permutation group S+ n,the free orthogonal quantum group O+ n and the quantum reflection groups Hs+ n. Our fixed point......-algebra construction provides concrete examples of free actions of free orthogonal easy quantum groups,which are related to Hopf-Galois extensions....

Fibonacci number of the tadpole graph

Directory of Open Access Journals (Sweden)

Joe DeMaio

2014-10-01

Full Text Available In 1982, Prodinger and Tichy defined the Fibonacci number of a graph G to be the number of independent sets of the graph G. They did so since the Fibonacci number of the path graph Pn is the Fibonacci number F(n+2 and the Fibonacci number of the cycle graph Cn is the Lucas number Ln. The tadpole graph Tn,k is the graph created by concatenating Cn and Pk with an edge from any vertex of Cn to a pendant of Pk for integers n=3 and k=0. This paper establishes formulae and identities for the Fibonacci number of the tadpole graph via algebraic and combinatorial methods.

On characterizing terrain visibility graphs

Directory of Open Access Journals (Sweden)

William Evans

2015-06-01

Full Text Available A terrain is an $x$-monotone polygonal line in the $xy$-plane. Two vertices of a terrain are mutually visible if and only if there is no terrain vertex on or above the open line segment connecting them. A graph whose vertices represent terrain vertices and whose edges represent mutually visible pairs of terrain vertices is called a terrain visibility graph. We would like to find properties that are both necessary and sufficient for a graph to be a terrain visibility graph; that is, we would like to characterize terrain visibility graphs.Abello et al. [Discrete and Computational Geometry, 14(3:331--358, 1995] showed that all terrain visibility graphs are “persistent”. They showed that the visibility information of a terrain point set implies some ordering requirements on the slopes of the lines connecting pairs of points in any realization, and as a step towards showing sufficiency, they proved that for any persistent graph $M$ there is a total order on the slopes of the (pseudo lines in a generalized configuration of points whose visibility graph is $M$.We give a much simpler proof of this result by establishing an orientation to every triple of vertices, reflecting some slope ordering requirements that are consistent with $M$ being the visibility graph, and prove that these requirements form a partial order. We give a faster algorithm to construct a total order on the slopes. Our approach attempts to clarify the implications of the graph theoretic properties on the ordering of the slopes, and may be interpreted as defining properties on an underlying oriented matroid that we show is a restricted type of $3$-signotope.

Network reconstruction via graph blending

Science.gov (United States)

Estrada, Rolando

2016-05-01

Graphs estimated from empirical data are often noisy and incomplete due to the difficulty of faithfully observing all the components (nodes and edges) of the true graph. This problem is particularly acute for large networks where the number of components may far exceed available surveillance capabilities. Errors in the observed graph can render subsequent analyses invalid, so it is vital to develop robust methods that can minimize these observational errors. Errors in the observed graph may include missing and spurious components, as well fused (multiple nodes are merged into one) and split (a single node is misinterpreted as many) nodes. Traditional graph reconstruction methods are only able to identify missing or spurious components (primarily edges, and to a lesser degree nodes), so we developed a novel graph blending framework that allows us to cast the full estimation problem as a simple edge addition/deletion problem. Armed with this framework, we systematically investigate the viability of various topological graph features, such as the degree distribution or the clustering coefficients, and existing graph reconstruction methods for tackling the full estimation problem. Our experimental results suggest that incorporating any topological feature as a source of information actually hinders reconstruction accuracy. We provide a theoretical analysis of this phenomenon and suggest several avenues for improving this estimation problem.

Interaction graphs

DEFF Research Database (Denmark)

Seiller, Thomas

2016-01-01

Interaction graphs were introduced as a general, uniform, construction of dynamic models of linear logic, encompassing all Geometry of Interaction (GoI) constructions introduced so far. This series of work was inspired from Girard's hyperfinite GoI, and develops a quantitative approach that should...... be understood as a dynamic version of weighted relational models. Until now, the interaction graphs framework has been shown to deal with exponentials for the constrained system ELL (Elementary Linear Logic) while keeping its quantitative aspect. Adapting older constructions by Girard, one can clearly define...... "full" exponentials, but at the cost of these quantitative features. We show here that allowing interpretations of proofs to use continuous (yet finite in a measure-theoretic sense) sets of states, as opposed to earlier Interaction Graphs constructions were these sets of states were discrete (and finite...

Groupies in multitype random graphs.

Science.gov (United States)

Shang, Yilun

2016-01-01

A groupie in a graph is a vertex whose degree is not less than the average degree of its neighbors. Under some mild conditions, we show that the proportion of groupies is very close to 1/2 in multitype random graphs (such as stochastic block models), which include Erdős-Rényi random graphs, random bipartite, and multipartite graphs as special examples. Numerical examples are provided to illustrate the theoretical results.

The Harary index of a graph

CERN Document Server

Xu, Kexiang; Trinajstić, Nenad

2015-01-01

This is the first book to focus on the topological index, the Harary index, of a graph, including its mathematical properties, chemical applications and some related and attractive open problems. This book is dedicated to Professor Frank Harary (1921—2005), the grandmaster of graph theory and its applications. It has be written by experts in the field of graph theory and its applications. For a connected graph G, as an important distance-based topological index, the Harary index H(G) is defined as the sum of the reciprocals of the distance between any two unordered vertices of the graph G. In this book, the authors report on the newest results on the Harary index of a graph. These results mainly concern external graphs with respect to the Harary index; the relations to other topological indices; its properties and applications to pure graph theory and chemical graph theory; and two significant variants, i.e., additively and multiplicatively weighted Harary indices. In the last chapter, we present a number o...

A Modal-Logic Based Graph Abstraction

NARCIS (Netherlands)

Bauer, J.; Boneva, I.B.; Kurban, M.E.; Rensink, Arend; Ehrig, H; Heckel, R.; Rozenberg, G.; Taentzer, G.

2008-01-01

Infinite or very large state spaces often prohibit the successful verification of graph transformation systems. Abstract graph transformation is an approach that tackles this problem by abstracting graphs to abstract graphs of bounded size and by lifting application of productions to abstract

Graph mining for next generation sequencing: leveraging the assembly graph for biological insights.

Science.gov (United States)

Warnke-Sommer, Julia; Ali, Hesham

2016-05-06

The assembly of Next Generation Sequencing (NGS) reads remains a challenging task. This is especially true for the assembly of metagenomics data that originate from environmental samples potentially containing hundreds to thousands of unique species. The principle objective of current assembly tools is to assemble NGS reads into contiguous stretches of sequence called contigs while maximizing for both accuracy and contig length. The end goal of this process is to produce longer contigs with the major focus being on assembly only. Sequence read assembly is an aggregative process, during which read overlap relationship information is lost as reads are merged into longer sequences or contigs. The assembly graph is information rich and capable of capturing the genomic architecture of an input read data set. We have developed a novel hybrid graph in which nodes represent sequence regions at different levels of granularity. This model, utilized in the assembly and analysis pipeline Focus, presents a concise yet feature rich view of a given input data set, allowing for the extraction of biologically relevant graph structures for graph mining purposes. Focus was used to create hybrid graphs to model metagenomics data sets obtained from the gut microbiomes of five individuals with Crohn's disease and eight healthy individuals. Repetitive and mobile genetic elements are found to be associated with hybrid graph structure. Using graph mining techniques, a comparative study of the Crohn's disease and healthy data sets was conducted with focus on antibiotics resistance genes associated with transposase genes. Results demonstrated significant differences in the phylogenetic distribution of categories of antibiotics resistance genes in the healthy and diseased patients. Focus was also evaluated as a pure assembly tool and produced excellent results when compared against the Meta-velvet, Omega, and UD-IDBA assemblers. Mining the hybrid graph can reveal biological phenomena captured

Distance-transitive graphs

NARCIS (Netherlands)

Cohen, A.M.; Beineke, L.W.; Wilson, R.J.; Cameron, P.J.

2004-01-01

In this chapter we investigate the classification of distance-transitive graphs: these are graphs whose automorphism groups are transitive on each of the sets of pairs of vertices at distance i, for i = 0, 1,.... We provide an introduction into the field. By use of the classification of finite

TrajGraph: A Graph-Based Visual Analytics Approach to Studying Urban Network Centralities Using Taxi Trajectory Data.

Science.gov (United States)

Huang, Xiaoke; Zhao, Ye; Yang, Jing; Zhang, Chong; Ma, Chao; Ye, Xinyue

2016-01-01

We propose TrajGraph, a new visual analytics method, for studying urban mobility patterns by integrating graph modeling and visual analysis with taxi trajectory data. A special graph is created to store and manifest real traffic information recorded by taxi trajectories over city streets. It conveys urban transportation dynamics which can be discovered by applying graph analysis algorithms. To support interactive, multiscale visual analytics, a graph partitioning algorithm is applied to create region-level graphs which have smaller size than the original street-level graph. Graph centralities, including Pagerank and betweenness, are computed to characterize the time-varying importance of different urban regions. The centralities are visualized by three coordinated views including a node-link graph view, a map view and a temporal information view. Users can interactively examine the importance of streets to discover and assess city traffic patterns. We have implemented a fully working prototype of this approach and evaluated it using massive taxi trajectories of Shenzhen, China. TrajGraph's capability in revealing the importance of city streets was evaluated by comparing the calculated centralities with the subjective evaluations from a group of drivers in Shenzhen. Feedback from a domain expert was collected. The effectiveness of the visual interface was evaluated through a formal user study. We also present several examples and a case study to demonstrate the usefulness of TrajGraph in urban transportation analysis.

Temporal Representation in Semantic Graphs

Energy Technology Data Exchange (ETDEWEB)

Levandoski, J J; Abdulla, G M

2007-08-07

A wide range of knowledge discovery and analysis applications, ranging from business to biological, make use of semantic graphs when modeling relationships and concepts. Most of the semantic graphs used in these applications are assumed to be static pieces of information, meaning temporal evolution of concepts and relationships are not taken into account. Guided by the need for more advanced semantic graph queries involving temporal concepts, this paper surveys the existing work involving temporal representations in semantic graphs.

The complexity of the matching-cut problem for planar graphs and other graph classes

NARCIS (Netherlands)

Bonsma, P.S.

2009-01-01

The Matching-Cut problem is the problem to decide whether a graph has an edge cut that is also a matching. Previously this problem was studied under the name of the Decomposable Graph Recognition problem, and proved to be -complete when restricted to graphs with maximum degree four. In this paper it

PRIVATE GRAPHS – ACCESS RIGHTS ON GRAPHS FOR SEAMLESS NAVIGATION

Directory of Open Access Journals (Sweden)

W. Dorner

2016-06-01

Full Text Available After the success of GNSS (Global Navigational Satellite Systems and navigation services for public streets, indoor seems to be the next big development in navigational services, relying on RTLS – Real Time Locating Services (e.g. WIFI and allowing seamless navigation. In contrast to navigation and routing services on public streets, seamless navigation will cause an additional challenge: how to make routing data accessible to defined users or restrict access rights for defined areas or only to parts of the graph to a defined user group? The paper will present case studies and data from literature, where seamless and especially indoor navigation solutions are presented (hospitals, industrial complexes, building sites, but the problem of restricted access rights was only touched from a real world, but not a technical perspective. The analysis of case studies will show, that the objective of navigation and the different target groups for navigation solutions will demand well defined access rights and require solutions, how to make only parts of a graph to a user or application available to solve a navigational task. The paper will therefore introduce the concept of private graphs, which is defined as a graph for navigational purposes covering the street, road or floor network of an area behind a public street and suggest different approaches how to make graph data for navigational purposes available considering access rights and data protection, privacy and security issues as well.

Integer Flows and Circuit Covers of Graphs and Signed Graphs

Science.gov (United States)

Cheng, Jian

The work in Chapter 2 is motivated by Tutte and Jaeger's pioneering work on converting modulo flows into integer-valued flows for ordinary graphs. For a signed graphs (G, sigma), we first prove that for each k ∈ {2, 3}, if (G, sigma) is (k - 1)-edge-connected and contains an even number of negative edges when k = 2, then every modulo k-flow of (G, sigma) can be converted into an integer-valued ( k + 1)-ow with a larger or the same support. We also prove that if (G, sigma) is odd-(2p+1)-edge-connected, then (G, sigma) admits a modulo circular (2 + 1/ p)-flows if and only if it admits an integer-valued circular (2 + 1/p)-flows, which improves all previous result by Xu and Zhang (DM2005), Schubert and Steffen (EJC2015), and Zhu (JCTB2015). Shortest circuit cover conjecture is one of the major open problems in graph theory. It states that every bridgeless graph G contains a set of circuits F such that each edge is contained in at least one member of F and the length of F is at most 7/5∥E(G)∥. This concept was recently generalized to signed graphs by Macajova et al. (JGT2015). In Chapter 3, we improve their upper bound from 11∥E( G)∥ to 14/3 ∥E(G)∥, and if G is 2-edgeconnected and has even negativeness, then it can be further reduced to 11/3 ∥E(G)∥. Tutte's 3-flow conjecture has been studied by many graph theorists in the last several decades. As a new approach to this conjecture, DeVos and Thomassen considered the vectors as ow values and found that there is a close relation between vector S1-flows and integer 3-NZFs. Motivated by their observation, in Chapter 4, we prove that if a graph G admits a vector S1-flow with rank at most two, then G admits an integer 3-NZF. The concept of even factors is highly related to the famous Four Color Theorem. We conclude this dissertation in Chapter 5 with an improvement of a recent result by Chen and Fan (JCTB2016) on the upperbound of even factors. We show that if a graph G contains an even factor, then it

Black holes as quantum gravity condensates

Science.gov (United States)

Oriti, Daniele; Pranzetti, Daniele; Sindoni, Lorenzo

2018-03-01

We model spherically symmetric black holes within the group field theory formalism for quantum gravity via generalized condensate states, involving sums over arbitrarily refined graphs (dual to three-dimensional triangulations). The construction relies heavily on both the combinatorial tools of random tensor models and the quantum geometric data of loop quantum gravity, both part of the group field theory formalism. Armed with the detailed microscopic structure, we compute the entropy associated with the black hole horizon, which turns out to be equivalently the Boltzmann entropy of its microscopic degrees of freedom and the entanglement entropy between the inside and outside regions. We recover the area law under very general conditions, as well as the Bekenstein-Hawking formula. The result is also shown to be generically independent of any specific value of the Immirzi parameter.

Dynamics of a complex quantum magnet

International Nuclear Information System (INIS)

Landry, James W.; Coppersmith, S. N.

2003-01-01

We have computed the low energy quantum states and low frequency dynamical susceptibility of complex quantum spin systems in the limit of strong interactions, obtaining exact results for system sizes enormously larger than accessible previously. The ground state is a complex superposition of a substantial fraction of all the classical ground states, and yet the dynamical susceptibility exhibits sharp resonances reminiscent of the behavior of single spins. These results show that strongly interacting quantum systems can organize to generate coherent excitations and shed light on recent experiments demonstrating that coherent excitations are present in a disordered spin liquid. The dependence of the energy spectra on system size differs qualitatively from that of the energy spectra of random undirected bipartite graphs with similar statistics, implying that strong interactions are giving rise to these unusual spectral properties

Port-Hamiltonian Systems on Open Graphs

NARCIS (Netherlands)

Schaft, A.J. van der; Maschke, B.M.

2010-01-01

In this talk we discuss how to define in an intrinsic manner port-Hamiltonian dynamics on open graphs. Open graphs are graphs where some of the vertices are boundary vertices (terminals), which allow interconnection with other systems. We show that a directed graph carries two natural Dirac

Towards a theory of geometric graphs

CERN Document Server

Pach, Janos

2004-01-01

The early development of graph theory was heavily motivated and influenced by topological and geometric themes, such as the Konigsberg Bridge Problem, Euler's Polyhedral Formula, or Kuratowski's characterization of planar graphs. In 1936, when Denes Konig published his classical Theory of Finite and Infinite Graphs, the first book ever written on the subject, he stressed this connection by adding the subtitle Combinatorial Topology of Systems of Segments. He wanted to emphasize that the subject of his investigations was very concrete: planar figures consisting of points connected by straight-line segments. However, in the second half of the twentieth century, graph theoretical research took an interesting turn. In the most popular and most rapidly growing areas (the theory of random graphs, Ramsey theory, extremal graph theory, algebraic graph theory, etc.), graphs were considered as abstract binary relations rather than geometric objects. Many of the powerful techniques developed in these fields have been su...

Programming Non-Trivial Algorithms in the Measurement Based Quantum Computation Model

Energy Technology Data Exchange (ETDEWEB)

Alsing, Paul [United States Air Force Research Laboratory, Wright-Patterson Air Force Base; Fanto, Michael [United States Air Force Research Laboratory, Wright-Patterson Air Force Base; Lott, Capt. Gordon [United States Air Force Research Laboratory, Wright-Patterson Air Force Base; Tison, Christoper C. [United States Air Force Research Laboratory, Wright-Patterson Air Force Base

2014-01-01

We provide a set of prescriptions for implementing a quantum circuit model algorithm as measurement based quantum computing (MBQC) algorithm1, 2 via a large cluster state. As means of illustration we draw upon our numerical modeling experience to describe a large graph state capable of searching a logical 8 element list (a non-trivial version of Grover's algorithm3 with feedforward). We develop several prescriptions based on analytic evaluation of cluster states and graph state equations which can be generalized into any circuit model operations. Such a resulting cluster state will be able to carry out the desired operation with appropriate measurements and feed forward error correction. We also discuss the physical implementation and the analysis of the principal 3-qubit entangling gate (Toffoli) required for a non-trivial feedforward realization of an 8-element Grover search algorithm.

Criticality and novel quantum liquid phases in Ginzburg-Landau theories with compact and non-compact gauge fields

Energy Technology Data Exchange (ETDEWEB)

Smiseth, Jo

2005-07-01

The critical properties of three-dimensional U(1)-symmetric lattice gauge theories have been studied. The models apply to various physical systems such as insulating phases of strongly correlated electron systems as well as superconducting and superfluid states of liquid metallic hydrogen under extreme pressures. The thesis contains an introductory part and a collection of research papers of which seven are published works and one is submitted for publication. The outline of this thesis is as follows. In Chapter 2 the theory of phase transitions is discussed with emphasis on continuous phase transitions, critical phenomena and phase transitions in gauge theories. In the next chapter the phases of the abelian Higgs model are presented, and the critical phenomena are discussed. Furthermore, the multicomponent Ginzburg-Landau theory and the applications to liquid metallic hydrogen are presented. Chapter 4 contains an overview of the Monte Carlo integration scheme, including the Metropolis algorithm, error estimates, and re weighting techniques. This chapter is followed by the papers I-VIII. Paper I: Criticality in the (2+1)-Dimensional Compact Higgs Model and Fractionalized Insulators. Paper II: Phase structure of (2+1)-dimensional compact lattice gauge theories and the transition from Mott insulator to fractionalized insulator. Paper III: Compact U(1) gauge theories in 2+1 dimensions and the physics of low dimensional insulating materials. Paper IV: Phase structure of Abelian Chern-Simons gauge theories. Paper V: Critical Properties of the N-Color London Model. Paper VI: Field- and temperature induced topological phase transitions in the three-dimensional N-component London superconductor. Paper VII: Vortex Sublattice Melting in a Two-Component Superconductor. Paper VIII: Observation of a metallic superfluid in a numerical experiment (ml)

Software for Graph Analysis and Visualization

Directory of Open Access Journals (Sweden)

M. I. Kolomeychenko

2014-01-01

Full Text Available This paper describes the software for graph storage, analysis and visualization. The article presents a comparative analysis of existing software for analysis and visualization of graphs, describes the overall architecture of application and basic principles of construction and operation of the main modules. Furthermore, a description of the developed graph storage oriented to storage and processing of large-scale graphs is presented. The developed algorithm for finding communities and implemented algorithms of autolayouts of graphs are the main functionality of the product. The main advantage of the developed software is high speed processing of large size networks (up to millions of nodes and links. Moreover, the proposed graph storage architecture is unique and has no analogues. The developed approaches and algorithms are optimized for operating with big graphs and have high productivity.

Advances in quantum mechanics contemporary trends and open problems

CERN Document Server

Dell'Antonio, Gianfausto

2017-01-01

This volume collects recent contributions on the contemporary trends in the mathematics of quantum mechanics, and more specifically in mathematical problems arising in quantum many-body dynamics, quantum graph theory, cold atoms, unitary gases, with particular emphasis on the developments of the specific mathematical tools needed, including: linear and non-linear Schrödinger equations, topological invariants, non-commutative geometry, resonances and operator extension theory, among others. Most of contributors are international leading experts or respected young researchers in mathematical physics, PDE, and operator theory. All their material is the fruit of recent studies that have already become a reference in the community. Offering a unified perspective of the mathematics of quantum mechanics, it is a valuable resource for researchers in the field.

What Would a Graph Look Like in this Layout? A Machine Learning Approach to Large Graph Visualization.

Science.gov (United States)

Kwon, Oh-Hyun; Crnovrsanin, Tarik; Ma, Kwan-Liu

2018-01-01

Using different methods for laying out a graph can lead to very different visual appearances, with which the viewer perceives different information. Selecting a "good" layout method is thus important for visualizing a graph. The selection can be highly subjective and dependent on the given task. A common approach to selecting a good layout is to use aesthetic criteria and visual inspection. However, fully calculating various layouts and their associated aesthetic metrics is computationally expensive. In this paper, we present a machine learning approach to large graph visualization based on computing the topological similarity of graphs using graph kernels. For a given graph, our approach can show what the graph would look like in different layouts and estimate their corresponding aesthetic metrics. An important contribution of our work is the development of a new framework to design graph kernels. Our experimental study shows that our estimation calculation is considerably faster than computing the actual layouts and their aesthetic metrics. Also, our graph kernels outperform the state-of-the-art ones in both time and accuracy. In addition, we conducted a user study to demonstrate that the topological similarity computed with our graph kernel matches perceptual similarity assessed by human users.

Text-Filled Stacked Area Graphs

DEFF Research Database (Denmark)

Kraus, Martin

2011-01-01

-filled stacked area graphs; i.e., graphs that feature stacked areas that are filled with small-typed text. Since these graphs allow for computing the text layout automatically, it is possible to include large amounts of textual detail with very little effort. We discuss the most important challenges and some...... solutions for the design of text-filled stacked area graphs with the help of an exemplary visualization of the genres, publication years, and titles of a database of several thousand PC games....

On Graph Rewriting, Reduction and Evaluation

DEFF Research Database (Denmark)

Zerny, Ian

2010-01-01

We inter-derive two prototypical styles of graph reduction: reduction machines à la Turner and graph rewriting systems à la Barendregt et al. To this end, we adapt Danvy et al.'s mechanical program derivations from the world of terms to the world of graphs. We also outline how to inter-derive a t......We inter-derive two prototypical styles of graph reduction: reduction machines à la Turner and graph rewriting systems à la Barendregt et al. To this end, we adapt Danvy et al.'s mechanical program derivations from the world of terms to the world of graphs. We also outline how to inter...

Hybrid quantum gates between flying photon and diamond nitrogen-vacancy centers assisted by optical microcavities

Science.gov (United States)

Wei, Hai-Rui; Lu Long, Gui

2015-01-01

Hybrid quantum gates hold great promise for quantum information processing since they preserve the advantages of different quantum systems. Here we present compact quantum circuits to deterministically implement controlled-NOT, Toffoli, and Fredkin gates between a flying photon qubit and diamond nitrogen-vacancy (NV) centers assisted by microcavities. The target qubits of these universal quantum gates are encoded on the spins of the electrons associated with the diamond NV centers and they have long coherence time for storing information, and the control qubit is encoded on the polarizations of the flying photon and can be easily manipulated. Our quantum circuits are compact, economic, and simple. Moreover, they do not require additional qubits. The complexity of our schemes for universal three-qubit gates is much reduced, compared to the synthesis with two-qubit entangling gates. These schemes have high fidelities and efficiencies, and they are feasible in experiment. PMID:26271899

Adiabatic condition and the quantum hitting time of Markov chains

International Nuclear Information System (INIS)

Krovi, Hari; Ozols, Maris; Roland, Jeremie

2010-01-01

We present an adiabatic quantum algorithm for the abstract problem of searching marked vertices in a graph, or spatial search. Given a random walk (or Markov chain) P on a graph with a set of unknown marked vertices, one can define a related absorbing walk P ' where outgoing transitions from marked vertices are replaced by self-loops. We build a Hamiltonian H(s) from the interpolated Markov chain P(s)=(1-s)P+sP ' and use it in an adiabatic quantum algorithm to drive an initial superposition over all vertices to a superposition over marked vertices. The adiabatic condition implies that, for any reversible Markov chain and any set of marked vertices, the running time of the adiabatic algorithm is given by the square root of the classical hitting time. This algorithm therefore demonstrates a novel connection between the adiabatic condition and the classical notion of hitting time of a random walk. It also significantly extends the scope of previous quantum algorithms for this problem, which could only obtain a full quadratic speedup for state-transitive reversible Markov chains with a unique marked vertex.

Minimal-memory realization of pearl-necklace encoders of general quantum convolutional codes

International Nuclear Information System (INIS)

Houshmand, Monireh; Hosseini-Khayat, Saied

2011-01-01

Quantum convolutional codes, like their classical counterparts, promise to offer higher error correction performance than block codes of equivalent encoding complexity, and are expected to find important applications in reliable quantum communication where a continuous stream of qubits is transmitted. Grassl and Roetteler devised an algorithm to encode a quantum convolutional code with a ''pearl-necklace'' encoder. Despite their algorithm's theoretical significance as a neat way of representing quantum convolutional codes, it is not well suited to practical realization. In fact, there is no straightforward way to implement any given pearl-necklace structure. This paper closes the gap between theoretical representation and practical implementation. In our previous work, we presented an efficient algorithm to find a minimal-memory realization of a pearl-necklace encoder for Calderbank-Shor-Steane (CSS) convolutional codes. This work is an extension of our previous work and presents an algorithm for turning a pearl-necklace encoder for a general (non-CSS) quantum convolutional code into a realizable quantum convolutional encoder. We show that a minimal-memory realization depends on the commutativity relations between the gate strings in the pearl-necklace encoder. We find a realization by means of a weighted graph which details the noncommutative paths through the pearl necklace. The weight of the longest path in this graph is equal to the minimal amount of memory needed to implement the encoder. The algorithm has a polynomial-time complexity in the number of gate strings in the pearl-necklace encoder.

Graph transformation tool contest 2008

NARCIS (Netherlands)

Rensink, Arend; van Gorp, Pieter

This special section is the outcome of the graph transformation tool contest organised during the Graph-Based Tools (GraBaTs) 2008 workshop, which took place as a satellite event of the International Conference on Graph Transformation (ICGT) 2008. The contest involved two parts: three “off-line case

On dominator colorings in graphs

Indian Academy of Sciences (India)

colors required for a dominator coloring of G is called the dominator .... Theorem 1.3 shows that the complete graph Kn is the only connected graph of order n ... Conversely, if a graph G satisfies condition (i) or (ii), it is easy to see that χd(G) =.

Graphs with branchwidth at most three

NARCIS (Netherlands)

Bodlaender, H.L.; Thilikos, D.M.

1997-01-01

In this paper we investigate both the structure of graphs with branchwidth at most three, as well as algorithms to recognise such graphs. We show that a graph has branchwidth at most three, if and only if it has treewidth at most three and does not contain the three-dimensional binary cube graph

Quantum field theory

CERN Document Server

Sadovskii, Michael V

2013-01-01

This book discusses the main concepts of the Standard Model of elementary particles in a compact and straightforward way. The work illustrates the unity of modern theoretical physics by combining approaches and concepts of the quantum field theory and modern condensed matter theory. The inductive approach allows a deep understanding of ideas and methods used for solving problems in this field.

Planar graphs theory and algorithms

CERN Document Server

Nishizeki, T

1988-01-01

Collected in this volume are most of the important theorems and algorithms currently known for planar graphs, together with constructive proofs for the theorems. Many of the algorithms are written in Pidgin PASCAL, and are the best-known ones; the complexities are linear or 0(nlogn). The first two chapters provide the foundations of graph theoretic notions and algorithmic techniques. The remaining chapters discuss the topics of planarity testing, embedding, drawing, vertex- or edge-coloring, maximum independence set, subgraph listing, planar separator theorem, Hamiltonian cycles, and single- or multicommodity flows. Suitable for a course on algorithms, graph theory, or planar graphs, the volume will also be useful for computer scientists and graph theorists at the research level. An extensive reference section is included.

CORECLUSTER: A Degeneracy Based Graph Clustering Framework

OpenAIRE

Giatsidis , Christos; Malliaros , Fragkiskos; Thilikos , Dimitrios M. ,; Vazirgiannis , Michalis

2014-01-01

International audience; Graph clustering or community detection constitutes an important task forinvestigating the internal structure of graphs, with a plethora of applications in several domains. Traditional tools for graph clustering, such asspectral methods, typically suffer from high time and space complexity. In thisarticle, we present \\textsc{CoreCluster}, an efficient graph clusteringframework based on the concept of graph degeneracy, that can be used along withany known graph clusteri...

Coloring sums of extensions of certain graphs

Directory of Open Access Journals (Sweden)

Johan Kok

2017-12-01

Full Text Available We recall that the minimum number of colors that allow a proper coloring of graph $G$ is called the chromatic number of $G$ and denoted $\\chi(G$. Motivated by the introduction of the concept of the $b$-chromatic sum of a graph the concept of $\\chi'$-chromatic sum and $\\chi^+$-chromatic sum are introduced in this paper. The extended graph $G^x$ of a graph $G$ was recently introduced for certain regular graphs. This paper furthers the concepts of $\\chi'$-chromatic sum and $\\chi^+$-chromatic sum to extended paths and cycles. Bipartite graphs also receive some attention. The paper concludes with patterned structured graphs. These last said graphs are typically found in chemical and biological structures.

On a conjecture concerning helly circle graphs

Directory of Open Access Journals (Sweden)

Durán Guillermo

2003-01-01

Full Text Available We say that G is an e-circle graph if there is a bijection between its vertices and straight lines on the cartesian plane such that two vertices are adjacent in G if and only if the corresponding lines intersect inside the circle of radius one. This definition suggests a method for deciding whether a given graph G is an e-circle graph, by constructing a convenient system S of equations and inequations which represents the structure of G, in such a way that G is an e-circle graph if and only if S has a solution. In fact, e-circle graphs are exactly the circle graphs (intersection graphs of chords in a circle, and thus this method provides an analytic way for recognizing circle graphs. A graph G is a Helly circle graph if G is a circle graph and there exists a model of G by chords such that every three pairwise intersecting chords intersect at the same point. A conjecture by Durán (2000 states that G is a Helly circle graph if and only if G is a circle graph and contains no induced diamonds (a diamond is a graph formed by four vertices and five edges. Many unsuccessful efforts - mainly based on combinatorial and geometrical approaches - have been done in order to validate this conjecture. In this work, we utilize the ideas behind the definition of e-circle graphs and restate this conjecture in terms of an equivalence between two systems of equations and inequations, providing a new, analytic tool to deal with it.

Some results from the combinatorial approach to quantum logic

International Nuclear Information System (INIS)

Greechie, R.J.

1976-01-01

The combinatorial approach to quantum logic focuses on certain interconnections between graphs, combinatorial designs, and convex sets as applied to a quantum logic. This article is concerned only with orthomodular lattices and associated structures. A class of complete atomic irreducible semimodular orthomodular lattices is derived which may not be represented as linear subspaces of a vector space over a division ring. Each of these lattices is a proposition system of dimension three. These proposition systems form orthocomplemented non-Desarguesian projective geometries. (B.R.H.)

Efficient parallel and out of core algorithms for constructing large bi-directed de Bruijn graphs

Directory of Open Access Journals (Sweden)

Vaughn Matthew

2010-11-01

Full Text Available Abstract Background Assembling genomic sequences from a set of overlapping reads is one of the most fundamental problems in computational biology. Algorithms addressing the assembly problem fall into two broad categories - based on the data structures which they employ. The first class uses an overlap/string graph and the second type uses a de Bruijn graph. However with the recent advances in short read sequencing technology, de Bruijn graph based algorithms seem to play a vital role in practice. Efficient algorithms for building these massive de Bruijn graphs are very essential in large sequencing projects based on short reads. In an earlier work, an O(n/p time parallel algorithm has been given for this problem. Here n is the size of the input and p is the number of processors. This algorithm enumerates all possible bi-directed edges which can overlap with a node and ends up generating Θ(nΣ messages (Σ being the size of the alphabet. Results In this paper we present a Θ(n/p time parallel algorithm with a communication complexity that is equal to that of parallel sorting and is not sensitive to Σ. The generality of our algorithm makes it very easy to extend it even to the out-of-core model and in this case it has an optimal I/O complexity of Θ(nlog(n/BBlog(M/B (M being the main memory size and B being the size of the disk block. We demonstrate the scalability of our parallel algorithm on a SGI/Altix computer. A comparison of our algorithm with the previous approaches reveals that our algorithm is faster - both asymptotically and practically. We demonstrate the scalability of our sequential out-of-core algorithm by comparing it with the algorithm used by VELVET to build the bi-directed de Bruijn graph. Our experiments reveal that our algorithm can build the graph with a constant amount of memory, which clearly outperforms VELVET. We also provide efficient algorithms for the bi-directed chain compaction problem. Conclusions The bi

Efficient parallel and out of core algorithms for constructing large bi-directed de Bruijn graphs.

Science.gov (United States)

Kundeti, Vamsi K; Rajasekaran, Sanguthevar; Dinh, Hieu; Vaughn, Matthew; Thapar, Vishal

2010-11-15

Assembling genomic sequences from a set of overlapping reads is one of the most fundamental problems in computational biology. Algorithms addressing the assembly problem fall into two broad categories - based on the data structures which they employ. The first class uses an overlap/string graph and the second type uses a de Bruijn graph. However with the recent advances in short read sequencing technology, de Bruijn graph based algorithms seem to play a vital role in practice. Efficient algorithms for building these massive de Bruijn graphs are very essential in large sequencing projects based on short reads. In an earlier work, an O(n/p) time parallel algorithm has been given for this problem. Here n is the size of the input and p is the number of processors. This algorithm enumerates all possible bi-directed edges which can overlap with a node and ends up generating Θ(nΣ) messages (Σ being the size of the alphabet). In this paper we present a Θ(n/p) time parallel algorithm with a communication complexity that is equal to that of parallel sorting and is not sensitive to Σ. The generality of our algorithm makes it very easy to extend it even to the out-of-core model and in this case it has an optimal I/O complexity of Θ(nlog(n/B)Blog(M/B)) (M being the main memory size and B being the size of the disk block). We demonstrate the scalability of our parallel algorithm on a SGI/Altix computer. A comparison of our algorithm with the previous approaches reveals that our algorithm is faster--both asymptotically and practically. We demonstrate the scalability of our sequential out-of-core algorithm by comparing it with the algorithm used by VELVET to build the bi-directed de Bruijn graph. Our experiments reveal that our algorithm can build the graph with a constant amount of memory, which clearly outperforms VELVET. We also provide efficient algorithms for the bi-directed chain compaction problem. The bi-directed de Bruijn graph is a fundamental data structure for

Optimization Problems on Threshold Graphs

Directory of Open Access Journals (Sweden)

Elena Nechita

2010-06-01

Full Text Available During the last three decades, different types of decompositions have been processed in the field of graph theory. Among these we mention: decompositions based on the additivity of some characteristics of the graph, decompositions where the adjacency law between the subsets of the partition is known, decompositions where the subgraph induced by every subset of the partition must have predeterminate properties, as well as combinations of such decompositions. In this paper we characterize threshold graphs using the weakly decomposition, determine: density and stability number, Wiener index and Wiener polynomial for threshold graphs.

Hierarchy of modular graph identities

Energy Technology Data Exchange (ETDEWEB)

D’Hoker, Eric; Kaidi, Justin [Mani L. Bhaumik Institute for Theoretical Physics, Department of Physics and Astronomy,University of California,Los Angeles, CA 90095 (United States)

2016-11-09

The low energy expansion of Type II superstring amplitudes at genus one is organized in terms of modular graph functions associated with Feynman graphs of a conformal scalar field on the torus. In earlier work, surprising identities between two-loop graphs at all weights, and between higher-loop graphs of weights four and five were constructed. In the present paper, these results are generalized in two complementary directions. First, all identities at weight six and all dihedral identities at weight seven are obtained and proven. Whenever the Laurent polynomial at the cusp is available, the form of these identities confirms the pattern by which the vanishing of the Laurent polynomial governs the full modular identity. Second, the family of modular graph functions is extended to include all graphs with derivative couplings and worldsheet fermions. These extended families of modular graph functions are shown to obey a hierarchy of inhomogeneous Laplace eigenvalue equations. The eigenvalues are calculated analytically for the simplest infinite sub-families and obtained by Maple for successively more complicated sub-families. The spectrum is shown to consist solely of eigenvalues s(s−1) for positive integers s bounded by the weight, with multiplicities which exhibit rich representation-theoretic patterns.

Hierarchy of modular graph identities

International Nuclear Information System (INIS)

D’Hoker, Eric; Kaidi, Justin

2016-01-01

The low energy expansion of Type II superstring amplitudes at genus one is organized in terms of modular graph functions associated with Feynman graphs of a conformal scalar field on the torus. In earlier work, surprising identities between two-loop graphs at all weights, and between higher-loop graphs of weights four and five were constructed. In the present paper, these results are generalized in two complementary directions. First, all identities at weight six and all dihedral identities at weight seven are obtained and proven. Whenever the Laurent polynomial at the cusp is available, the form of these identities confirms the pattern by which the vanishing of the Laurent polynomial governs the full modular identity. Second, the family of modular graph functions is extended to include all graphs with derivative couplings and worldsheet fermions. These extended families of modular graph functions are shown to obey a hierarchy of inhomogeneous Laplace eigenvalue equations. The eigenvalues are calculated analytically for the simplest infinite sub-families and obtained by Maple for successively more complicated sub-families. The spectrum is shown to consist solely of eigenvalues s(s−1) for positive integers s bounded by the weight, with multiplicities which exhibit rich representation-theoretic patterns.

Well-covered graphs and factors

DEFF Research Database (Denmark)

Randerath, Bert; Vestergaard, Preben D.

2006-01-01

A maximum independent set of vertices in a graph is a set of pairwise nonadjacent vertices of largest cardinality α. Plummer defined a graph to be well-covered, if every independent set is contained in a maximum independent set of G. Every well-covered graph G without isolated vertices has a perf...

On the centrality of some graphs

Directory of Open Access Journals (Sweden)

Vecdi Aytac

2017-10-01

Full Text Available A central issue in the analysis of complex networks is the assessment of their stability and vulnerability. A variety of measures have been proposed in the literature to quantify the stability of networks and a number of graph-theoretic parameters have been used to derive formulas for calculating network reliability. Different measures for graph vulnerability have been introduced so far to study different aspects of the graph behavior after removal of vertices or links such as connectivity, toughness, scattering number, binding number, residual closeness and integrity. In this paper, we consider betweenness centrality of a graph. Betweenness centrality of a vertex of a graph is portion of the shortest paths all pairs of vertices passing through a given vertex. In this paper, we obtain exact values for betweenness centrality for some wheel related graphs namely gear, helm, sunflower and friendship graphs.

Enabling Graph Appliance for Genome Assembly

Energy Technology Data Exchange (ETDEWEB)

Singh, Rina [ORNL; Graves, Jeffrey A [ORNL; Lee, Sangkeun (Matt) [ORNL; Sukumar, Sreenivas R [ORNL; Shankar, Mallikarjun [ORNL

2015-01-01

In recent years, there has been a huge growth in the amount of genomic data available as reads generated from various genome sequencers. The number of reads generated can be huge, ranging from hundreds to billions of nucleotide, each varying in size. Assembling such large amounts of data is one of the challenging computational problems for both biomedical and data scientists. Most of the genome assemblers developed have used de Bruijn graph techniques. A de Bruijn graph represents a collection of read sequences by billions of vertices and edges, which require large amounts of memory and computational power to store and process. This is the major drawback to de Bruijn graph assembly. Massively parallel, multi-threaded, shared memory systems can be leveraged to overcome some of these issues. The objective of our research is to investigate the feasibility and scalability issues of de Bruijn graph assembly on Cray s Urika-GD system; Urika-GD is a high performance graph appliance with a large shared memory and massively multithreaded custom processor designed for executing SPARQL queries over large-scale RDF data sets. However, to the best of our knowledge, there is no research on representing a de Bruijn graph as an RDF graph or finding Eulerian paths in RDF graphs using SPARQL for potential genome discovery. In this paper, we address the issues involved in representing a de Bruin graphs as RDF graphs and propose an iterative querying approach for finding Eulerian paths in large RDF graphs. We evaluate the performance of our implementation on real world ebola genome datasets and illustrate how genome assembly can be accomplished with Urika-GD using iterative SPARQL queries.

On 4-critical t-perfect graphs

OpenAIRE

Benchetrit, Yohann

2016-01-01

It is an open question whether the chromatic number of $t$-perfect graphs is bounded by a constant. The largest known value for this parameter is 4, and the only example of a 4-critical $t$-perfect graph, due to Laurent and Seymour, is the complement of the line graph of the prism $\\Pi$ (a graph is 4-critical if it has chromatic number 4 and all its proper induced subgraphs are 3-colorable). In this paper, we show a new example of a 4-critical $t$-perfect graph: the complement of the line gra...

Local adjacency metric dimension of sun graph and stacked book graph

Science.gov (United States)

Yulisda Badri, Alifiah; Darmaji

2018-03-01

A graph is a mathematical system consisting of a non-empty set of nodes and a set of empty sides. One of the topics to be studied in graph theory is the metric dimension. Application in the metric dimension is the navigation robot system on a path. Robot moves from one vertex to another vertex in the field by minimizing the errors that occur in translating the instructions (code) obtained from the vertices of that location. To move the robot must give different instructions (code). In order for the robot to move efficiently, the robot must be fast to translate the code of the nodes of the location it passes. so that the location vertex has a minimum distance. However, if the robot must move with the vertex location on a very large field, so the robot can not detect because the distance is too far.[6] In this case, the robot can determine its position by utilizing location vertices based on adjacency. The problem is to find the minimum cardinality of the required location vertex, and where to put, so that the robot can determine its location. The solution to this problem is the dimension of adjacency metric and adjacency metric bases. Rodrguez-Velzquez and Fernau combine the adjacency metric dimensions with local metric dimensions, thus becoming the local adjacency metric dimension. In the local adjacency metric dimension each vertex in the graph may have the same adjacency representation as the terms of the vertices. To obtain the local metric dimension of values in the graph of the Sun and the stacked book graph is used the construction method by considering the representation of each adjacent vertex of the graph.

Mechatronic modeling and simulation using bond graphs

CERN Document Server

Das, Shuvra

2009-01-01

Introduction to Mechatronics and System ModelingWhat Is Mechatronics?What Is a System and Why Model Systems?Mathematical Modeling Techniques Used in PracticeSoftwareBond Graphs: What Are They?Engineering SystemsPortsGeneralized VariablesBond GraphsBasic Components in SystemsA Brief Note about Bond Graph Power DirectionsSummary of Bond Direction RulesDrawing Bond Graphs for Simple Systems: Electrical and MechanicalSimplification Rules for Junction StructureDrawing Bond Graphs for Electrical SystemsDrawing Bond Graphs for Mechanical SystemsCausalityDrawing Bond Graphs for Hydraulic and Electronic Components and SystemsSome Basic Properties and Concepts for FluidsBond Graph Model of Hydraulic SystemsElectronic SystemsDeriving System Equations from Bond GraphsSystem VariablesDeriving System EquationsTackling Differential CausalityAlgebraic LoopsSolution of Model Equations and Their InterpretationZeroth Order SystemsFirst Order SystemsSecond Order SystemTransfer Functions and Frequency ResponsesNumerical Solution ...

Quantum control and representation theory

International Nuclear Information System (INIS)

Ibort, A; Perez-Pardo, J M

2009-01-01

A new notion of controllability for quantum systems that takes advantage of the linear superposition of quantum states is introduced. We call such a notion von Neumann controllability, and it is shown that it is strictly weaker than the usual notion of pure state and operator controllability. We provide a simple and effective characterization of it by using tools from the theory of unitary representations of Lie groups. In this sense, we are able to approach the problem of control of quantum states from a new perspective, that of the theory of unitary representations of Lie groups. A few examples of physical interest and the particular instances of compact and nilpotent dynamical Lie groups are discussed

Numerical characteristics of quantum computer simulation

Science.gov (United States)

Chernyavskiy, A.; Khamitov, K.; Teplov, A.; Voevodin, V.; Voevodin, Vl.

2016-12-01

The simulation of quantum circuits is significantly important for the implementation of quantum information technologies. The main difficulty of such modeling is the exponential growth of dimensionality, thus the usage of modern high-performance parallel computations is relevant. As it is well known, arbitrary quantum computation in circuit model can be done by only single- and two-qubit gates, and we analyze the computational structure and properties of the simulation of such gates. We investigate the fact that the unique properties of quantum nature lead to the computational properties of the considered algorithms: the quantum parallelism make the simulation of quantum gates highly parallel, and on the other hand, quantum entanglement leads to the problem of computational locality during simulation. We use the methodology of the AlgoWiki project (algowiki-project.org) to analyze the algorithm. This methodology consists of theoretical (sequential and parallel complexity, macro structure, and visual informational graph) and experimental (locality and memory access, scalability and more specific dynamic characteristics) parts. Experimental part was made by using the petascale Lomonosov supercomputer (Moscow State University, Russia). We show that the simulation of quantum gates is a good base for the research and testing of the development methods for data intense parallel software, and considered methodology of the analysis can be successfully used for the improvement of the algorithms in quantum information science.

Expert interpretation of bar and line graphs: The role of graphicacy in reducing the effect of graph format.

Directory of Open Access Journals (Sweden)

David ePeebles

2015-10-01

Full Text Available The distinction between informational and computational equivalence of representations, first articulated by Larkin and Simon (1987 has been a fundamental principle in the analysis of diagrammatic reasoning which has been supported empirically on numerous occasions. We present an experiment that investigates this principle in relation to the performance of expert graph users of 2 x 2 'interaction' bar and line graphs. The study sought to determine whether expert interpretation is affected by graph format in the same way that novice interpretations are. The findings revealed that, unlike novices - and contrary to the assumptions of several graph comprehension models - experts' performance was the same for both graph formats, with their interpretation of bar graphs being no worse than that for line graphs. We discuss the implications of the study for guidelines for presenting such data and for models of expert graph comprehension.

Proving termination of graph transformation systems using weighted type graphs over semirings

NARCIS (Netherlands)

Bruggink, H.J.S.; König, B.; Nolte, D.; Zantema, H.; Parisi-Presicce, F.; Westfechtel, B.

2015-01-01

We introduce techniques for proving uniform termination of graph transformation systems, based on matrix interpretations for string rewriting. We generalize this technique by adapting it to graph rewriting instead of string rewriting and by generalizing to ordered semirings. In this way we obtain a

Quantum mechanical resonances

International Nuclear Information System (INIS)

Cisneros S, A.; McIntosh, H.V.

1982-01-01

A discussion of the nature of quantum mechanical resonances is presented from the point of view of the spectral theory of operators. In the case of Bohr-Feshbach resonances, graphs are presented to illustrate the theory showing the decay of a doubly excited metastable state and the excitation of the resonance by an incident particle with proper energy. A characterization of resonances is given as well as a procedure to determine widths using the spectral density function. A sufficient condition is given for the validity of the Breit-Wigner formula for Bohr-Feshbach resonances. (author)

In search of fundamental discreteness in (2 + 1)-dimensional quantum gravity

NARCIS (Netherlands)

Budd, T.G.; Loll, R.

2009-01-01

Inspired by previous work in (2 + 1)-dimensional quantum gravity, which found evidence for a discretization of time in the quantum theory, we reexamine the issue for the case of pure Lorentzian gravity with vanishing cosmological constant and spatially compact universes of genus g ≥ 2. Taking the

DIMENSI METRIK GRAPH LOBSTER Ln (q;r

Directory of Open Access Journals (Sweden)

PANDE GDE DONY GUMILAR

2013-05-01

Full Text Available The metric dimension of connected graph G is the cardinality of minimum resolving set in graph G. In this research, we study how to find the metric dimension of lobster graph Ln (q;r. Lobster graph Ln (q;r is a regular lobster graph with vertices backbone on the main path, every backbone vertex is connected to q hand vertices and every hand vertex is connected to r finger vertices, with n, q, r element of N. We obtain the metric dimension of lobster graph L2 (1;1 is 1, the metric dimension of lobster graph L2 (1;1 for n > 2 is 2.