Search

Most of the common graph layout principles (a.k.a. "aesthetics") on which many graph drawing algorithms are based are easy to define and to perceive. For example, the number of pairs of edges that cross each other, how symmetric a drawing looks, the aspect ratio of the bounding box, or the angular resolution at the nodes. The extent to which a graph drawing conforms to these principles can be determined by looking at how it is drawn -- that is, by looking at the marks on the page -- without consideration for the underlying structure of the graph. A key layout principle is that of optimising `stress', the basis for many algorithms such as the popular Kamada \& Kawai algorithm and several force-directed algorithms. The stress of a graph drawing is, loosely speaking, the extent to which the geometric distance between each pair of nodes is proportional to the shortest path between them -- over the whole graph drawing. The definition of stress therefore relies on the underlying structure of the graph (the `paths') in a way that other layout principles do not, making stress difficult to describe to novices unfamiliar with graph drawing principles, and, we believe, difficult to perceive. We conducted an experiment to see whether people (novices as well as experts) can see stress in graph drawings, and found that it is possible to train novices to `see' stress -- even if their perception strategies are not based on the definitional concepts., Comment: To appear in GD2024

Stress is among the most commonly employed quality metrics and optimization criteria for dimension reduction projections of high dimensional data. Complex, high dimensional data is ubiquitous across many scientific disciplines, including machine learning, biology, and the social sciences. One of the primary methods of visualizing these datasets is with two dimensional scatter plots that visually capture some properties of the data. Because visually determining the accuracy of these plots is challenging, researchers often use quality metrics to measure projection accuracy or faithfulness to the full data. One of the most commonly employed metrics, normalized stress, is sensitive to uniform scaling of the projection, despite this act not meaningfully changing anything about the projection. We investigate the effect of scaling on stress and other distance based quality metrics analytically and empirically by showing just how much the values change and how this affects dimension reduction technique evaluations. We introduce a simple technique to make normalized stress scale invariant and show that it accurately captures expected behavior on a small benchmark.

The normalized stress metric measures how closely distances between vertices in a graph drawing match the graph-theoretic distances between those vertices. It is one of the most widely employed quality metrics for graph drawing, and is even the optimization goal of several popular graph layout algorithms. However, normalized stress can be misleading when used to compare the outputs of two or more algorithms, as it is sensitive to the size of the drawing compared to the graph-theoretic distances used. Uniformly scaling a layout will change the value of stress despite not meaningfully changing the drawing. In fact, the change in stress values can be so significant that a clearly better layout can appear to have a worse stress score than a random layout. In this paper, we study different variants for calculating stress used in the literature (raw stress, normalized stress, etc.) and show that many of them are affected by this problem, which threatens the validity of experiments that compare the quality of one algorithm to that of another. We then experimentally justify one of the stress calculation variants, scale-normalized stress, as one that fairly compares drawing outputs regardless of their size. We also describe an efficient computation for scale-normalized stress and provide an open source implementation.

Superconducting qubits provide a promising approach to large-scale fault-tolerant quantum computing. However, qubit connectivity on a planar surface is typically restricted to only a few neighboring qubits. Achieving longer-range and more flexible connectivity, which is particularly appealing in light of recent developments in error-correcting codes, however usually involves complex multi-layer packaging and external cabling, which is resource-intensive and can impose fidelity limitations. Here, we propose and realize a high-speed on-chip quantum processor that supports reconfigurable all-to-all coupling with a large on-off ratio. We implement the design in a four-node quantum processor, built with a modular design comprising a wiring substrate coupled to two separate qubit-bearing substrates, each including two single-qubit nodes. We use this device to demonstrate reconfigurable controlled-Z gates across all qubit pairs, with a benchmarked average fidelity of $96.00\%\pm0.08\%$ and best fidelity of $97.14\%\pm0.07\%$, limited mainly by dephasing in the qubits. We also generate multi-qubit entanglement, distributed across the separate modules, demonstrating GHZ-3 and GHZ-4 states with fidelities of $88.15\%\pm0.24\%$ and $75.18\%\pm0.11\%$, respectively. This approach promises efficient scaling to larger-scale quantum circuits, and offers a pathway for implementing quantum algorithms and error correction schemes that benefit from enhanced qubit connectivity.

