Być może nawet gdy się równa, to może być nieopłacalne, gdy n będzie
równe np. milion, wtedy x^n będzie wolniejsze dla początkowych danych
niż 2^x.

Ale..

"
Toshiba stworzyła algorytm, który ma wyprzedzać komputery kwantowe
oshiba twierdzi, że udało im się stworzyć algorytm, który wyprzedza
komputery kwantowe przy wykorzystaniu standardowego hardware'u. Firma ma
zamiar skomercjalizować swoje rozwiązanie.

Przed rynkiem komputerowym stoi ogromne wyzwanie. Powoli zbliżamy się do
kresu możliwości tradycyjnego krzemu. Wkrótce (jest to prawdopodobnie
kwestia kilku lat) zwiększenie wydajność PC-tów będzie ogromnym
wyzwaniem. Tymczasem na świecie jest coraz więcej danych, które trzeba
przetwarzać i analizować. Komputery radzą sobie z tym coraz gorzej i
stąd duża wiara w komputery kwantowe, które miałyby rozwiązać wiele
dzisiejszych problemów. Tymczasem Toshiba twierdzi, że znalazła inny sposób.

Japońska firma od kilku lat miała pracować i doskonalić algorytm do
przetwarzania i analizowania dużych ilości danych. SBA (Simulated
Bifurcation Algorithm) w końcu jest gotowy i efekty są ponoć bardzo
zaskakujące. Zdaniem przedstawicieli Toshiby radzi on sobie lepiej niż
rozwiązania stosowane w najszybszych superkomputerach, a nawet
komputerach kwantowych. W trakcie demonstracji pokazano, jak algorytm
znajduje się rozwiązanie dla problemu z 2000 połączonych zmiennych w
zaledwie 50 mikrosekund. To mniej więcej 10 raczy szybciej niż oparte na
laserach komputery kwantowe.

Chociaż nad komputerami kwantowymi pracują największe firmy
technologiczne na świecie, to wciąż efekty nie zadowalają. Powstały już
co prawda pierwsze urządzenia, ale są one bardzo ograniczone i pod
względem wydajności daleko im do tego, co byłoby wymagane w praktyce.
Dlatego algorytm Toshiby może być pewnego rodzaju rewolucją. Czas
pokaże, co z tego wyjdzie.
"
https://gamingsociety.pl/artykul/toshiba-simulated-b
ifurcation-algorithm-1099121/

do góry

On Wednesday, January 22, 2020 at 2:00:02 AM UTC+1, Borneq wrote:
> Być może nawet gdy się równa, to może być nieopłacalne, gdy n będzie
> równe np. milion, wtedy x^n będzie wolniejsze dla początkowych danych
> niż 2^x.
>
> Ale..
>
> "
> Toshiba stworzyła algorytm, który ma wyprzedzać komputery kwantowe
> oshiba twierdzi, że udało im się stworzyć algorytm, który wyprzedza
> komputery kwantowe przy wykorzystaniu standardowego hardware'u. Firma ma
> zamiar skomercjalizować swoje rozwiązanie.
>
> Przed rynkiem komputerowym stoi ogromne wyzwanie. Powoli zbliżamy się do
> kresu możliwości tradycyjnego krzemu. Wkrótce (jest to prawdopodobnie
> kwestia kilku lat) zwiększenie wydajność PC-tów będzie ogromnym
> wyzwaniem. Tymczasem na świecie jest coraz więcej danych, które trzeba
> przetwarzać i analizować. Komputery radzą sobie z tym coraz gorzej i
> stąd duża wiara w komputery kwantowe, które miałyby rozwiązać wiele
> dzisiejszych problemów. Tymczasem Toshiba twierdzi, że znalazła inny sposób.
>
> Japońska firma od kilku lat miała pracować i doskonalić algorytm do
> przetwarzania i analizowania dużych ilości danych. SBA (Simulated
> Bifurcation Algorithm) w końcu jest gotowy i efekty są ponoć bardzo
> zaskakujące. Zdaniem przedstawicieli Toshiby radzi on sobie lepiej niż
> rozwiązania stosowane w najszybszych superkomputerach, a nawet
> komputerach kwantowych. W trakcie demonstracji pokazano, jak algorytm
> znajduje się rozwiązanie dla problemu z 2000 połączonych zmiennych w
> zaledwie 50 mikrosekund. To mniej więcej 10 raczy szybciej niż oparte na
> laserach komputery kwantowe.
>
> Chociaż nad komputerami kwantowymi pracują największe firmy
> technologiczne na świecie, to wciąż efekty nie zadowalają. Powstały już
> co prawda pierwsze urządzenia, ale są one bardzo ograniczone i pod
> względem wydajności daleko im do tego, co byłoby wymagane w praktyce.
> Dlatego algorytm Toshiby może być pewnego rodzaju rewolucją. Czas
> pokaże, co z tego wyjdzie.
> "
> https://gamingsociety.pl/artykul/toshiba-simulated-b
ifurcation-algorithm-1099121/

