Format results
Quantum many-time physics: noise, complexity, and windows to new phenomena
Gregory White University of Melbourne
Market Power and Tax Interventions: A Principal Components Approach
Ben Golub (Northwestern)Interpretable Quantum Advantage in Neural Sequence Learning
Eric Anschuetz Massachusetts Institute of Technology (MIT)
Quantum Constraint Problems can be complete for BQP, QCMA, and BPP
Alexander Meiburg University of California System
First-Passage Processes in Physics and Beyond
Sidney Redner Santa Fe Institute
Quantum-enhanced telescopy
Yunkai Wang Perimeter Institute for Theoretical Physics
Persuasion in Networks: Public Signals and Cores
Ozan Candogan (U Chicago)We consider a setting where agents in a social network take binary actions that exhibit local strategic complementarities. Their payoffs are affine and increasing in an underlying real-valued state of the world. An information designer commits to a signaling mechanism that publicly reveals a signal that is potentially informative about the state. She wants to maximize the expected number of agents who take action 1. We study the structure and design of optimal public signaling mechanisms. The designer’s payoff is an increasing step function of the posterior mean (of the state) induced by the realization of her signal. We provide a convex optimization formulation and an algorithm that obtain an optimal public signaling mechanism whenever the designer’s payoff admits this structure. This structure is prevalent, making our formulation and results useful well beyond persuasion in networks. In our problem, the step function is characterized in terms of the cores of the underlying network. The optimal mechanism is based on a “double-interval partition†of the set of states: it associates up to two subintervals of the set of states with each core, and when the state realization belongs to the interval(s) associated with a core, the mechanism publicly reveals this fact. In turn, this induces the agents in the relevant core to take action 1. We also provide a framework for obtaining asymptotically optimal public signaling mechanisms for a class of random networks. Our approach uses only the limiting degree distribution information, thereby making it useful even when the network structure is not fully known. Finally, we explore which networks are more amenable to persuasion, and show that more assortative connection structures lead to larger payoffs for the designer. On the other hand, the dependence of the designer’s payoff on the agents’ degrees can be quite counterintuitive. In particular, we focus on networks sampled uniformly at random from the set of all networks consistent with a degree sequence, and illustrate that when the degrees of some nodes increase, this can reduce the designer’s expected payoff, despite an increase in the extent of (positive) network externalities.Quantum many-time physics: noise, complexity, and windows to new phenomena
Gregory White University of Melbourne
Quantum theory has a temporal composition, which is expressed under many different operational frameworks. Here, points in time are imbued with a Hilbert space structure, and quantum states are passed between times through a series of experimental interventions. A multi-time quantum process, therefore, carries the same complex properties as a many-body quantum state. This invites the question: to what extent can temporal correlations be as interesting as spatial ones, and how can we access them? One particular avenue through which this structure manifests is in open quantum systems. System-environment dynamics can precipitate non-Markovian processes by which correlations persist between different times. Recently, the advent of high-fidelity quantum devices has made it possible to probe coherent quantum systems. In this talk, I will discuss my recent work in which we show how this serves as a novel test bed to capture many-time physics. We build frameworks to extract generic spatiotemporal properties of quantum stochastic processes, show how process complexity may be manipulated, and elevate user-control into the theory to make it self-consistent. Remarkably, many of these complex features are already present in naturally occurring noise, and hence the results have direct application to the development of fault-tolerant quantum devices. I will also briefly discuss some of my future research goals: the existence of exotic temporal phenomena and how emergent spatiotemporal features can be captured through renormalisation group approaches; the learnability of spacetime quantum correlations and avenues here to quantum advantage; and the taming of correlated noise in quantum devices through bespoke error suppression and error correction.
Market Power and Tax Interventions: A Principal Components Approach
Ben Golub (Northwestern)Suppliers of differentiated goods make simultaneous pricing decisions, which are strategically linked because the goods are substitutes or complements in consumption. We study how changes in producers' costs pass through to two key outcomes: prices and welfare. We consider the positive question of which cost changes (e.g., shocks to commodity prices) are most amplified by strategic behavior. We also investigate the policy question of which marginal taxes and subsidies are best for welfare. A key tool is a certain basis for the goods space, determined by the network of interactions among suppliers. It consists of principal components in the goods space, independent in the sense that a cost change incident on any component passes through to the price only of that component. Pass-through coefficients are determined by associated eigenvalues of a demand matrix and yield an ordering of principal components. The ordered basis permits a simple cutoff characterization of optimal tax-and-subsidy interventions, which subsidizes principal components, with high pass-through, and taxes ones with low pass-through. The gain in welfare achievable by an optimal tax scheme is increasing in a suitable measure of eigenvalue dispersion. The results permit us to leverage the theory of spectral approximation to design optimal interventions even when the demand system is observed with a lot of noise.Interpretable Quantum Advantage in Neural Sequence Learning
Eric Anschuetz Massachusetts Institute of Technology (MIT)
Quantum neural networks have been widely studied in recent years, given their potential practical utility and recent results regarding their ability to efficiently express certain classical data. However, analytic results to date rely on assumptions and arguments from complexity theory. Due to this, there is little intuition as to the source of the expressive power of quantum neural networks or for which classes of classical data any advantage can be reasonably expected to hold. In this talk, I will discuss my recent results (arXiv:2209.14353) studying the relative expressive power between a broad class of neural network sequence models and a class of recurrent models based on Gaussian operations with non-Gaussian measurements. We explicitly show that quantum contextuality is the source of an unconditional memory separation in the expressivity of the two model classes. Additionally, we use this intuition to study the relative performance of our introduced model on a standard translation data set exhibiting linguistic contextuality and show that the quantum model outperforms state-of-the-art classical models even in practice. I will also briefly discuss connections to my previous work studying the trainability of variational quantum algorithms (arXiv:2109.06957, arXiv:2205.05786).
Quantum Constraint Problems can be complete for BQP, QCMA, and BPP
Alexander Meiburg University of California System
Constraint satisfaction problems are known to always be "easy" or "hard", in the sense of being either solvable in P or being NP-complete, with no intermediate difficulty levels. The quantum analog of constraint problems, frustration-free Hamiltonians, are known to exhibit at least two more levels of complexity: QMA (for arbitrary local Hamiltonians) and MA (for stoquastic Hamiltonians). Wondering if other complexity classes can occur, we answer in the affirmative: there are interactions which can be freely arranged on qubits in any arrangement, such that the resulting frustration problem is BQP-complete, and captures exactly the difficulty of quantum computation. Simple modifications of this construction show that quantum constraint problems can be complete for QCMA and BPP as well. Based on https://arxiv.org/abs/2101.08381
TBD
Dean Eckles (MIT) *Presenting VirtuallyInstructions to join the fully virtual workshop session in the academic metaverse: https://immorlica.com/workshop.htm **Recording Notice** Once you enter Gathertown, you consent to being recorded. If do you do not wish to be recorded, you can: Make yourself anonymous Not enter the Gathertown spaceGeometric contribution to entanglement entropy and multipartite entanglement in two-dimensional chiral topological liquid
Yuhan Liu University of Chicago
The multipartite entanglement structure for the ground states of two dimensional topological phases is an interesting albeit not well understood question. Utilizing the bulk-boundary correspondence, the tripartite entanglement calculation of 2d topological phases can be reduced to that on the vertex state, defined by the boundary conditions at the interfaces between spatial regions. In this work, we use the conformal interface technique to calculate the entanglement measures of the vertex state, which include the area-law, geometrical and topological pieces, and the possible extra order one contribution. This explains our previous observation of Markov gap h=\frac{c}{3}\ln 2 in the 3-vertex state, and generalizes it to the p-vertex state as well as rational conformal field theory, and more general choices of subsystem. Finally, we support our prediction by numerical evidence.
Zoom link: https://pitp.zoom.us/j/93914854044?pwd=eWl3eGVLU25XUGhKbnFRSm5ab0JuUT09
First-Passage Processes in Physics and Beyond
Sidney Redner Santa Fe Institute
A fundamental aspect of a random walk is determining when it reaches a specified threshold position for the first time. This first-passage time, and more generally, the distribution of first passage times underlies many non-equilibrium phenomena, such as the triggering of integrate and fire neurons, the statistics of cell division, and the execution of stock options. The computation of the first-passage time and its distribution is both simple and beautiful, with profound connections to electrostatic potential theory. I will present some aspects of these fundamentals and then discuss applications of first-passage ideas to diverse phenomena, including stochastic search processes and a toy model of wealth sharing.
Zoom link: https://pitp.zoom.us/j/98293478936?pwd=NTR3dWZoNElWRmd2NVJ1bzk5aC9ZQT09
Quantum-enhanced telescopy
Yunkai Wang Perimeter Institute for Theoretical Physics
Optical astronomical imaging looks for better imaging quality in extreme cases of weak and subdiffraction limits. I focus on the quantum enhancement of astronomical interferometric imaging, including its fundamental limit and practical issues. For the fundamental aspects, I ignore any resource limit and noise and consider the ideal imaging problems. I show that the resolution limit can be enhanced with more carefully chosen measurement strategies and the general imaging quality can be enhanced by postprocessing the stellar photons with a quantum computer. For the practical aspects, I try to overcome the transmission loss suffered by interferometric imaging using quantum network, consider the possibility to implement a local scheme with better performance, and discuss the feasibility of decomposing thermal states into temporally localized pulses.
Games on Endogenous Networks
Evan Sadler (Columbia) *Presenting VirtuallyInstructions to join the fully virtual workshop session in the academic metaverse: https://immorlica.com/workshop.htm **Recording Notice** Once you enter Gathertown, you consent to being recorded. If do you do not wish to be recorded, you can: Make yourself anonymous Not enter the Gathertown space Abstract We study network games in which players choose both the partners with whom they associate and an action level (e.g., effort) that creates spillovers for those partners. We introduce a framework and two solution concepts, extending standard approaches for analyzing each choice in isolation: Nash equilibrium in actions and pairwise stability in links. Our main results show that, under suitable order conditions on incentives, stable networks take simple forms. The first condition concerns whether links create positive or negative payoff spillovers. The second concerns whether actions are strategic complements to links, or strategic substitutes. Together, these conditions yield a taxonomy of the relationship between network structure and economic primitives organized around two network architectures: ordered overlapping cliques and nested split graphs. We apply our model to understand the consequences of competition for status, to microfound matching models that assume clique formation, and to interpret empirical findings that highlight unintended consequences of group design.Learning efficient decoders for quasi-chaotic quantum scramblers
Scrambling of quantum information is an important feature at the root of randomization and benchmarking protocols, the onset of quantum chaos, and black-hole physics.
Unscrambling this information is possible given perfect knowledge of the scrambler [ArXiv: 1710.03363].
We show that one can retrieve the scrambled information without any previous knowledge of the scrambler, by a learning algorithm that allows the building of an efficient decoder. Surprisingly, complex quantum scramblers admit Clifford decoders: the salient properties of a scrambling unitary can be efficiently described even if exponentially complex, as long as it is not fully chaotic. This is possible because all the redundant complexity can be described as an entropy, and for non-chaotic black holes can be efficiently pushed away, just like in a refrigerator. This entropy is not due to thermal fluctuations but to the non-stabilizer behavior of the scrambler.