We treat the problem of finding transitive subgroups G of S_n containing normal subgroups N_1 and N_2, with N_1 transitive and N_2 not transitive, such that G/N_1 is isomorphic G/N_2. We show that such G exist whenever n has a prime factor that also divides the Euler-phi function of n. We show that no such G exist when n = pq for p < q with p not dividing q-1.

Beyond their origin in modeling many-body quantum systems, tensor networks have emerged as a promising class of models for solving machine learning problems, notably in unsupervised generative learning. While possessing many desirable features arising from their quantum-inspired nature, tensor network generative models have previously been largely restricted to binary or categorical data, limiting their utility in real-world modeling problems. We overcome this by introducing a new family of tensor network generative models for continuous data, which are capable of learning from distributions containing continuous random variables. We develop our method in the setting of matrix product states, first deriving a universal expressivity theorem proving the ability of this model family to approximate any reasonably smooth probability density function with arbitrary precision. We then benchmark the performance of this model on several synthetic and real-world datasets, finding that the model learns and generalizes well on distributions of continuous and discrete variables. We develop methods for modeling different data domains, and introduce a trainable compression layer which is found to increase model performance given limited memory or computational resources. Overall, our methods give important theoretical and empirical evidence of the efficacy of quantum-inspired methods for the rapidly growing field of generative learning., Comment: 21 pages, 15 figures

Quantum communication testbeds provide a useful resource for experimentally investigating a variety of communication protocols. Here we demonstrate a superconducting circuit testbed with bidirectional multi-photon state transfer capability using time-domain shaped wavepackets. The system we use to achieve this comprises two remote nodes, each including a tunable superconducting transmon qubit and a tunable microwave-frequency resonator, linked by a 2 m-long superconducting coplanar waveguide, which serves as a transmission line. We transfer both individual and superposition Fock states between the two remote nodes, and additionally show that this bidirectional state transfer can be done simultaneously, as well as used to entangle elements in the two nodes., Comment: Main Paper has 6 pages, 4 figures. Supplementary has 14 pages, 16 figures, 2 tables

We present a method for balancing between the Local and Global Structures (LGS) in graph embedding, via a tunable parameter. Some embedding methods aim to capture global structures, while others attempt to preserve local neighborhoods. Few methods attempt to do both, and it is not always possible to capture well both local and global information in two dimensions, which is where most graph drawing live. The choice of using a local or a global embedding for visualization depends not only on the task but also on the structure of the underlying data, which may not be known in advance. For a given graph, LGS aims to find a good balance between the local and global structure to preserve. We evaluate the performance of LGS with synthetic and real-world datasets and our results indicate that it is competitive with the state-of-the-art methods, using established quality metrics such as stress and neighborhood preservation. We introduce a novel quality metric, cluster distance preservation, to assess intermediate structure capture. All source-code, datasets, experiments and analysis are available online., Comment: Appears in the Proceedings of the 31st International Symposium on Graph Drawing and Network Visualization (GD 2023)

Interpreting a node-link graph is enhanced if similar subgraphs (or motifs) are depicted in a similar manner; that is, they have the same visual form. Small motifs within graphs may be perceived to be identical when they are structurally dissimilar, or may be perceived to be dissimilar when they are identical. This issue primarily relates to the Gestalt principle of similarity, but may also include an element of quick, low-level pattern-matching. We believe that if motifs are identical, they should be depicted identically; if they are nearly-identical, they should be depicted nearly-identically. This principle is particularly important in domains where motifs hold meaning and where their identification is important. We identified five small motifs: bi-cliques, cliques, cycles, double-cycles, and stars. For each, we defined visual variations on two dimensions: same or different structure, same or different shape. We conducted a crowd-sourced empirical study to test the perception of similarity of these varied motifs, and found that determining whether motifs are identical or similar is affected by both shape and structure., Comment: Appears in the Proceedings of the 31st International Symposium on Graph Drawing and Network Visualization (GD 2023)

