The Point of Continuity Property: Descriptive Complexity and Ordinal Index

∗ Supported by D.G.I.C.Y.T. Project No. PB93-1142

An edge-based matching kernel through discrete-time quantum walks

In this paper, we propose a new edge-based matching kernel for graphs by using discrete-time quantum walks. To this end, we commence by transforming a graph into a directed line graph. The reasons of using the line graph structure are twofold. First, for a graph, its directed line graph is a dual representation and each vertex of the line graph represents a corresponding edge in the original graph. Second, we show that the discrete-time quantum walk can be seen as a walk on the line graph and the state space of the walk is the vertex set of the line graph, i.e., the state space of the walk is the edges of the original graph. As a result, the directed line graph provides an elegant way of developing new edge-based matching kernel based on discrete-time quantum walks. For a pair of graphs, we compute the h-layer depth-based representation for each vertex of their directed line graphs by computing entropic signatures (computed from discrete-time quantum walks on the line graphs) on the family of K-layer expansion subgraphs rooted at the vertex, i.e., we compute the depth-based representations for edges of the original graphs through their directed line graphs. Based on the new representations, we define an edge-based matching method for the pair of graphs by aligning the h-layer depth-based representations computed through the directed line graphs. The new edge-based matching kernel is thus computed by counting the number of matched vertices identified by the matching method on the directed line graphs. Experiments on standard graph datasets demonstrate the effectiveness of our new kernel.

A quantum Jensen-Shannon graph kernel for unattributed graphs

In this paper, we use the quantum Jensen-Shannon divergence as a means of measuring the information theoretic dissimilarity of graphs and thus develop a novel graph kernel. In quantum mechanics, the quantum Jensen-Shannon divergence can be used to measure the dissimilarity of quantum systems specified in terms of their density matrices. We commence by computing the density matrix associated with a continuous-time quantum walk over each graph being compared. In particular, we adopt the closed form solution of the density matrix introduced in Rossi et al. (2013) [27,28] to reduce the computational complexity and to avoid the cumbersome task of simulating the quantum walk evolution explicitly. Next, we compare the mixed states represented by the density matrices using the quantum Jensen-Shannon divergence. With the quantum states for a pair of graphs described by their density matrices to hand, the quantum graph kernel between the pair of graphs is defined using the quantum Jensen-Shannon divergence between the graph density matrices. We evaluate the performance of our kernel on several standard graph datasets from both bioinformatics and computer vision. The experimental results demonstrate the effectiveness of the proposed quantum graph kernel.

A quantum Jensen-Shannon graph kernel using the continuous-time quantum walk

In this paper, we use the quantum Jensen-Shannon divergence as a means to establish the similarity between a pair of graphs and to develop a novel graph kernel. In quantum theory, the quantum Jensen-Shannon divergence is defined as a distance measure between quantum states. In order to compute the quantum Jensen-Shannon divergence between a pair of graphs, we first need to associate a density operator with each of them. Hence, we decide to simulate the evolution of a continuous-time quantum walk on each graph and we propose a way to associate a suitable quantum state with it. With the density operator of this quantum state to hand, the graph kernel is defined as a function of the quantum Jensen-Shannon divergence between the graph density operators. We evaluate the performance of our kernel on several standard graph datasets from bioinformatics. We use the Principle Component Analysis (PCA) on the kernel matrix to embed the graphs into a feature space for classification. The experimental results demonstrate the effectiveness of the proposed approach. © 2013 Springer-Verlag.

Manifold learning and the quantum Jensen-Shannon divergence kernel

The quantum Jensen-Shannon divergence kernel [1] was recently introduced in the context of unattributed graphs where it was shown to outperform several commonly used alternatives. In this paper, we study the separability properties of this kernel and we propose a way to compute a low-dimensional kernel embedding where the separation of the different classes is enhanced. The idea stems from the observation that the multidimensional scaling embeddings on this kernel show a strong horseshoe shape distribution, a pattern which is known to arise when long range distances are not estimated accurately. Here we propose to use Isomap to embed the graphs using only local distance information onto a new vectorial space with a higher class separability. The experimental evaluation shows the effectiveness of the proposed approach. © 2013 Springer-Verlag.

Efficient computation of decoherent quantum walks through eigenvalue perturbation

