W E L C O M E | learn more |
Research Center for Quantum Information
Institute of Physics, Slovak Academy of Sciences
Dúbravská cesta 9, 84511 Bratislava, Slovakia
Tel: (+421 +2) 20910701
Fax: (+421 +2) 5477-6085
| map |
N E W S | old news |
  24.03.2014 Research publication
Satisfiability-unsatisfiability transition in the adversarial satisfiability problem
Adversarial satisfiability (AdSAT) is a generalization of the satisfiability (SAT) problem in which two players try to make a Boolean formula true (resp. false) by controlling their respective sets of variables. AdSAT belongs to a higher complexity class in the polynomial hierarchy than SAT, and therefore the nature of the critical region and the transition are not easily parallel to those of SAT and worthy of independent study. AdSAT also provides an upper bound for the transition threshold of the quantum satisfiability problem (QSAT). We present a complete algorithm for AdSAT, show that 2-AdSAT is in P, and then study two stochastic algorithms (simulated annealing and its improved variant) and compare their performances in detail for 3-AdSAT. Varying the density of clauses α we claim that there is a sharp SAT-UNSAT transition at a critical value whose upper bound is αc≲1.5, suggesting a much stricter upper bound for the QSAT transition than those previously found.
by Marco Bardoscia, Daniel Nagaj, and Antonello Scardicchio
Phys. Rev. E 89, 032128 (2014) |+++|
COQI (APVV-0646-10)
  15.03.2014 Summer school
Qute-Europe Summer School 2014 (QESS 2014)
Starting your graduate in quantum information science and looking for right move for your PhD study? Come to our school on current challenges and elementary paradigms of quantum information processing. The school is organized from 18-28 August in charming Smolenice castle (Slovakia). To learn more details visit the school website http://quantum.physics.sk/conf/qess2014/. Support (provided by QUTE-EUROPE Coordination Action) is available and early deadline is 15/04/2014.
  21.02.2014 Conference
CEQIP 2014
This year in Znojmo (Czech republic), 4-8 June. Traditionally, excellent speakers, unforgettable athmosphere, delicious food and wine testing, unbreakable cipher game, adrenalyn underground experience, etc. Check more details on workshop website http://ceqip.eu/. Deadline for submission is April, 1st, seriously :-)
S E M I N A R S | more |
25/04 10:30
Michal Sedlák (Bratislava)
Hilbert's projective metric in quantum information theory

29/04 10:30*
Libor Caha (Bratislava)
tba

15/05 13:30
Lukáš Slodička (Bratislava)
tba
V I S I T O R S | history |
08.06-12.06 Daniel Burgarth
(Aberystwyth University, Aberystwyth, United Kingdom)

09.06-12.06* Marcus Cramer
(University of Ulm, Germany)

01.06-30.06* Erkka Haapasalo
(University of Turku, Finland)

01.06-30.06* Mikko Tukiainen
(University of Turku, Finland)

01.06-30.06* Teiko Heinosaari
(University of Turku, Finland)






Today is 23.04.2014, You are visitor number 5523