In the field of quantum computation and communication there is a compelling need for quantum-coherent frequency conversion between microwave electronics and infra-red optics. A promising platform for this is an optomechanical crystal resonator that uses simultaneous photonic and phononic crystals to create a co-localized cavity coupling an electromagnetic mode to an acoustic mode, which then via electromechanical interactions can undergo direct transduction to electronics. The majority of work in this area has been on one-dimensional nanobeam resonators which provide strong optomechanical couplings but, due to their geometry, suffer from an inability to dissipate heat produced by the laser pumping required for operation. Recently, a quasi-two-dimensional optomechanical crystal cavity was developed in silicon exhibiting similarly strong coupling with better thermalization, but at a mechanical frequency above optimal qubit operating frequencies. Here we adapt this design to gallium arsenide, a natural thin-film single-crystal piezoelectric that can incorporate electromechanical interactions, obtaining a mechanical resonant mode at f_m ~ 4.5 GHz ideal for superconducting qubits, and demonstrating optomechanical coupling g_om/(2pi) ~ 650 kHz.

In circuit quantum electrodynamics (QED), qubits are typically measured using dispersively-coupled readout resonators. Coupling between each readout resonator and its electrical environment however reduces the qubit lifetime via the Purcell effect. Inserting a Purcell filter counters this effect while maintaining high readout fidelity, but reduces measurement bandwidth and thus limits multiplexing readout capacity. In this letter, we develop and implement a multi-stage bandpass Purcell filter that yields better qubit protection while simultaneously increasing measurement bandwidth and multiplexed capacity. We report on the experimental performance of our transmission-line--based implementation of this approach, a flexible design that can easily be integrated with current scaled-up, long coherence time superconducting quantum processors.

Linear optical quantum computing provides a desirable approach to quantum computing, with a short list of required elements. The similarity between photons and phonons points to the interesting potential for linear mechanical quantum computing (LMQC), using phonons in place of photons. While single-phonon sources and detectors have been demonstrated, a phononic beamsplitter element remains an outstanding requirement. Here we demonstrate such an element, using two superconducting qubits to fully characterize a beamsplitter with single phonons. We further use the beamsplitter to demonstrate two-phonon interference, a requirement for two-qubit gates, completing the toolbox needed for LMQC. This advance brings linear quantum computing to a fully solid-state system, along with straightforward conversion between itinerant phonons and superconducting qubits.

With the advent of quantum and quantum-inspired machine learning, adapting the structure of learning models to match the structure of target datasets has been shown to be crucial for obtaining high performance. Probabilistic models based on tensor networks (TNs) are prime candidates to benefit from data-dependent design considerations, owing to their bias towards correlations which are local with respect to the topology of the model. In this work, we use methods from spectral graph theory to search for optimal permutations of model sites which are adapted to the structure of an input dataset. Our method uses pairwise mutual information estimates from the target dataset to ensure that strongly correlated bits are placed closer to each other relative to the model's topology. We demonstrate the effectiveness of such preprocessing for probabilistic modeling tasks, finding substantial improvements in the performance of generative models based on matrix product states (MPS) across a variety of datasets. We also show how spectral embedding, a dimensionality reduction technique from spectral graph theory, can be used to gain further insights into the structure of datasets of interest., Comment: 9 pages, 5 figures

The rapid pace of recent advancements in numerical computation, notably the rise of GPU and TPU hardware accelerators, have allowed tensor network (TN) algorithms to scale to even larger quantum simulation problems, and to be employed more broadly for solving machine learning tasks. The "quantum-inspired" nature of TNs permits them to be mapped to parametrized quantum circuits (PQCs), a fact which has inspired recent proposals for enhancing the performance of TN algorithms using near-term quantum devices, as well as enabling joint quantum-classical training frameworks which benefit from the distinct strengths of TN and PQC models. However, the success of any such methods depends on efficient and accurate methods for approximating TN states using realistic quantum circuits, something which remains an unresolved question. In this work, we compare a range of novel and previously-developed algorithmic protocols for decomposing matrix product states (MPS) of arbitrary bond dimensions into low-depth quantum circuits consisting of stacked linear layers of two-qubit unitaries. These protocols are formed from different combinations of a preexisting analytical decomposition scheme with constrained optimization of circuit unitaries, and all possess efficient classical runtimes. Our experimental results reveal one particular protocol, involving sequential growth and optimization of the quantum circuit, to outperform all other methods, with even greater benefits seen in the setting of limited computational resources. Given these promising results, we expect our proposed decomposition protocol to form a useful ingredient within any joint application of TNs and PQCs, in turn further unlocking the rich and complementary benefits of classical and quantum computation., Comment: 11 pages, 4 figures

