Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userObstacles to quantum annealing in a planar embedding of XORSAT
48
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We introduce a planar embedding of the k-regular k-XORSAT problem, in which solutions are encoded in the ground state of a classical statistical mechanics model of reversible logic gates arranged on a square grid and acting on bits that represent the Boolean variables of the problem. The special feature of this embedding is that the resulting model lacks a finite-temperature phase transition, thus bypassing the first-order thermodynamic transition known to occur in the random graph representation of XORSAT. In spite of this attractive feature, the thermal relaxation into the ground state displays remarkably slow glassy behavior. The question addressed in this paper is whether this planar embedding can afford an efficient path to solution of k-regular k-XORSAT via quantum adiabatic annealing. We first show that our model bypasses an avoided level crossing and consequent exponentially small gap in the limit of small transverse fields. We then present quantum Monte Carlo results for our embedding of the k-regular k-XORSAT that strongly support a picture in which second-order and first-order transitions develop at a finite transverse field for k = 2 and k = 3, respectively. This translates into power-law and exponential dependences in the scaling of energy gaps with system size, corresponding to times-to-solution which are, respectively, polynomial and exponential in the number of variables. We conclude that neither classical nor quantum annealing can efficiently solve our reformulation of XORSAT, even though the original problem can be solved in polynomial time by Gaussian elimination.
rate research
Read More
Classical models with complex energy landscapes represent a perspective avenue for the near-term application of quantum simulators. Until now, many theoretical works studied the performance of quantum algorithms for models with a unique ground state. However, when the classical problem is in a so-called clustering phase, the ground state manifold is highly degenerate. As an example, we consider a 3-XORSAT model defined on simple hypergraphs. The degeneracy of classical ground state manifold translates into the emergence of an extensive number of $Z_2$ symmetries, which remain intact even in the presence of a quantum transverse magnetic field. We establish a general duality approach that restricts the quantum problem to a given sector of conserved $Z_2$ charges and use it to study how the outcome of the quantum adiabatic algorithm depends on the hypergraph geometry. We show that the tree hypergraph which corresponds to a classically solvable instance of the 3-XORSAT problem features a constant gap, whereas the closed hypergraph encounters a second-order phase transition with a gap vanishing as a power-law in the problem size. The duality developed in this work provides a practical tool for studies of quantum models with classically degenerate energy manifold and reveals potential connections between glasses and gauge theories.
We show how classical and quantum dualities, as well as duality relations that appear only in a sector of certain theories (emergent dualities), can be unveiled, and systematically established. Our method relies on the use of morphisms of the bond algebra of a quantum Hamiltonian. Dualities are characterized as unitary mappings implementing such morphisms, whose even powers become symmetries of the quantum problem. Dual variables -which were guessed in the past- can be derived in our formalism. We obtain new self-dualities for four-dimensional Abelian gauge field theories.
In order to treat all-to-all connected quadratic binary optimization problems (QUBO) with hardware quantum annealers, an embedding of the original problem is required due to the sparsity of the hardwares topology. Embedding fully-connected graphs -- typically found in industrial applications -- incurs a quadratic space overhead and thus a significant overhead in the time to solution. Here we investigate this embedding penalty of established planar embedding schemes such as minor embedding on a square lattice, minor embedding on a Chimera graph, and the Lechner-Hauke-Zoller scheme using simulated quantum annealing on classical hardware. Large-scale quantum Monte Carlo simulation suggest a polynomial time-to-solution overhead. Our results demonstrate that standard analog quantum annealing hardware is at a disadvantage in comparison to classical digital annealers, as well as gate-model quantum annealers and could also serve as benchmark for improvements of the standard quantum annealing protocol.
We study quantum transport after an inhomogeneous quantum quench in a free fermion lattice system in the presence of a localised defect. Using a new rigorous analytical approach for the calculation of large time and distance asymptotics of physical observables, we derive the exact profiles of particle density and current. Our analysis shows that the predictions of a semiclassical approach that has been extensively applied in similar problems match exactly with the correct asymptotics, except for possible finite distance corrections close to the defect. We generalise our formulas to an arbitrary non-interacting particle-conserving defect, expressing them in terms of its scattering properties.
We study the mechanism of decay of a topological (winding-number) excitation due to finite-size effects in a two-dimensional valence-bond solid state, realized in an $S=1/2$ spin model ($J$-$Q$ model) and studied using projector Monte Carlo simulations in the valence bond basis. A topological excitation with winding number $|W|>0$ contains domain walls, which are unstable due to the emergence of long valence bonds in the wave function, unlike in effective descriptions with the quantum dimer model. We find that the life time of the winding number in imaginary time diverges as a power of the system length $L$. The energy can be computed within this time (i.e., it converges toward a quasi-eigenvalue before the winding number decays) and agrees for large $L$ with the domain-wall energy computed in an open lattice with boundary modifications enforcing a domain wall. Constructing a simplified two-state model and using the imaginary-time behavior from the simulations as input, we find that the real-time decay rate out of the initial winding sector is exponentially small in $L$. Thus, the winding number rapidly becomes a well-defined conserved quantum number for large systems, supporting the conclusions reached by computing the energy quasi-eigenvalues. Including Heisenberg exchange interactions which brings the system to a quantum-critical point separating the valence-bond solid from an antiferromagnetic ground state (the putative deconfined quantum-critical point), we can also converge the domain wall energy here and find that it decays as a power-law of the system size. Thus, the winding number is an emergent quantum number also at the critical point, with all winding number sectors becoming degenerate in the thermodynamic limit. This supports the description of the critical point in terms of a U(1) gauge-field theory.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