Tyle znalazłem na wiki:

https://pl.wikipedia.org/wiki/Bifurkacja_(matematyka
)

Gdzie można coś więcej doczytać na temat samej teorii?

Pozdrawiam

do góry

On 1/22/20 2:21 AM, M.M. wrote:
> Gdzie można coś więcej doczytać na temat samej teorii?

Fraktale i chaos, choćby książka którą kupiłem jeszcze na studiach:

Fraktale i chaos (ta mała książka) - Jacek Kudrewicz
Fraktale. Granice chaosu (Ta duża ksiażka)- H.-O.Peitgen, H.Jurgens,
D.Saupe (rok 1995)


Ciekawe, może teoria bifurkacji była by przydatna do utrzymywania plazmy
w Tokamaku? A ostatnio z Chin były wiadomości o sukcesach...

do góry

On Wednesday, January 22, 2020 at 2:00:02 AM UTC+1, Borneq wrote:
> Być może nawet gdy się równa, to może być nieopłacalne, gdy n będzie
> równe np. milion, wtedy x^n będzie wolniejsze dla początkowych danych
> niż 2^x.
>
> Ale..
>
> "
> Toshiba stworzyła algorytm, który ma wyprzedzać komputery kwantowe
> oshiba twierdzi, że udało im się stworzyć algorytm, który wyprzedza
> komputery kwantowe przy wykorzystaniu standardowego hardware'u. Firma ma
> zamiar skomercjalizować swoje rozwiązanie.
>
> Przed rynkiem komputerowym stoi ogromne wyzwanie. Powoli zbliżamy się do
> kresu możliwości tradycyjnego krzemu. Wkrótce (jest to prawdopodobnie
> kwestia kilku lat) zwiększenie wydajność PC-tów będzie ogromnym
> wyzwaniem. Tymczasem na świecie jest coraz więcej danych, które trzeba
> przetwarzać i analizować. Komputery radzą sobie z tym coraz gorzej i
> stąd duża wiara w komputery kwantowe, które miałyby rozwiązać wiele
> dzisiejszych problemów. Tymczasem Toshiba twierdzi, że znalazła inny sposób.
>
> Japońska firma od kilku lat miała pracować i doskonalić algorytm do
> przetwarzania i analizowania dużych ilości danych. SBA (Simulated
> Bifurcation Algorithm) w końcu jest gotowy i efekty są ponoć bardzo
> zaskakujące. Zdaniem przedstawicieli Toshiby radzi on sobie lepiej niż
> rozwiązania stosowane w najszybszych superkomputerach, a nawet
> komputerach kwantowych. W trakcie demonstracji pokazano, jak algorytm
> znajduje się rozwiązanie dla problemu z 2000 połączonych zmiennych w
> zaledwie 50 mikrosekund. To mniej więcej 10 raczy szybciej niż oparte na
> laserach komputery kwantowe.
>
> Chociaż nad komputerami kwantowymi pracują największe firmy
> technologiczne na świecie, to wciąż efekty nie zadowalają. Powstały już
> co prawda pierwsze urządzenia, ale są one bardzo ograniczone i pod
> względem wydajności daleko im do tego, co byłoby wymagane w praktyce.
> Dlatego algorytm Toshiby może być pewnego rodzaju rewolucją. Czas
> pokaże, co z tego wyjdzie.
> "
> https://gamingsociety.pl/artykul/toshiba-simulated-b
ifurcation-algorithm-1099121/

https://phys.org/news/2019-04-toshiba-breakthrough-a
lgorithm-world-fastest.html

"Toshiba has solved these issues by developing a novel combinatorial optimization
algorithm, the Simulated Bifurcation Algorithm. It is highly parallelizable, and can
therefore easily speed up problem solving on standard digital computer through
parallel computation. As current large-scale computational systems can be used as is,
there is no need to install new equipment, making it easy to scale up at a low cost."

w.

do góry

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...
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.

*) kantowy w sumie daje to samo:)


pzdr
bartekltg

do góry

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

do góry