We describe an efficient and scalable spherical graph embedding method. The method uses a generalization of the Euclidean stress function for Multi-Dimensional Scaling adapted to spherical space, where geodesic pairwise distances are employed instead of Euclidean distances. The resulting spherical stress function is optimized by means of stochastic gradient descent. Quantitative and qualitative evaluations demonstrate the scalability and effectiveness of the proposed method. We also show that some graph families can be embedded with lower distortion on the sphere, than in Euclidean and hyperbolic spaces., Comment: Appears in the Proceedings of the 30th International Symposium on Graph Drawing and Network Visualization (GD 2022)

While recent breakthroughs have proven the ability of noisy intermediate-scale quantum (NISQ) devices to achieve quantum advantage in classically-intractable sampling tasks, the use of these devices for solving more practically relevant computational problems remains a challenge. Proposals for attaining practical quantum advantage typically involve parametrized quantum circuits (PQCs), whose parameters can be optimized to find solutions to diverse problems throughout quantum simulation and machine learning. However, training PQCs for real-world problems remains a significant practical challenge, largely due to the phenomenon of barren plateaus in the optimization landscapes of randomly-initialized quantum circuits. In this work, we introduce a scalable procedure for harnessing classical computing resources to provide pre-optimized initializations for PQCs, which we show significantly improves the trainability and performance of PQCs on a variety of problems. Given a specific optimization task, this method first utilizes tensor network (TN) simulations to identify a promising quantum state, which is then converted into gate parameters of a PQC by means of a high-performance decomposition procedure. We show that this learned initialization avoids barren plateaus, and effectively translates increases in classical resources to enhanced performance and speed in training quantum circuits. By demonstrating a means of boosting limited quantum resources using classical computers, our approach illustrates the promise of this synergy between quantum and quantum-inspired models in quantum computing, and opens up new avenues to harness the power of modern quantum hardware for realizing practical quantum advantage., Comment: 15 pages, 7 figures

When visualizing a high-dimensional dataset, dimension reduction techniques are commonly employed which provide a single 2-dimensional view of the data. We describe ENS-t-SNE: an algorithm for Embedding Neighborhoods Simultaneously that generalizes the t-Stochastic Neighborhood Embedding approach. By using different viewpoints in ENS-t-SNE's 3D embedding, one can visualize different types of clusters within the same high-dimensional dataset. This enables the viewer to see and keep track of the different types of clusters, which is harder to do when providing multiple 2D embeddings, where corresponding points cannot be easily identified. We illustrate the utility of ENS-t-SNE with real-world applications and provide an extensive quantitative evaluation with datasets of different types and sizes.

Hyperbolic geometry offers a natural focus + context for data visualization and has been shown to underlie real-world complex networks. However, current hyperbolic network visualization approaches are limited to special types of networks and do not scale to large datasets. With this in mind, we designed, implemented, and analyzed three methods for hyperbolic visualization of networks in the browser based on inverse projections, generalized force-directed algorithms, and hyperbolic multi-dimensional scaling (H-MDS). A comparison with Euclidean MDS shows that H-MDS produces embeddings with lower distortion for several types of networks. All three methods can handle node-link representations and are available in fully functional web-based systems., Comment: To appear in IEEE PacificVis 2022

We develop a photon energy measurement scheme for single photon counting Microwave Kinetic Inductance Detectors (MKIDs) that uses principal component analysis (PCA) to measure the energy of an incident photon from the signal ("photon pulse") generated by the detector. PCA can be used to characterize a photon pulse using an arbitrarily large number of features and therefore PCA-based energy measurement does not rely on the assumption of an energy-independent pulse shape that is made in standard filtering techniques. A PCA-based method for energy measurement is especially useful in applications where the detector is operating near its saturation energy and pulse shape varies strongly with photon energy. It has been shown previously that PCA using two principal components can be used as an energy-measurement scheme. We extend upon these ideas and develop a method for measuring the energies of photons by characterizing their pulse shapes using any number of principal components and any number of calibration energies. Applying this technique with 50 principal components, we show improvements to a previously-reported energy resolution for Thermal Kinetic Inductance Detectors (TKIDs) from 75 eV to 43 eV at 5.9 keV. We also apply this technique with 50 principal components to data from an optical to near-IR MKID and achieve energy resolutions that are consistent with the best results from existing analysis techniques.

