More Like this

1. Parallel Repetition via Fortification: Analytic View and The Quantum Case

   Bavarian, Mohammad; Vidick, Thomas; Yuen, Henry (January 2017, Innovations in Theoretical Computer Science)

   In a recent work, Moshkovitz [FOCS '14] presented a transformation on two-player games called ``fortification'', and gave an elementary proof of an (exponential decay) parallel repetition theorem for fortified two-player projection games. In this paper, we give an \emph{analytic reformulation} of Moshkovitz's fortification framework, which was originally cast in combinatorial terms. This reformulation allows us to expand the scope of the fortification method to new settings. First, we show \emph{any} game (not just projection games) can be fortified, and give a simple proof of parallel repetition for general fortified games. Then, we prove parallel repetition and fortification theorems for games with players sharing quantum entanglement, as well as games with more than two players. This gives a new gap amplification method for general games in the quantum and multiplayer settings, two problems which have recently received much attention. An important component of our work is a variant of the fortification transformation, called ``ordered fortification", that preserves the entangled value of a game. The original fortification of Moshkovitz does not in general preserve the entangled value of a game, and this was a barrier to extending the fortification framework to the quantum setting. 

   more » « less
2. Hardness amplification for entangled games via anchoring

   https://doi.org/10.1145/3055399.3055433  

   Bavarian, Mohammad; Vidick, Thomas; Yuen, Henry (June 2017, Proceedings of the annual ACM Symposium on Theory of Computing)

   We study the parallel repetition of one-round games involving players that can use quantum entanglement. A major open question in this area is whether parallel repetition reduces the entangled value of a game at an exponential rate --- in other words, does an analogue of Raz's parallel repetition theorem hold for games with players sharing quantum entanglement? Previous results only apply to special classes of games. We introduce a class of games we call anchored. We then introduce a simple transformation on games called \emph{anchoring}, inspired in part by the Feige-Kilian transformation, that turns \emph{any} (multiplayer) game into an anchored game. Unlike the Feige-Kilian transformation, our anchoring transformation is completeness preserving. We prove an exponential-decay parallel repetition theorem for anchored games that involve any number of entangled players. We also prove a threshold version of our parallel repetition theorem for anchored games. Together, our parallel repetition theorems and anchoring transformation provide the first hardness amplification techniques for general entangled games. We give an application to the games version of the Quantum PCP Conjecture. 

   more » « less
3. Photo-activated polymerization inhibition process in photoinitiator systems for high-throughput 3D nanoprinting

   https://doi.org/10.1515/nanoph-2022-0611  

   Somers, Paul; Liang, Zihao; Chi, Teng; Johnson, Jason E.; Pan, Liang; Boudouris, Bryan W.; Xu, Xianfan (February 2023, Nanophotonics)

   Abstract The systems for multiphoton 3D nanoprinting are rapidly increasing in print speed for larger throughput and scale, unfortunately without also improvement in resolution. Separately, the process of photoinhibition lithography has been demonstrated to enhance the resolution of multiphoton printing through the introduction of a secondary laser source. The photo-chemical dynamics and interactions for achieving photoinhibition in the various multiphoton photoinitiator systems are complex and still not well understood. Here, we examine the photoinhibition process of the common photoinitiator 7-diethylamino 3-thenoylcoumarin (DETC) with inhibition lasers near or at the multiphoton printing laser wavelength in typical low peak intensity, high repetition rate 3D nanoprinting processes. We demonstrate the clear inhibition of the polymerization process consistent with a triplet absorption deactivation mechanism for a DETC photoresist as well as show inhibition for several other photoresist systems. Additionally, we explore options to recover the photoinhibition process when printing with high intensity, low repetition rate lasers. Finally, we demonstrate photoinhibition in a projection multiphoton printing system. This investigation of photoinhibition lithography with common photoinitiators elucidates the possibility for photoinhibition occurring in many resist systems with typical high repetition rate multiphoton printing lasers as well as for high-speed projection multiphoton printing. 

   more » « less
4. The parallel-transported (quasi)-diabatic basis

   https://doi.org/10.1063/5.0122781  

   Littlejohn, Robert; Rawlinson, Jonathan; Subotnik, Joseph (November 2022, The Journal of Chemical Physics)

   This article concerns the use of parallel transport to create a diabatic basis. The advantages of the parallel-transported basis include the facility with which Taylor series expansions can be carried out in the neighborhood of a point or a manifold such as a seam (the locus of degeneracies of the electronic Hamiltonian), and the close relationship between the derivative couplings and the curvature in this basis. These are important for analytic treatments of the nuclear Schrödinger equation in the neighborhood of degeneracies. The parallel-transported basis bears a close relationship to the singular-value basis; in this article, both are expanded in power series about a reference point and are shown to agree through second order but not beyond. Taylor series expansions are effected through the projection operator, whose expansion does not involve energy denominators or any type of singularity and in terms of which both the singular-value basis and the parallel-transported basis can be expressed. The parallel-transported basis is a version of Poincaré gauge, well known in electromagnetism, which provides a relationship between the derivative couplings and the curvature and which, along with a formula due to Mead, affords an efficient method for calculating Taylor series of the basis states and the derivative couplings. The case in which fine structure effects are included in the electronic Hamiltonian is covered. 

   more » « less
5. Model-Free Reinforcement Learning for Stochastic Parity Games

   Hahn, Ernst Moritz; Perez, Mateo; Schewe, Sven; Somenzi, Fabio; Trivedi, Ashutosh; Wojtczak, Dominik (August 2020, 31st International Conference on Concurrency Theory (CONCUR 2020))

   null (Ed.)

   This paper investigates the use of model-free reinforcement learning to compute the optimal value in two-player stochastic games with parity objectives. In this setting, two decision makers, player Min and player Max, compete on a finite game arena - a stochastic game graph with unknown but fixed probability distributions - to minimize and maximize, respectively, the probability of satisfying a parity objective. We give a reduction from stochastic parity games to a family of stochastic reachability games with a parameter ε, such that the value of a stochastic parity game equals the limit of the values of the corresponding simple stochastic games as the parameter ε tends to 0. Since this reduction does not require the knowledge of the probabilistic transition structure of the underlying game arena, model-free reinforcement learning algorithms, such as minimax Q-learning, can be used to approximate the value and mutual best-response strategies for both players in the underlying stochastic parity game. We also present a streamlined reduction from 1 1/2-player parity games to reachability games that avoids recourse to nondeterminism. Finally, we report on the experimental evaluations of both reductions 

   more » « less