We present a didactic introduction to adiabatic quantum computation (AQC) via the explicit construction of a classical simulator of quantum computers. This constitutes a suitable route to introduce several important concepts for advanced undergraduates in physics: quantum many-body systems, quantum phase transitions, disordered systems, spin-glasses, and computational complexity theory. (C) 2018 American Association of Physics Teachers. ; The authors want to acknowledge the faculty and students of the Facultad de Informática of UCM (Madrid) for their kind invitation to deliver this crash course, particularly to I. Rodríguez-Laguna and N. Martí. The authors would also like to thank G. Sierra for very useful comments on the manuscript. This work was funded by the Spanish government through Grant Nos. FIS2015-69167-C2-1-P and FIS2015-66020-C2-1-P
Computational complexity theory contains a corpus of theorems and conjectures regarding the time a Turing machine will need to solve certain types of problems as a function of the input size. Nature need not be a Turing machine and, thus, these theorems do not apply directly to it. But classical simulations of physical processes are programs running on Turing machines and, as such, are subject to them. In this work, computational complexity theory is applied to classical simulations of systems performing an adiabatic quantum computation (AQC), based on an annealed extension of the density matrix renormalization group (DMRG). We conjecture that the computational time required for those classical simulations is controlled solely by the maximal entanglement found during the process. Thus, lower bounds on the growth of entanglement with the system size can be provided. In some cases, quantum phase transitions can be predicted to take place in certain inhomogeneous systems. Concretely, physical conclusions are drawn from the assumption that the complexity classes P and NP differ. As a by-product, an alternative measure of entanglement is proposed which, via Chebyshev's inequality, allows us to establish strict bounds on the required computational time. ; This work was supported by the Spanish government by grants FIS2012-33642 and FIS2012-38866-C05-1 and ERC grant QUAGATUA.
We consider a model of power distribution in a social system where a set of agents plays a simple game on a graph: The probability of winning each round is proportional to the agent's current power, and the winner gets more power as a result. We show that when the agents are distributed on simple one-dimensional and two-dimensional networks, inequality grows naturally up to a certain stationary value characterized by a clear division between a higher and a lower class of agents. High class agents are separated by one or several lower class agents which serve as a geometrical barrier preventing further flow of power between them. Moreover, we consider the effect of redistributive mechanisms, such as proportional (nonprogressive) taxation. Sufficient taxation will induce a sharp transition towards a more equal society, and we argue that the critical taxation level is uniquely determined by the system geometry. Interestingly, we find that the roughness and Shannon entropy of the power distributions are a very useful complement to the standard measures of inequality, such as the Gini index and the Lorenz curve ; We acknowledge financial support from the Spanish Government through Grants No. FIS2015-69167-C2-1-P, No. FIS2015-66020-C2- 1-P, and No. PGC2018-094763-B-I00
Average block entanglement in the 1D XX-model with uncorrelated random couplings is known to grow as the logarithm of the block size, in similarity to conformal systems. In this work we study random spin chains whose couplings present long range correlations, generated as gaussian fields with a power-law spectral function. Ground states are always planar valence bond states, and their statistical ensembles are characterized in terms of their block entropy and their bond-length distribution, which follow power-laws. We conjecture the existence of a critical value for the spectral exponent, below which the system behavior is identical to the case of uncorrelated couplings. Above that critical value, the entanglement entropy violates the area law and grows as a power law of the block size, with an exponent which increases from zero to one. Interestingly, we show that XXZ models with positive anisotropy present the opposite behavior, and strong correlations in the couplings lead to lower entropies. Similar planar bond structures are also found in statistical models of RNA folding and kinetic roughening, and we trace an analogy between them and quantum valence bond states. Using an inverse renormalization procedure we determine the optimal spin-chain couplings which give rise to a given planar bond structure, and study the statistical properties of the couplings whose bond structures mimic those found in RNA folding. ; We would like to thank J Cuesta for insights into the statistical mechanics of RNAfolding, and F Iglói and Z Zimborás for useful remarks. This work was funded by grants FIS-2012-33642 and FIS-2012-38866-C05-1,from the Spanish government, QUITEMAD+S2013/ICE-2801 from the Madrid regional government and SEV-2012-0249 of the 'Centro de Excelencia Severo Ochoa' Programme.
We consider a model of a quenched disordered geometry in which a random metric is defined on R-2, which is flat on average and presents short-range correlations. We focus on the statistical properties of balls and geodesics, i.e., circles and straight lines. We show numerically that the roughness of a ball of radius R scales as R-x, with a fluctuation exponent x similar or equal to 1/3, while the lateral spread of the minimizing geodesic between two points at a distance L grows as L-zeta, with wandering exponent value zeta similar or equal to 2/3. Results on related first-passage percolation problems lead us to postulate that the statistics of balls in these random metrics belong to the Kardar-Parisi-Zhang universality class of surface kinetic roughening, with. and. relating to critical exponents characterizing a corresponding interface growth process. Moreover, we check that the one-point and two-point correlators converge to the behavior expected for the Airy-2 process characterized by the Tracy-Widom (TW) probability distribution function of the largest eigenvalue of large random matrices in the Gaussian unitary ensemble (GUE). Nevertheless extreme-value statistics of ball coordinates are given by the TW distribution associated with random matrices in the Gaussian orthogonal ensemble. Furthermore, we also find TW-GUE statistics with good accuracy in arrival times. ; We want to acknowledge very useful discussions with K Takeuchi and S Ferreira. This work has been supported by the Spanish government (MINECO) through grant FIS2012-38866-C05-01. JR-L also acknowledges MINECO grants FIS2012-33642, TOQATA and ERC grant QUAGATUA. TL's research and travel was supported in part by NSF PIRE grant OISE-07-30136.
The discovery of novel entanglement patterns in quantum many- body systems is a prominent research direction in contemporary physics. Here we provide the example of a spin chain with random and inhomogeneous couplings that in the ground state exhibits a very unusual area-law violation. In the clean limit, i.e. without disorder, the model is the rainbow chain and has volume law entanglement. We show that, in the presence of disorder, the entanglement entropy exhibits a power-law growth with the subsystem size, with an exponent 1/2. By employing the strong disorder renormalization group (SDRG) framework, we show that this exponent is related to the survival probability of certain random walks. The ground state of the model exhibits extended regions of short-range singlets (that we term 'bubble' regions) as well as rare long range singlet ('rainbow' regions). Crucially, while the probability of extended rainbow regions decays exponentially with their size, that of the bubble regions is power law. We provide strong numerical evidence for the correctness of SDRG results by exploiting the free-fermion solution of the model. Finally, we investigate the role of interactions by considering the random inhomogeneous XXZ spin chain. Within the SDRG framework and in the strong inhomogeneous limit, we show that the above area-law violation takes place only at the free-fermion point of phase diagram. This point divides two extended regions, which exhibit volume-law and area-law entanglement, respectively. ; SNS has been supported by the Spanish grant No. FIS2015-66020-C2-1-P. JRL and GS have been supported by the Spanish grants No. FIS2015-69167-C2-1-P, QUITEMAD+S2013/ICE-2801 and SEV-2016-0597 of the "Centro de Excelencia Severo Ochoa" Programme. VA acknowledges support from the European Union's Horizon 2020 under the Marie Sklodowoska-Curie grant agreement No 702612 OEMBS. PC acknowledges support from ERC under Consolidator grant number 771536 (NEMO). Part of this work has been carried out during the workshop "Quantum paths" at the Erwin Schrödinger International Institute for Mathematics and Physics (ESI) in Vienna, and during the workshop "Entanglement in Quantum Systems" at the Galileo Galilei Institute (GGI) in Florence. ; Publicado
The use of Massive Open Online Courses (MOOCs) is increasing worldwide and brings a revolution in education. The application of MOOCs has technological but also pedagogical implications. MOOCs are usually driven by short video lessons, automatic correction exercises, and the technological platforms can implement gamification or learning analytics techniques. However, much more analysis is required about the success or failure of these initiatives in order to know if this new MOOCs paradigm is appropriate for different learning situations. This work aims at analyzing and reporting whether the introduction of MOOCs technology was good or not in a case study with the Khan Academy platform at our university with students in a remedial Physics course in engineering education. Results show that students improved their grades significantly when using MOOCs technology, student satisfaction was high regarding the experience and for most of the different provided features, and there were good levels of interaction with the platform (e.g., number of completed videos or proficient exercises), and also the activity distribution for the different topics and types of activities was appropriate. ; This work has been supported by the "eMadrid" project (Regional Government of Madrid) under grant S2013/ICE-2715, the "RESET" project (Ministry of Economy and Competiveness) under grant TIN2014-53199-C3-1-R, the IRENE project (Ministry of Economy and Competiveness) under grant PT-2012-1036-370000 and the European Erasmus SHEILA project under grant 562080-EPP-1-2015-BE-EPPKA3-PI-FORWARD. ; Publicado