A number of recent studies have investigated the introduction of decoherence in quantum walks and the resulting transition to classical random walks. Interestingly,it has been shown that algorithmic properties of quantum walks with decoherence such as the spreading rate are sometimes better than their purely quantum counterparts. Not only quantum walks with decoherence provide a generalization of quantum walks that naturally encompasses both the quantum and classical case, but they also give rise to new and different probability distribution. The application of quantum walks with decoherence to large graphs is limited by the necessity of evolving state vector whose sizes quadratic in the number of nodes of the graph, as opposed to the linear state vector of the purely quantum (or classical) case. In this technical report,we show how to use perturbation theory to reduce the computational complexity of evolving a continuous-time quantum walk subject to decoherence. More specifically, given a graph over n nodes, we show how to approximate the eigendecomposition of the n2×n2 Lindblad super-operator from the eigendecomposition of the n×n graph Hamiltonian.

Spatial ecological complexity measures in GRASS GIS

Good estimates of ecosystem complexity are essential for a number of ecological tasks: from biodiversity estimation, to forest structure variable retrieval, to feature extraction by edge detection and generation of multifractal surface as neutral models for e.g. feature change assessment. Hence, measuring ecological complexity over space becomes crucial in macroecology and geography. Many geospatial tools have been advocated in spatial ecology to estimate ecosystem complexity and its changes over space and time. Among these tools, free and open source options especially offer opportunities to guarantee the robustness of algorithms and reproducibility. In this paper we will summarize the most straightforward measures of spatial complexity available in the Free and Open Source Software GRASS GIS, relating them to key ecological patterns and processes.

Significant quantum effects in hydrogen activation

Dissociation of molecular hydrogen is an important step in a wide variety of chemical, biological, and physical processes. Due to the light mass of hydrogen, it is recognized that quantum effects are often important to its reactivity. However, understanding how quantum effects impact the reactivity of hydrogen is still in its infancy. Here, we examine this issue using a well-defined Pd/Cu(111) alloy that allows the activation of hydrogen and deuterium molecules to be examined at individual Pd atom surface sites over a wide range of temperatures. Experiments comparing the uptake of hydrogen and deuterium as a function of temperature reveal completely different behavior of the two species. The rate of hydrogen activation increases at lower sample temperature, whereas deuterium activation slows as the temperature is lowered. Density functional theory simulations in which quantum nuclear effects are accounted for reveal that tunneling through the dissociation barrier is prevalent for H2 up to ∼190 K and for D2 up to ∼140 K. Kinetic Monte Carlo simulations indicate that the effective barrier to H2 dissociation is so low that hydrogen uptake on the surface is limited merely by thermodynamics, whereas the D2 dissociation process is controlled by kinetics. These data illustrate the complexity and inherent quantum nature of this ubiquitous and seemingly simple chemical process. Examining these effects in other systems with a similar range of approaches may uncover temperature regimes where quantum effects can be harnessed, yielding greater control of bond-breaking processes at surfaces and uncovering useful chemistries such as selective bond activation or isotope separation.

Comparison of different space indexing methods for ecological evaluation of urban openspaces

Nowadays we meet many different evaluation methods regarding the ecological performance of green surfaces and parks. All these methods are extremely valuable in determining how well a green surface performs from ecological aspect and to what extent the environment were damaged if these sites would be built or would be developed any other way causing reduction of green surfaces. The goal of the article is to clarify the differences between two evaluation methods (GSI – Green Space Intensity, BARC – Biological Activity Rate Calculation) suitable for urban green infrastructure analysis and to see if any significant difference can be observed evaluating the same site by these methods. Our research sites are in Budapest and their sizes vary between 2,5-8 acres. The most important aspects of site analysis are the following: size and boundaries of the park, existence or lack of water features, the characteristics of their surfaces and the complexity of vegetation. We summarize the data of the site analysis in tables, make a summarizing diagram for visual representation and draw conclusions from the results. As a final step, we evaluate how these two evaluation systems relate to urban open space developments.

Space time coding for polynomial phase modulated signals

Polynomial phase modulated (PPM) signals have been shown to provide improved error rate performance with respect to conventional modulation formats under additive white Gaussian noise and fading channels in single-input single-output (SISO) communication systems. In this dissertation, systems with two and four transmit antennas using PPM signals were presented. In both cases we employed full-rate space-time block codes in order to take advantage of the multipath channel. For two transmit antennas, we used the orthogonal space-time block code (OSTBC) proposed by Alamouti and performed symbol-wise decoding by estimating the phase coefficients of the PPM signal using three different methods: maximum-likelihood (ML), sub-optimal ML (S-ML) and the high-order ambiguity function (HAF). In the case of four transmit antennas, we used the full-rate quasi-OSTBC (QOSTBC) proposed by Jafarkhani. However, in order to ensure the best error rate performance, PPM signals were selected such as to maximize the QOSTBC’s minimum coding gain distance (CGD). Since this method does not always provide a unique solution, an additional criterion known as maximum channel interference coefficient (CIC) was proposed. Through Monte Carlo simulations it was shown that by using QOSTBCs along with the properly selected PPM constellations based on the CGD and CIC criteria, full diversity in flat fading channels and thus, low BER at high signal-to-noise ratios (SNR) can be ensured. Lastly, the performance of symbol-wise decoding for QOSTBCs was evaluated. In this case a quasi zero-forcing method was used to decouple the received signal and it was shown that although this technique reduces the decoding complexity of the system, there is a penalty to be paid in terms of error rate performance at high SNRs.