We investigate a correspondence between two formalisms for discrete probabilistic modeling: probabilistic graphical models (PGMs) and tensor networks (TNs), a powerful modeling framework for simulating complex quantum systems. The graphical calculus of PGMs and TNs exhibits many similarities, with discrete undirected graphical models (UGMs) being a special case of TNs. However, more general probabilistic TN models such as Born machines (BMs) employ complex-valued hidden states to produce novel forms of correlation among the probabilities. While representing a new modeling resource for capturing structure in discrete probability distributions, this behavior also renders the direct application of standard PGM tools impossible. We aim to bridge this gap by introducing a hybrid PGM-TN formalism that integrates quantum-like correlations into PGM models in a principled manner, using the physically-motivated concept of decoherence. We first prove that applying decoherence to the entirety of a BM model converts it into a discrete UGM, and conversely, that any subgraph of a discrete UGM can be represented as a decohered BM. This method allows a broad family of probabilistic TN models to be encoded as partially decohered BMs, a fact we leverage to combine the representational strengths of both model families. We experimentally verify the performance of such hybrid models in a sequential modeling task, and identify promising uses of our method within the context of existing applications of graphical models., Comment: 18 pages, 11 figures

Pandemic control measures like lock-down, restrictions on restaurants and gatherings, social-distancing have shown to be effective in curtailing the spread of COVID-19. However, their sustained enforcement has negative economic effects. To craft strategies and policies that reduce the hardship on the people and the economy while being effective against the pandemic, authorities need to understand the disease dynamics at the right geo-spatial granularity. Considering factors like the hospitals' ability to handle the fluctuating demands, evaluating various reopening scenarios, and accurate forecasting of cases are vital to decision making. Towards this end, we present a flexible end-to-end solution that seamlessly integrates public health data with tertiary client data to accurately estimate the risk of reopening a community. At its core lies a state-of-the-art prediction model that auto-captures changing trends in transmission and mobility. Benchmarking against various published baselines confirm the superiority of our forecasting algorithm. Combined with the ability to extend to multiple client-specific requirements and perform deductive reasoning through counter-factual analysis, this solution provides actionable insights to multiple client domains ranging from government to educational institutions, hospitals, and commercial establishments., Comment: 9 pages, 11 figures

Modeling joint probability distributions over sequences has been studied from many perspectives. The physics community developed matrix product states, a tensor-train decomposition for probabilistic modeling, motivated by the need to tractably model many-body systems. But similar models have also been studied in the stochastic processes and weighted automata literature, with little work on how these bodies of work relate to each other. We address this gap by showing how stationary or uniform versions of popular quantum tensor network models have equivalent representations in the stochastic processes and weighted automata literature, in the limit of infinitely long sequences. We demonstrate several equivalence results between models used in these three communities: (i) uniform variants of matrix product states, Born machines and locally purified states from the quantum tensor networks literature, (ii) predictive state representations, hidden Markov models, norm-observable operator models and hidden quantum Markov models from the stochastic process literature,and (iii) stochastic weighted automata, probabilistic automata and quadratic automata from the formal languages literature. Such connections may open the door for results and methods developed in one area to be applied in another.

Recurrent neural networks (RNNs) are powerful tools for sequential modeling, but typically require significant overparameterization and regularization to achieve optimal performance. This leads to difficulties in the deployment of large RNNs in resource-limited settings, while also introducing complications in hyperparameter selection and training. To address these issues, we introduce a "fully tensorized" RNN architecture which jointly encodes the separate weight matrices within each recurrent cell using a lightweight tensor-train (TT) factorization. This approach represents a novel form of weight sharing which reduces model size by several orders of magnitude, while still maintaining similar or better performance compared to standard RNNs. Experiments on image classification and speaker verification tasks demonstrate further benefits for reducing inference times and stabilizing model training and hyperparameter selection.

