- Nov 26 2015 cond-mat.str-el quant-ph arXiv:1511.08090v1Quantum tensor network states and more particularly projected entangled-pair states provide a natural framework for representing ground states of gapped, topologically ordered systems. The defining feature of these representations is that topological order is a consequence of the symmetry of the underlying tensors in terms of matrix product operators. In this paper, we present a systematic study of those matrix product operators, and show how this relates entanglement properties of projected entangled-pair states to the formalism of fusion tensor categories. From the matrix product operators we construct a C*-algebra and find that topological sectors can be identified with the central idempotents of this algebra. This allows us to construct projected entangled-pair states containing an arbitrary number of anyons. Properties such as topological spin, the S matrix, fusion and braiding relations can readily be extracted from the idempotents. As the matrix product operator symmetries are acting purely on the virtual level of the tensor network, the ensuing Wilson loops are not fattened when perturbing the system, and this opens up the possibility of simulating topological theories away from renormalization group fixed points. We illustrate the general formalism for the special cases of discrete gauge theories and string-net models.
- A pure quantum state is called $k$-uniform if all its reductions to $k$-qudit are maximally mixed. We investigate the general constructions of $k$-uniform pure quantum states of $n$ subsystems with $d$ levels. We provide one construction via symmetric matrices and the second one through classical error-correcting codes. There are three main results arising from our constructions. Firstly, we show that for any given even $n\ge 2$, there always exists an $n/2$-uniform $n$-qudit quantum state of level $p$ for sufficiently large prime $p$. Secondly, both constructions show that their exist $k$-uniform $n$-qudit pure quantum states such that $k$ is proportional to $n$, i.e., $k=\Omega(n)$ although the construction from symmetric matrices outperforms the one by error-correcting codes. Thirdly, our symmetric matrix construction provides a positive answer to the open question in \citeDA on whether there exists $3$-uniform $n$-qudit pure quantum state for all $n\ge 8$. In fact, we can further prove that, for every $k$, there exists a constant $M_k$ such that there exists a $k$-uniform $n$-qudit quantum state for all $n\ge M_k$. In addition, by using concatenation of algebraic geometry codes, we give an explicit construction of $k$-uniform quantum state when $k$ tends to infinity.
- Nov 26 2015 cs.CC arXiv:1511.08113v1We give an introduction to some of the recent ideas that go under the name ``geometric complexity theory''. We first sketch the proof of the known upper and lower bounds for the determinantal complexity of the permanent. We then introduce the concept of a representation theoretic obstruction, which has close links to algebraic combinatorics, and we explain some of the insights gained so far. In particular, we address very recent insights on the complexity of testing the positivity of Kronecker coefficients. We also briefly discuss the related asymptotic version of this question.
- Nov 26 2015 cs.CC arXiv:1511.08189v1We show that the Graph Automorphism problem is ZPP-reducible to MKTP, the problem of minimizing time-bounded Kolmogorov complexity. MKTP has previously been studied in connection with the Minimum Circuit Size Problem (MCSP) and is often viewed as essentially a different encoding of MCSP. All prior reductions to MCSP have applied equally well to MKTP, and vice-versa, and all such reductions have relied on the fact that functions computable in polynomial time can be inverted with high probability relative to MCSP and MKTP. Our reduction uses a different approach, and consequently yields the first example of a problem -- other than MKTP itself -- that is in ZPP^MKTP but that is not known to lie in NP intersect coNP. We also show that this approach can be used to provide a reduction of the Graph Isomorphism problem to MKTP.
- Nov 26 2015 quant-ph physics.chem-ph arXiv:1511.08161v1Boson Sampling represents a promising witness of the supremacy of quantum systems as a resource for the solution of computational problems. The classical hardness of Boson Sampling has been related to the so called Permanent-of-Gaussians Conjecture and has been extended to some generalizations such as scattershot Boson Sampling, approximate and lossy sampling under some reasonable constraints. However, it is still unclear how demanding these bounds are for a quantum experimental sampler. Starting from a state of the art analysis and focusing on the foreseeable practical conditions needed to reach quantum supremacy, we look at different techniques and present a more general and effective solution. We apply our approach to both the experimental suggestions presented to date and we eventually find in both cases a new threshold that is less error sensitive and experimentally more feasible.
- A method is discussed to analyze the dynamics of a dissipative quantum system. The method hinges upon the definition of an alternative (time-dependent) product among the observables of the system. In the long time limit this yields a contracted algebra. This contraction irreversibly affects some of the quantum features of the dissipative system.
- Despite the tremendous empirical success of equivalence principle, there are several theoretical motivations for existence of a preferred reference frame (or aether) in a consistent theory of quantum gravity. However, if quantum gravity had a preferred reference frame, why would high energy processes enjoy such a high degree of Lorentz symmetry? While this is often considered as an argument against aether, here I provide three independent arguments for why perturbative unitarity (or weak coupling) of the Lorentz-violating effective field theories put stringent constraints on possible observable violations of Lorentz symmetry at high energies. In particular, the interaction with the scalar graviton in a consistent low-energy theory of gravity and a (radiatively and dynamically) stable cosmological framework, leads to these constraints. The violation (quantified by the relative difference in maximum speed of propagation) is limited to $\lesssim 10^{-10} E({\rm eV})^{-4}$ (superseding all current empirical bounds), or the theory will be strongly coupled beyond meV scale. The latter happens in extended Horava-Lifshitz gravities, as a result of a previously ignored quantum anomaly. Finally, given that all cosmologically viable theories with significant Lorentz violation appear to be strongly coupled beyond meV scale, we conjecture that, similar to color confinement in QCD, or Vainshetin screening for massive gravity, high energy theories (that interact with gravity) are shielded from Lorentz violation (at least, up to the scale where gravity is UV-completed). In contrast, microwave or radio photons, cosmic background neutrinos, or gravitational waves may provide more promising candidates for discovery of violations of Lorentz symmetry.
- In this paper, we show how to create paraphrastic sentence embeddings using the Paraphrase Database (Ganitkevitch et al., 2013), an extensive semantic resource with millions of phrase pairs. We consider several compositional architectures and evaluate them on 24 textual similarity datasets encompassing domains such as news, tweets, web forums, news headlines, machine translation output, glosses, and image and video captions. We present the interesting result that simple compositional architectures based on updated vector averaging vastly outperform long short-term memory (LSTM) recurrent neural networks and that these simpler architectures allow us to learn models with superior generalization. Our models are efficient, very easy to use, and competitive with task-tuned systems. We make them available to the research community1 with the hope that they can serve as the new baseline for further work on universal paraphrastic sentence embeddings.
- The development of intelligent machines is one of the biggest unsolved challenges in computer science. In this paper, we propose some fundamental properties these machines should have, focusing in particular on communication and learning. We discuss a simple environment that could be used to incrementally teach a machine the basics of natural-language-based communication, as a prerequisite to more complex interaction with human users. We also present some conjectures on the sort of algorithms the machine should support in order to profitably learn from the environment.
- We study the effective field theory of KKLT and LVS moduli stabilisation scenarios coupled to an anti-D3-brane at the tip of a warped throat. We describe the presence of the anti-brane in terms of a nilpotent goldstino superfield in a supersymmetric effective field theory. The introduction of this superfield produces a term that can lead to a de Sitter minimum. We fix the Kaehler moduli dependence of the nilpotent field couplings by matching this term with the anti-D3-brane uplifting contribution. The main result of this paper is the computation, within this EFT, of the soft supersymmetry breaking terms in both KKLT and LVS for matter living on D3-brane (leaving the D7-brane analysis to an appendix). A handful of distinct phenomenological scenarios emerge that could have low energy implications, most of them having a split spectrum of soft masses. Some cosmological and phenomenological properties of these models are discussed. We also check that the attraction between the D3-brane and the anti-D3-brane does not affect the leading contribution to the soft masses and does not destabilise the system.
- In this work we deal with the problem of high-level event detection in video. Specifically, we study the challenging problems of i) learning to detect video events from solely a textual description of the event, without using any positive video examples, and ii) additionally exploiting very few positive training samples together with a small number of ``related'' videos. For learning only from an event's textual description, we first identify a general learning framework and then study the impact of different design choices for various stages of this framework. For additionally learning from example videos, when true positive training samples are scarce, we employ an extension of the Support Vector Machine that allows us to exploit ``related'' event videos by automatically introducing different weights for subsets of the videos in the overall training set. Experimental evaluations performed on the large-scale TRECVID MED 2014 video dataset provide insight on the effectiveness of the proposed methods.
- Embedding learning, a.k.a. representation learning, has been shown to be able to model large-scale semantic knowledge graphs. A key concept is a mapping of the knowledge graph to a tensor representation whose entries are predicted by models using latent representations of generalized entities. In recent publications the embedding models were extended to also consider temporal evolutions, temporal patterns and subsymbolic representations. These extended models were used successfully to predict clinical events like procedures, lab measurements, and diagnoses. In this paper, we attempt to map these embedding models, which were developed purely as solutions to technical problems, to various cognitive memory functions, in particular to semantic and concept memory, episodic memory and sensory memory. We also make an analogy between a predictive model, which uses entity representations derived in memory models, to working memory. Cognitive memory functions are typically classified as long-term or short-term memory, where long-term memory has the subcategories declarative memory and non-declarative memory and the short term memory has the subcategories sensory memory and working memory. There is evidence that these main cognitive categories are partially dissociated from one another in the brain, as expressed in their differential sensitivity to brain damage. However, there is also evidence indicating that the different memory functions are not mutually independent. A hypothesis that arises out off this work is that mutual information exchange can be achieved by sharing or coupling of distributed latent representations of entities across different memory functions.
- Nov 26 2015 cs.LG arXiv:1511.07948v1We study non-convex empirical risk minimization for learning halfspaces and neural networks. For loss functions that are $L$-Lipschitz continuous, we present algorithms to learn halfspaces and multi-layer neural networks that achieve arbitrarily small excess risk $\epsilon>0$. The time complexity is polynomial in the input dimension $d$ and the sample size $n$, but exponential in the quantity $(L/\epsilon^2)\log(L/\epsilon)$. These algorithms run multiple rounds of random initialization followed by arbitrary optimization steps. We further show that if the data is separable by some neural network with constant margin $\gamma>0$, then there is a polynomial-time algorithm for learning a neural network that separates the training data with margin $\Omega(\gamma)$. As a consequence, the algorithm achieves arbitrary generalization error $\epsilon>0$ with ${\rm poly}(d,1/\epsilon)$ sample and time complexity. We establish the same learnability result when the labels are randomly flipped with probability $\eta<1/2$.
- Nov 26 2015 math.CO arXiv:1511.07920v1The minimum rank problem is to determine for a graph $G$ the smallest rank of a Hermitian (or real symmetric) matrix whose off-diagonal zero-nonzero pattern is that of the adjacency matrix of $G$. Here $G$ is taken to be a circulant graph, and only circulant matrices are considered. The resulting graph parameter is termed the minimum circulant rank of the graph. This value is determined for every circulant graph in which a vertex neighborhood forms a consecutive set, and in this case is shown to coincide with the usual minimum rank. Under the additional restriction to positive semidefinite matrices, the resulting parameter is shown to be equal to the smallest number of dimensions in which the graph has an orthogonal representation with a certain symmetry property, and also to the smallest number of terms appearing among a certain family of polynomials determined by the graph. This value is then determined when the number of vertices is prime. The analogous parameter over the reals is also investigated.
- Person detection is a key problem for many computer vision tasks. While face detection has reached maturity, detecting people under a full variation of camera view-points, human poses, lighting conditions and occlusions is still a difficult challenge. In this work we focus on detecting human heads in natural scenes. Starting from the recent local R-CNN object detector, we extend it with two types of contextual cues. First, we leverage person-scene relations and propose a Global CNN model trained to predict positions and scales of heads directly from the full image. Second, we explicitly model pairwise relations among objects and train a Pairwise CNN model using a structured-output surrogate loss. The Local, Global and Pairwise models are combined into a joint CNN framework. To train and test our full model, we introduce a large dataset composed of 369,846 human heads annotated in 224,740 movie frames. We evaluate our method and demonstrate improvements of person head detection against several recent baselines in three datasets. We also show improvements of the detection speed provided by our model.
- The rnn package provides components for implementing a wide range of Recurrent Neural Networks. It is built withing the framework of the Torch distribution for use with the nn package. The components have evolved from 3 iterations, each adding to the flexibility and capability of the package. All component modules inherit either the AbstractRecurrent or AbstractSequencer classes. Strong unit testing, continued backwards compatibility and access to supporting material are the principles followed during its development. The package is compared against existing implementations of two published papers.
- Nov 26 2015 physics.chem-ph physics.comp-ph arXiv:1511.07883v1Obtaining the exciton dynamics of large photosynthetic complexes by using mixed quantum mechanics/molecular mechanics (QM/MM) is computationally demanding. We propose a machine learning technique, multi-layer perceptrons, as a tool to reduce the time required to compute excited state energies. With this approach we predict time-dependent density functional theory (TDDFT) excited state energies of bacteriochlorophylls in the Fenna-Matthews-Olson (FMO) complex. Additionally we compute spectral densities and exciton populations from the predictions. Different methods to determine multi-layer perceptron training sets are introduced, leading to several initial data selections. In addition, we compute spectral densities and exciton populations. Once multi-layer perceptrons are trained, predicting excited state energies was found to be significantly faster than the corresponding QM/MM calculations. We showed that multi-layer perceptrons can successfully reproduce the energies of QM/MM calculations to a high degree of accuracy with prediction errors contained within 0.01 eV (0.5%). Spectral densities and exciton dynamics are also in agreement with the TDDFT results. The acceleration and accurate prediction of dynamics strongly encourage the combination of machine learning techniques with ab-initio methods.
- Cold atoms with laser-induced spin-orbit (SO) interactions provide intriguing new platforms to explore novel quantum physics beyond natural conditions of solids. Recent experiments demonstrated the one-dimensional (1D) SO coupling for boson and fermion gases. However, realization of 2D SO interaction, a much more important task, remains very challenging. Here we propose and experimentally realize, for the first time, 2D SO coupling and topological band with $^{87}$Rb degenerate gas through a minimal optical Raman lattice scheme, without relying on phase locking or fine tuning of optical potentials. A controllable crossover between 2D and 1D SO couplings is studied, and the SO effects and nontrivial band topology are observed by measuring the atomic cloud distribution and spin texture in the momentum space. Our realization of 2D SO coupling with advantages of small heating and topological stability opens a broad avenue in cold atoms to study exotic quantum phases, including the highly-sought-after topological superfluid phases.
- Nov 26 2015 astro-ph.SR astro-ph.GA arXiv:1511.08204v1
- Nov 26 2015 astro-ph.SR astro-ph.GA arXiv:1511.08203v1
- Nov 26 2015 astro-ph.CO arXiv:1511.08200v1
- Nov 26 2015 astro-ph.GA arXiv:1511.08199v1
- Nov 26 2015 cond-mat.mes-hall arXiv:1511.08196v1
- Nov 26 2015 astro-ph.CO gr-qc arXiv:1511.08195v1
- Nov 26 2015 q-fin.MF arXiv:1511.08194v1
- Nov 26 2015 math.AP arXiv:1511.08193v1
- Nov 26 2015 cond-mat.mtrl-sci arXiv:1511.08192v1
- Nov 26 2015 math.CA arXiv:1511.08191v1
- Nov 26 2015 stat.ME arXiv:1511.08190v1
- Nov 26 2015 hep-ph arXiv:1511.08188v1
- Nov 26 2015 hep-th arXiv:1511.08187v1
- Nov 26 2015 math.DS arXiv:1511.08184v1
- Nov 26 2015 gr-qc arXiv:1511.08183v1
- Nov 26 2015 stat.OT arXiv:1511.08180v1
- Nov 26 2015 cs.CV arXiv:1511.08177v1
- Nov 26 2015 math.NT arXiv:1511.08176v1
- Nov 26 2015 cond-mat.mes-hall arXiv:1511.08175v1
- Nov 26 2015 hep-ph arXiv:1511.08174v1
- Nov 26 2015 math.NT arXiv:1511.08172v1
- Nov 26 2015 astro-ph.SR arXiv:1511.08171v1
- Nov 26 2015 astro-ph.HE arXiv:1511.08168v1
- Nov 26 2015 cs.CV arXiv:1511.08166v1