In this work, we design a novel game-theoretical framework capable of capturing the defining aspects of quantum theory. We introduce an original model and an algorithmic procedure that enables to express measurement scenarios encountered in quantum mechanics as multiplayer games and to translate physical notions of causality, correlation, and contextuality to particular aspects of game theory. Furthermore, inspired by the established correspondence, we investigate the causal consistency of games in extensive form with imperfect information from the quantum perspective and we conclude that counterfactual dependencies should be distinguished from causation and correlation as a separate phenomenon of its own. Most significantly, we deduce that Nashian free choice game theory is non-contextual and hence is in contradiction with the Kochen-Specker theorem. Hence, we propose that quantum physics should be analysed with toolkits from non-Nashian game theory applied to our suggested model.
The community of scientists is characterized by their need to publish in peer-reviewed journals, in an attempt to avoid the "perish" side of the famous maxim. Accordingly, almost all researchers authored some scientific articles. Scholarly publications represent at least two benefits for the study of the scientific community as a social group. First, they attest of some form of relation between scientists (collaborations, mentoring, heritage,...), useful to determine and analyze social subgroups. Second, most of them are recorded in large data bases, easily accessible and including a lot of pertinent information, easing the quantitative and qualitative study of the scientific community. Understanding the underlying dynamics driving the creation of knowledge in general, and of scientific publication in particular, in addition to its interest from the social science point of view, can contribute to maintaining a high level of research, by identifying good and bad practices in science. In this manuscript, we aim at advancing this understanding by a statistical analysis of publications within peer-reviewed journals. Namely, we show that the distribution of the number of articles published by an author in a given journal is heavy-tailed, but has lighter tail than a power law. Interestingly, we demonstrate (both analytically and numerically) that such distributions are the result of an modified preferential attachment process.
In this paper we introduce classically time-controlled quantum automata or CTQA, which is a reasonable modification of Moore-Crutchfield quantum finite automata that uses time-dependent evolution and a "scheduler" defining how long each Hamiltonian will run. Surprisingly enough, time-dependent evolution provides a significant change in the computational power of quantum automata with respect to a discrete quantum model. Indeed, we show that if a scheduler is not computationally restricted, then a CTQA can decide the Halting problem. In order to unearth the computational capabilities of CTQAs we study the case of a computationally restricted scheduler. In particular we showed that depending on the type of restriction imposed on the scheduler, a CTQA can (i) recognize non-regular languages with cut-point, even in the presence of Karp-Lipton advice, and (ii) recognize non-regular promise languages with bounded-error. Furthermore, we study the cutpoint-union of cutpoint languages by introducing a new model of Moore-Crutchfield quantum finite automata with a rotating tape head. CTQA presents itself as a new model of computation that provides a different approach to a formal study of "classical control, quantum data" schemes in quantum computing.
In this paper we focus on modules over a finite chain ring $\mathcal{R}$ of size $q^s$. We compute the density of free modules of $\mathcal{R}^n$, where we separately treat the asymptotics in $n,q$ and $s$. In particular, we focus on two cases: one where we fix the length of the module and one where we fix the rank of the module. In both cases, the density results can be bounded by the Andrews-Gordon identities. We also study the asymptotic behaviour of modules generated by random matrices over $\mathcal{R}$. Since linear codes over $\mathcal{R}$ are submodules of $\mathcal{R}^n$ we get direct implications for coding theory. For example, we show that random codes achieve the Gilbert-Varshamov bound with high probability.
We extend a previous framework for designing differentially private (DP) mechanisms via randomized graph colorings that was restricted to binary functions, corresponding to colorings in a graph, to multi-valued functions. As before, datasets are nodes in the graph and any two neighboring datasets are connected by an edge. In our setting, we assume each dataset has a preferential ordering for the possible outputs of the mechanism, which we refer to as a rainbow. Different rainbows partition the graph of datasets into different regions. We show that when the DP mechanism is pre-specified at the boundary of such regions, at most one optimal mechanism can exist. Moreover, if the mechanism is to behave identically for all same-rainbow boundary datasets, the problem can be greatly simplified and solved by means of a morphism to a line graph. We then show closed form expressions for the line graph in the case of ternary functions. Treatment of ternary queries in this paper displays enough richness to be extended to higher-dimensional query spaces with preferential query ordering, but the optimality proof does not seem to follow directly from the ternary proof.
Predatory trading bots lurking in Ethereum's mempool present invisible taxation of traders on automated market makers (AMMs). AMM traders specify a slippage tolerance to indicate the maximum price movement they are willing to accept. This way, traders avoid automatic transaction failure in case of small price movements before their trade request executes. However, while a too-small slippage tolerance may lead to trade failures, a too-large tolerance allows predatory trading bots to profit from sandwich attacks. These bots can extract the difference between the slippage tolerance and the actual price movement as profit. In this work, we introduce the sandwich game to analyze sandwich attacks analytically from both the attacker and victim perspectives. Moreover, we provide a simple and highly effective algorithm that traders can use to set the slippage. We unveil that the vast majority of broadcast transactions can avoid sandwich attacks while simultaneously only experiencing a low risk of transaction failure. Thereby, we demonstrate that a constant auto-slippage cannot adjust to varying trade sizes and pool characteristics. Our algorithm outperforms the constant auto-slippage suggested by the biggest AMM, Uniswap, in all performed tests. Specifically, our algorithm repeatedly demonstrates a cost reduction exceeding a factor of 100.
Most stock markets are open for 6-8 hours per trading day. The Asian, European and North American stock markets are separated in time by time-zone differences. We propose a statistical factor model for daily returns across multiple time zones. Our model has a common global factor as well as a continent factor. We demonstrate that our model has a structural interpretation. We propose estimation routines by both the Frequentist (the Expectation-Maximisation (EM) algorithm) and Bayesian (the Markov Chain Monte Carlo (MCMC)) methods. Monte Carlo simulations are conducted to assess the validity of our estimation routines. Last, we apply our model to daily portfolio returns from Japan, UK and US.
Solving analytically intractable partial differential equations (PDEs) that involve at least one variable defined in an unbounded domain requires efficient numerical methods that accurately resolve the dependence of the PDE on that variable over several orders of magnitude. Unbounded domain problems arise in various application areas and solving such problems is important for understanding multi-scale biological dynamics, resolving physical processes at long time scales and distances, and performing parameter inference in engineering problems. In this work, we combine two classes of numerical methods: (i) physics-informed neural networks (PINNs) and (ii) adaptive spectral methods. The numerical methods that we develop take advantage of the ability of physics-informed neural networks to easily implement high-order numerical schemes to efficiently solve PDEs. We then show how recently introduced adaptive techniques for spectral methods can be integrated into PINN-based PDE solvers to obtain numerical solutions of unbounded domain problems that cannot be efficiently approximated by standard PINNs. Through a number of examples, we demonstrate the advantages of the proposed spectrally adapted PINNs (s-PINNs) over standard PINNs in approximating functions, solving PDEs, and estimating model parameters from noisy observations in unbounded domains.
Can quantum entanglement increase the capacity of (classical) covert channels? To one familiar with Holevo's Theorem it is tempting to think that the answer is obviously no. However, in this work we show: quantum entanglement can in fact increase the capacity of a classical covert channel, in the presence of an active adversary; on the other hand, a zero-capacity channel is not improved by entanglement, so entanglement cannot create `purely quantum' covert channels; the problem of determining the capacity of a given channel in the presence of entanglement is undecidable; but there is an algorithm to bound the entangled capacity of a channel from above, adapted from the semi-definite hierarchy from the theory of non-local games, whose close connection to channel capacity is at the core of all of our results.
Objects are made of parts, each with distinct geometry, physics, functionality, and affordances. Developing such a distributed, physical, interpretable representation of objects will facilitate intelligent agents to better explore and interact with the world. In this paper, we study physical primitive decomposition---understanding an object through its components, each with physical and geometric attributes. As annotated data for object parts and physics are rare, we propose a novel formulation that learns physical primitives by explaining both an object's appearance and its behaviors in physical events. Our model performs well on block towers and tools in both synthetic and real scenarios; we also demonstrate that visual and physical observations often provide complementary signals. We further present ablation and behavioral studies to better understand our model and contrast it with human performance.
Quantum machine learning is expected to be one of the first potential general-purpose applications of near-term quantum devices. A major recent breakthrough in classical machine learning is the notion of generative adversarial training, where the gradients of a discriminator model are used to train a separate generative model. In this work and a companion paper, we extend adversarial training to the quantum domain and show how to construct generative adversarial networks using quantum circuits. Furthermore, we also show how to compute gradients -- a key element in generative adversarial network training -- using another quantum circuit. We give an example of a simple practical circuit ansatz to parametrize quantum machine learning models and perform a simple numerical experiment to demonstrate that quantum generative adversarial networks can be trained successfully.