Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userProbing for quantum speedup in spin glass problems with planted solutions
227
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
The availability of quantum annealing devices with hundreds of qubits has made the experimental demonstration of a quantum speedup for optimization problems a coveted, albeit elusive goal. Going beyond earlier studies of random Ising problems, here we introduce a method to construct a set of frustrated Ising-model optimization problems with tunable hardness. We study the performance of a D-Wave Two device (DW2) with up to 503 qubits on these problems and compare it to a suite of classical algorithms, including a highly optimized algorithm designed to compete directly with the DW2. The problems are generated around predetermined ground-state configurations, called planted solutions, which makes them particularly suitable for benchmarking purposes. The problem set exhibits properties familiar from constraint satisfaction (SAT) problems, such as a peak in the typical hardness of the problems, determined by a tunable clause density parameter. We bound the hardness regime where the DW2 device either does not or might exhibit a quantum speedup for our problem set. While we do not find evidence for a speedup for the hardest and most frustrated problems in our problem set, we cannot rule out that a speedup might exist for some of the easier, less frustrated problems. Our empirical findings pertain to the specific D-Wave processor and problem set we studied and leave open the possibility that future processors might exhibit a quantum speedup on the same problem set.
rate research
Read More
We investigate the computational hardness of spin-glass instances on a square lattice, generated via a recently introduced tunable and scalable approach for planting solutions. The method relies on partitioning the problem graph into edge-disjoint subgraphs, and planting frustrated, elementary subproblems that share a common local ground state, which guarantees that the ground state of the entire problem is known a priori. Using population annealing Monte Carlo, we compare the typical hardness of problem classes over a large region of the multi-dimensional tuning parameter space. Our results show that the problems have a wide range of tunable hardness. Moreover, we observe multiple transitions in the hardness phase space, which we further corroborate using simulated annealing and simulated quantum annealing. By investigating thermodynamic properties of these planted systems, we demonstrate that the harder samples undergo magnetic ordering transitions which are also ultimately responsible for the observed hardness transitions on changing the sample composition.
We present Chook, an open-source Python-based tool to generate discrete optimization problems of tunable complexity with a priori known solutions. Chook provides a cross-platform unified environment for solution planting using a number of techniques, such as tile planting, Wishart planting, equation planting, and deceptive cluster loop planting. Chook also incorporates planted solutions for higher-order (beyond quadratic) binary optimization problems. The support for various planting schemes and the tunable hardness allows the user to generate problems with a wide range of complexity on different graph topologies ranging from hypercubic lattices to fully-connected graphs.
One of the main milestones in quantum information science is to realise quantum devices that exhibit an exponential computational advantage over classical ones without being universal quantum computers, a state of affairs dubbed quantum speedup, or sometimes quantum computational supremacy. The known schemes heavily rely on mathematical assumptions that are plausible but unproven, prominently results on anticoncentration of random prescriptions. In this work, we aim at closing the gap by proving two anticoncentration theorems and accompanying hardness results, one for circuit-based schemes, the other for quantum quench-type schemes for quantum simulations. Compared to the few other known such results, these results give rise to a number of comparably simple, physically meaningful and resource-economical schemes showing a quantum speedup in one and two spatial dimensions. At the heart of the analysis are tools of unitary designs and random circuits that allow us to conclude that universal random circuits anticoncentrate as well as an embedding of known circuit-based schemes in a 2D translation-invariant architecture.
The spectral form factor (SFF), characterizing statistics of energy eigenvalues, is a key diagnostic of many-body quantum chaos. In addition, partial spectral form factors (pSFFs) can be defined which refer to subsystems of the many-body system. They provide unique insights into energy eigenstate statistics of many-body systems, as we show in an analysis on the basis of random matrix theory and of the eigenstate thermalization hypothesis. We propose a protocol which allows the measurement of SFF and pSFFs in quantum many-body spin models, within the framework of randomized measurements. Aimed to probe dynamical properties of quantum many-body systems, our scheme employs statistical correlations of local random operations which are applied at different times in a single experiment. Our protocol provides a unified testbed to probe many-body quantum chaotic behavior, thermalization and many-body localization in closed quantum systems which we illustrate with simulations for Hamiltonian and Floquet many-body spin-systems.
Spin glasses and many-body localization (MBL) are prime examples of ergodicity breaking, yet their physical origin is quite different: the former phase arises due to rugged classical energy landscape, while the latter is a quantum-interference effect. Here we study quantum dynamics of an isolated 1d spin-glass under application of a transverse field. At high energy densities, the system is ergodic, relaxing via resonance avalanche mechanism, that is also responsible for the destruction of MBL in non-glassy systems with power-law interactions. At low energy densities, the interaction-induced fields obtain a power-law soft gap, making the resonance avalanche mechanism inefficient. This leads to the persistence of the spin-glass order, as demonstrated by resonance analysis and by numerical studies. A small fraction of resonant spins forms a thermalizing system with long-range entanglement, making this regime distinct from the conventional MBL. The model considered can be realized in systems of trapped ions, opening the door to investigating slow quantum dynamics induced by glassiness.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
