On Wednesday, January 22, 2020 at 6:02:12 PM UTC+1, bartekltg wrote:
> On Wednesday, January 22, 2020 at 2:00:02 AM UTC+1, Borneq wrote:
>
> > Ale..
>
> Żade ale. To nie ma nic wsplnego z N ?= NP.
> To algorytm probabilistyczny, przybliżony, aproksymacyjny...

Chyba że w innym sensie niż klasycznym... Ale nie piszą też nic o tym, że
ich algorytm jest aproksymacyjny.

[
These problemsare NOTORIOUSLY DIFFICULT because of combinatorial explosion (1,2).
Thus,special-purpose hardware devices for these problems are expected to beuseful. In
particular, "Ising machines"designed for finding a groundstate of the Ising spin
model (3) have recently attracted much attentionbecause many combinatorial
optimization problems CAN BE MAPPED tothe Ising problem (4), including
very-large-scale integrated circuit de-sign (5), drug design (6), and financial
portfolio management (7). Thesemachines have been developed by various approaches:
quantum com-puters based on quantum annealing (8,9) or quantum adiabatic
opti-mization (10-12) implemented with superconducting circuits (13,14),coherent
Ising machines (CIMs) implemented with laser pulses (15-20),and Ising machines based
on simulated annealing (SA) (1,21,22)im-plemented with digital circuits such as
field-programmable gate arrays(FPGAs) (23-29).
]


[
In this challenge, intense research efforts are underway to pave alternative
approaches for computing and information processing. Among them, Ising machines have
been shown to offer viable solutions for important NP-hard problems such as MAX-CUT 6
, protein folding 7 , and traveling salesman 8 , among others
[9][10][11][12][13][14][15] . To this end, a variety of Ising machines have been
demonstrated in effective spin systems of trapped atoms 16,17 , polariton condensates
18 , superconducting circuits 19 , coupled oscillators [20][21][22] , nanophotonic
waveguides [23][24][25] , randomly coupled lasers [26][27][28] , and time-multiplexed
optical parametric oscillators 29,30
]

Klasycznie/asymptotycznie też nie wierzę żeby NP=P na dowolnym rozmiarze, w
łatwiej postawione wyzwania też nie dowierzam. Ale można szukać bardzo
szybkich i w miarę dokładnych algorytmów dla problemów o ograniczonym rozmiarze.

Tu też ciekawszy cytat:
[
Solving an all-to-all connected 2000-node MAX-CUTproblem by a single-FPGA SB
machineFrom the advantages and properties of SB, we expect that SB will beuseful for
approximately solving large-scale Ising or MAX-CUT prob-lems with dense connectivity
as fast as possible. To check this expec-tation, we compare our SB machine with a
state-of-the-art CIM (17,19),because this machine has achieved outstanding
performance for theseproblems. For this comparison, we solved an all-to-all connected
2000-node MAX-CUT problem named K2000,whichwassolvedbytheCIM(17,19).We implemented an
SB-based 2000-spin Ising machine with a singleFPGA. The product-sum operation, ?Nj
1/4 1Ji;jxj, in Eq. 8, which is the mostcomputation-intensive part in SB, is
performed efficiently by massivelyparallel processing. Ji,jxjterms of up to 8192 are
processed at a singleclock, which is about four times more than the total spins. See
the Sup-plementary Materials for details.One of the main results in (17) is that the
CIM reached a targetenergy given by the Goemans-Williamson semidefinite
programming(GW-SDP) algorithm (17,38) in about 70 ms in the best case among100
trials, which is about 50 times shorter than that by the SA highlytuned in (17). [The
SA in (17,19) is very fast by putting all the elementsof the coupling matrix Jon a
cache of a single core. Thus, parallel com-puting with multiple cores cannot
accelerate the SA because of commu-nication overheads.] In comparison with this, our
single-FPGA SBmachine reaches the GW-SDP value in only 58 ms even in the worst
caseamong 100 trials, as shown in Fig. 2A.Anothermainresultin(17) is that the CIM
took only 5 ms to obtainas good solutions (large cut values) as the highly tuned SA
obtained in50 ms, where the cut value of the MAX-CUT problem is given
by?EIsing2?14?Ni 1/4 1?Nj 1/4 1Ji;jwith Ising parameters (see the
SupplementaryMaterials). Figure 2B shows that our SB machine takes only 0.5 ms to
obtain better solutions on average than both the CIM in 5 ms and theSA in 50 ms.
]



> Komiwojadzera też mozęsz rozwiązać w czasie liniowym, tylko niedokładnie.
> pytanie czy P=NP dotyczy znajdowania ścisłego, optymalnego rozwiązania.
> Ale dla wielu rzeczywistych przpadków takie przybliżone
> rozwiązanie jest wystarczająco dobre.
>
> I tu zaproponowali takie przylizone rozwiązanie*) dla jakeigoś
> problemu kombinarytorycznego, coś z modelem Isinga.
>
> https://www.researchgate.net/publication/332535366_C
ombinatorial_optimization_by_simulating_adiabatic_bi
furcations_in_nonlinear_Hamiltonian_systems
>
> Porównują się do symulowanego wyzarzania i jakeigoś algorytmu
> zaprojektowanego pos isinga.

Na to wygląda.


> *) kantowy w sumie daje to samo:)


Podali za dużo literatury pomocniczej jak na rozrywkę przy śniadaniu ;-)


Pozdrawiam