Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSolving NP-hard problems with bistable polaritonic networks
69
0
0.0
(
0
)
Added by
Oleksandr Kyriienko
Publication date
2018
fields
Physics
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
A lattice of locally bistable driven-dissipative cavity polaritons is found theoretically to effectively simulate the Ising model, also enabling an effective transverse field. We benchmark the system performance for spin glass problems, and study the scaling of the ground state energy deviation and success probability as a function of system size. As particular examples we consider NP-hard problems embedded in the Ising model, namely graph partitioning and the knapsack problem. We find that locally bistable polariton networks act as classical simulators for solving optimization problems, which can potentially present an improvement within the exponential complexity class.
rate research
Read More
Optimization is fundamental in many areas of science, from computer science and information theory to engineering and statistical physics, as well as to biology or social sciences. It typically involves a large number of variables and a cost function depending on these variables. Optimization problems in the NP-complete class are particularly difficult, it is believed that the number of operations required to minimize the cost function is in the most difficult cases exponential in the system size. However, even in an NP-complete problem the practically arising instances might, in fact, be easy to solve. The principal question we address in this thesis is: How to recognize if an NP-complete constraint satisfaction problem is typically hard and what are the main reasons for this? We adopt approaches from the statistical physics of disordered systems, in particular the cavity method developed originally to describe glassy systems. We describe new properties of the space of solutions in two of the most studied constraint satisfaction problems - random satisfiability and random graph coloring. We suggest a relation between the existence of the so-called frozen variables and the algorithmic hardness of a problem. Based on these insights, we introduce a new class of problems which we named locked constraint satisfaction, where the statistical description is easily solvable, but from the algorithmic point of view they are even more challenging than the canonical satisfiability.
Deep quantum neural networks may provide a promising way to achieve quantum learning advantage with noisy intermediate scale quantum devices. Here, we use deep quantum feedforward neural networks capable of universal quantum computation to represent the mixed states for open quantum many-body systems and introduce a variational method with quantum derivatives to solve the master equation for dynamics and stationary states. Owning to the special structure of the quantum networks, this approach enjoys a number of notable features, including the absence of barren plateaus, efficient quantum analogue of the backpropagation algorithm, resource-saving reuse of hidden qubits, general applicability independent of dimensionality and entanglement properties, as well as the convenient implementation of symmetries. As proof-of-principle demonstrations, we apply this approach to both one-dimensional transverse field Ising and two-dimensional $J_1-J_2$ models with dissipation, and show that it can efficiently capture their dynamics and stationary states with a desired accuracy.
We propose a method for solving statistical mechanics problems defined on sparse graphs. It extracts a small Feedback Vertex Set (FVS) from the sparse graph, converting the sparse system to a much smaller system with many-body and dense interactions with an effective energy on every configuration of the FVS, then learns a variational distribution parameterized using neural networks to approximate the original Boltzmann distribution. The method is able to estimate free energy, compute observables, and generate unbiased samples via direct sampling without auto-correlation. Extensive experiments show that our approach is more accurate than existing approaches for sparse spin glasses. On random graphs and real-world networks, our approach significantly outperforms the standard methods for sparse systems such as the belief-propagation algorithm; on structured sparse systems such as two-dimensional lattices our approach is significantly faster and more accurate than recently proposed variational autoregressive networks using convolution neural networks.
Systems with many stable configurations abound in nature, both in living and inanimate matter. Their inherent nonlinearity and sensitivity to small perturbations make them challenging to study, particularly in the presence of external driving, which can alter the relative stability of different attractors. Under such circumstances, one may ask whether any clear relationship holds between the specific pattern of external driving and the particular attractor states selected by a driven multistable system. To gain insight into this question, we numerically study driven disordered mechanical networks of bistable springs which possess a vast number of stable configurations arising from the two stable rest lengths of each spring, thereby capturing the essential physical properties of a broad class of multistable systems. We find that the attractor states of driven disordered multistable mechanical networks are fine-tuned with respect to the pattern of external forcing to have low work absorption from it. Furthermore, we find that these drive-specific attractor states are even more stable than expected for a given level of work absorption. Our results suggest that the driven exploration of the vast configuration space of these systems is biased towards states with exceptional relationship to the driving environment, and could therefore be used to `discover states with desired response properties in systems with a vast landscape of diverse configurations.
We study coherent backscattering of a quasi-monochromatic laser by a dilute gas of cold two-level atoms. We consider the perturbative regime of weak intensities, where nonlinear effects arise from {em inelastic} two-photon scattering processes. Here, coherent backscattering can be formed by interference between {em three} different scattering amplitudes. Consequently, if elastically scattered photons are filtered out from the photodetection signal by means of suitable frequency-selective detection, we find the nonlinear backscattering enhancement factor to exceed the linear barrier two.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