Tensor Networks (TN) offer a powerful framework to efficiently represent very high-dimensional objects. TN have recently shown their potential for machine learning applications and offer a unifying view of common tensor decomposition models such as Tucker, tensor train (TT) and tensor ring (TR). However, identifying the best tensor network structure from data for a given task is challenging. In this work, we leverage the TN formalism to develop a generic and efficient adaptive algorithm to jointly learn the structure and the parameters of a TN from data. Our method is based on a simple greedy approach starting from a rank one tensor and successively identifying the most promising tensor network edges for small rank increments. Our algorithm can adaptively identify TN structures with small number of parameters that effectively optimize any differentiable objective function. Experiments on tensor decomposition, tensor completion and model compression tasks demonstrate the effectiveness of the proposed algorithm. In particular, our method outperforms the state-of-the-art evolutionary topology search [Li and Sun, 2020] for tensor decomposition of images (while being orders of magnitude faster) and finds efficient tensor network structures to compress neural networks outperforming popular TT based approaches [Novikov et al., 2015].

Tensor networks are a powerful modeling framework developed for computational many-body physics, which have only recently been applied within machine learning. In this work we utilize a uniform matrix product state (u-MPS) model for probabilistic modeling of sequence data. We first show that u-MPS enable sequence-level parallelism, with length-n sequences able to be evaluated in depth O(log n). We then introduce a novel generative algorithm giving trained u-MPS the ability to efficiently sample from a wide variety of conditional distributions, each one defined by a regular expression. Special cases of this algorithm correspond to autoregressive and fill-in-the-blank sampling, but more complex regular expressions permit the generation of richly structured data in a manner that has no direct analogue in neural generative models. Experiments on sequence modeling with synthetic and real text data show u-MPS outperforming a variety of baselines and effectively generalizing their predictions in the presence of limited data., Comment: 18 pages, 2 figures; v4 conference version; v3 link to code for experiments; v2 major revision with new main result on regular expression sampling. International Conference on Artificial Intelligence and Statistics. PMLR, 2021

While quantum speed-up in solving certain decision problems by a fault-tolerant universal quantum computer has been promised, a timely research interest includes how far one can reduce the resource requirement to demonstrate a provable advantage in quantum devices without demanding quantum error correction, which is crucial for prolonging the coherence time of qubits. We propose a model device made of locally-interacting multiple qubits, designed such that simultaneous single-qubit measurements on it can output probability distributions whose average-case sampling is classically intractable, under similar assumptions as the sampling of non-interacting bosons and instantaneous quantum circuits. Notably, in contrast to these previous unitary-based realizations, our measurement-based implementation has two distinctive features. (i) Our implementation involves no adaptation of measurement bases, leading output probability distributions to be generated in constant time, independent of the system size. Thus, it could be implemented in principle without quantum error correction. (ii) Verifying the classical intractability of our sampling is done by changing the Pauli measurement bases only at certain output qubits. Our usage of random commuting quantum circuits in place of computationally universal circuits allows a unique unification of sampling and verification, so that they require the same physical resource requirements in contrast to the more demanding verification protocols seen elsewhere in the literature., Comment: 15 pages, 2 figures. v2: published version