Site controlled red-yellow-green light emitting InGaN quantum discs on nano-tipped GaN rods

We report a method of growing site controlled InGaN multiple quantum discs (QDs) at uniform wafer scale on coalescence free ultra-high density (>80%) nanorod templates by metal organic chemical vapour deposition (MOCVD). The dislocation and coalescence free nature of the GaN space filling nanorod arrays eliminates the well-known emission problems seen in InGaN based visible light sources that these types of crystallographic defects cause. Correlative scanning transmission electron microscopy (STEM), energy-dispersive X-ray (EDX) mapping and cathodoluminescence (CL) hyperspectral imaging illustrates the controlled site selection of the red, yellow and green (RYG) emission at these nano tips. This article reveals that the nanorod tips' broad emission in the RYG visible range is in fact achieved by manipulating the InGaN QD's confinement dimensions, rather than significantly increasing the In%. This article details the easily controlled method of manipulating the QDs dimensions producing high crystal quality InGaN without complicated growth conditions needed for strain relaxation and alloy compositional changes seen for bulk planar GaN templates.

Macroscopic Quantum Resonators (MAQRO): 2015 update

Do the laws of quantum physics still hold for macroscopic objects - this is at the heart of Schrödinger’s cat paradox - or do gravitation or yet unknown effects set a limit for massive particles? What is the fundamental relation between quantum physics and gravity? Ground-based experiments addressing these questions may soon face limitations due to limited free-fall times and the quality of vacuum and microgravity. The proposed mission Macroscopic Quantum Resonators (MAQRO) may overcome these limitations and allow addressing such fundamental questions. MAQRO harnesses recent developments in quantum optomechanics, high-mass matter-wave interferometry as well as state-of-the-art space technology to push macroscopic quantum experiments towards their ultimate performance limits and to open new horizons for applying quantum technology in space. The main scientific goal is to probe the vastly unexplored ‘quantum-classical’ transition for increasingly massive objects, testing the predictions of quantum theory for objects in a size and mass regime unachievable in ground-based experiments. The hardware will largely be based on available space technology. Here, we present the MAQRO proposal submitted in response to the 4th Cosmic Vision call for a medium-sized mission (M4) in 2014 of the European Space Agency (ESA) with a possible launch in 2025, and we review the progress with respect to the original MAQRO proposal for the 3rd Cosmic Vision call for a medium-sized mission (M3) in 2010. In particular, the updated proposal overcomes several critical issues of the original proposal by relying on established experimental techniques from high-mass matter-wave interferometry and by introducing novel ideas for particle loading and manipulation. Moreover, the mission design was improved to better fulfill the stringent environmental requirements for macroscopic quantum experiments.

The Quantum Tetrahedron in 3 and 4 Dimensions

Recent work on state sum models of quantum gravity in 3 and 4 dimensions has led to interest in the `quantum tetrahedron'. Starting with a classical phase space whose points correspond to geometries of the tetrahedron in R^3, we use geometric quantization to obtain a Hilbert space of states. This Hilbert space has a basis of states labeled by the areas of the faces of the tetrahedron together with one more quantum number, e.g. the area of one of the parallelograms formed by midpoints of the tetrahedron's edges. Repeating the procedure for the tetrahedron in R^4, we obtain a Hilbert space with a basis labelled solely by the areas of the tetrahedron's faces. An analysis of this result yields a geometrical explanation of the otherwise puzzling fact that the quantum tetrahedron has more degrees of freedom in 3 dimensions than in 4 dimensions.

Geometrical measurements in three-dimensional quantum gravity

A set of observables is described for the topological quantum field theory which describes quantum gravity in three space-time dimensions with positive signature and positive cosmological constant. The simplest examples measure the distances between points, giving spectra and probabilities which have a geometrical interpretation. The observables are related to the evaluation of relativistic spin networks by a Fourier transform.