An emerging insight is that ground states of symmetry-protected topological orders (SPTO's) possess latent computational complexity in terms of their many-body entanglement. By introducing a fractional symmetry of SPTO, which requires the invariance under 3-colorable symmetries of a lattice, we prove that every renormalization fixed-point state of 2D $(\mathbb{Z}_2)^m$ SPTO with fractional symmetry can be utilized for universal quantum computation using only Pauli measurements, as long as it belongs to a nontrivial 2D SPTO phase. Our infinite family of fixed-point states may serve as a base model to demonstrate the idea of a "quantum computational phase" of matter, whose states share universal computational complexity ubiquitously., Comment: 17 pages, 4 figures. v2: published version, contains a new appendix dealing with renormalization methods

Stochastic Boolean networks, or more generally, stochastic discrete networks, are an important class of computational models for molecular interaction networks. The stochasticity stems from the updating schedule. Standard updating schedules include the synchronous update, where all the nodes are updated at the same time, and the asynchronous update where a random node is updated at each time step. The former produces a deterministic dynamics while the latter a stochastic dynamics. A more general stochastic setting considers propensity parameters for updating each node. Stochastic Discrete Dynamical Systems (SDDS) is a modeling framework that considers two propensity parameters for updating each node and uses one when the update has a positive impact on the variable, that is, when the update causes the variable to increase its value, and uses the other when the update has a negative impact, that is, when the update causes it to decrease its value. This framework offers additional features for simulations but also adds a complexity in parameter estimation of the propensities. This paper presents a method for estimating the propensity parameters for SDDS. The method is based on adding noise to the system using the Google PageRank approach to make the system ergodic and thus guaranteeing the existence of a stationary distribution. Then with the use of a genetic algorithm, the propensity parameters are estimated. Approximation techniques that make the search algorithms efficient are also presented and Matlab/Octave code to test the algorithms are available at http://www.ms.uky.edu/~dmu228/GeneticAlg/Code.html., Comment: 20 pages, 4 figures, 2 tables

Measurement-based quantum computation (MQC) is a paradigm for studying quantum computation using many-body entanglement and single-qubit measurements. While MQC has inspired wide-ranging discoveries throughout quantum information, our understanding of the general principles underlying MQC seems to be biased by its historical reliance upon the archetypal 2D cluster state. Here, we utilize recent advances in the subject of symmetry-protected topological order (SPTO) to introduce a novel MQC resource state, whose physical and computational behavior differs fundamentally from the cluster state. We show that, in sharp contrast to the cluster state, our state enables universal quantum computation using only measurements of single-qubit Pauli X, Y, and Z operators. This novel computational feature is related to the "genuine" 2D SPTO possessed by our state, and which is absent in the cluster state. Our concrete connection between the latent computational complexity of many-body systems and macroscopic quantum orders may find applications in quantum many-body simulation for benchmarking classically intractable complexity., Comment: 15 pages, 11 figures. v2: new title and improved presentation of results; v3: major revision, with a strengthened main theorem 2 demonstrating the Pauli universality of our resource state; v4: published version

Wasserstein barycenters correspond to optimal solutions of transportation problems for several marginals, and as such have a wide range of applications ranging from economics to statistics and computer science. When the marginal probability measures are absolutely continuous (or vanish on small sets) the theory of Wasserstein barycenters is well-developed (see the seminal paper [1]). However, exact continuous computation of Wasserstein barycenters in this setting is tractable in only a small number of specialized cases. Moreover, in many applications data is given as a set of probability measures with finite support. In this paper, we develop theoretical results for Wasserstein barycenters in this discrete setting. Our results rely heavily on polyhedral theory which is possible due to the discrete structure of the marginals. Our results closely mirror those in the continuous case with a few exceptions. In this discrete setting we establish that Wasserstein barycenters must also be discrete measures and there is always a barycenter which is provably sparse. Moreover, for each Wasserstein barycenter there exists a non-mass-splitting optimal transport to each of the discrete marginals. Such non-mass-splitting transports do not generally exist between two discrete measures unless special mass balance conditions hold. This makes Wasserstein barycenters in this discrete setting special in this regard. We illustrate the results of our discrete barycenter theory with a proof-of-concept computation for a hypothetical transportation problem with multiple marginals: distributing a fixed set of goods when the demand can take on different distributional shapes characterized by the discrete marginal distributions. A Wasserstein barycenter, in this case, represents an optimal distribution of inventory facilities which minimize the squared distance/transportation cost totaled over all demands.

The study of the diameter of the graph of polyhedra is a classical problem in the theory of linear programming. While transportation polytopes are at the core of operations research and statistics it is still open whether the Hirsch conjecture is true for general $m{\times}n$--transportation polytopes. In earlier work the first three authors introduced a hierarchy of variations to the notion of graph diameter in polyhedra. The key reason was that this hierarchy provides some interesting lower bounds for the usual graph diameter. This paper has three contributions: First, we compare the hierarchy of diameters for the $m{\times}n$--transportation polytopes. We show that the Hirsch conjecture bound of $m+n-1$ is actually valid in most of these diameter notions. Second, we prove that for $3{\times}n$--transportation polytopes the Hirsch conjecture holds in the classical graph diameter. Third, we show for $2{\times}n$--transportation polytopes that the stronger monotone Hirsch conjecture holds and improve earlier bounds on the graph diameter.

We investigate entanglement naturally present in the 1D topologically ordered phase protected with the on-site symmetry group of an octahedron as a potential resource for teleportation-based quantum computation. We show that, as long as certain characteristic lengths are finite, all its ground states have the capability to implement any unit-fidelity one-qubit gate operation asymptotically as a key computational building block. This feature is intrinsic to the entire phase, in that perfect gate fidelity coincides with perfect string order parameters under a state-insensitive renormalization procedure. Our approach may pave the way toward a novel program to classify quantum many-body systems based on their operational use for quantum information processing., Comment: 10 pages, 3 figures. v2: published version

Bent-double radio sources have been used as a probe to measure the density of intergalactic gas in galaxy groups. We carry out a series of high-resolution, 3D simulations of AGN jets moving through an external medium with a constant density in order to develop a general formula for the radius of curvature of the jets, and to determine how accurately the density of the intra-group medium (IGM) can be measured. Our simulations produce curved jets ending in bright radio lobes with an extended trail of low surface brightness radio emission. The radius of curvature of the jets varies with time by only about 25%. The radio trail seen in our simulations is typically not detected in known sources, but may be detectable in lower resolution radio observations. The length of this tail can be used to determine the age of the AGN. We also use our simulation data to derive a formula for the kinetic luminosity of observed jets in terms of the radius of curvature and jet pressure. In characterizing how well observations can measure the IGM density, we find that the limited resolution of typical radio observations leads to a systematic under-estimate of the density of about 50%. The unknown angles between the observer and the direction of jet propagation and direction of AGN motion through the IGM leads to an uncertainty of about 50% in estimates of the IGM density. Previous conclusions drawn using these sources, indicating that galaxy groups contain significant reservoirs of baryons in their IGM, are still valid when considering this level of uncertainty. In addition, we model the X-ray emission expected from bent-double radio sources. We find that known sources in reasonably dense environments should be detectable in ~100 ks Chandra observations. X-ray observations of these sources would place constraints on the IGM density and AGN velocity that are complementary to radio observations., Comment: 14 pages, 8 figures, accepted by MNRAS

[Abridged] We present a medium-resolution spectroscopic survey of late-type giant stars at mid-Galactic latitudes of (30$^{\circ}<|b|<60^{\circ}$), designed to probe the properties of this population to distances of $\sim$9 kpc. Because M giants are generally metal-rich and we have limited contamination from thin disk stars by the latitude selection, most of the stars in the survey are expected to be members of the thick disk ($<$[Fe/H]$>\sim$-0.6) with some contribution from the metal-rich component of the nearby halo. Here we report first results for 1799 stars. The distribution of radial velocity (RV) as a function of l for these stars shows (1) the expected thick disk population and (2) local metal-rich halo stars moving at high speeds relative to the disk, that in some cases form distinct sequences in RV-$l$ space. High-resolution echelle spectra taken for 34 of these "RV outliers" reveal the following patterns across the [Ti/Fe]-[Fe/H] plane: seventeen of the stars have abundances reminiscent of the populations present in dwarf satellites of the Milky Way; eight have abundances coincident with those of the Galactic disk and more metal-rich halo; and nine of the stars fall on the locus defined by the majority of stars in the halo. The chemical abundance trends of the RV outliers suggest that this sample consists predominantly of stars accreted from infalling dwarf galaxies. A smaller fraction of stars in the RV outlier sample may have been formed in the inner Galaxy and subsequently kicked to higher eccentricity orbits, but the sample is not large enough to distinguish conclusively between this interpretation and the alternative that these stars represent the tail of the velocity distribution of the thick disk. Our data do not rule out the possibility that a minority of the sample could have formed from gas {\it in situ} on their current orbits., Comment: 43 pages, 9 figures, 4 tables, published in the Astrophysical Journal

In [7], a notion of constant scalar curvature metrics on piecewise flat manifolds is defined. Such metrics are candidates for canonical metrics on discrete manifolds. In this paper, we define a class of vertex transitive metrics on certain triangulations of $\mathbb{S}^3$; namely, the boundary complexes of cyclic polytopes. We use combinatorial properties of cyclic polytopes to show that, for any number of vertices, these metrics have constant scalar curvature., Comment: 15 pages, 4 figures