In classical Monty Hall problem, one player can always win with probability 2/3. We generalize the problem to the quantum domain and show that a fair two-party zero-sum game can be carried out if the other player is permitted to adopt quantum measurement strategy.
We initiate the study of quantum races, games where two or more quantum computers compete to solve a computational problem. While the problem of dueling algorithms has been studied for classical deterministic algorithms, the quantum case presents add
itional sources of uncertainty for the players. The foremost among these is that players do not know if they have solved the problem until they measure their quantum state. This question of `when to measure? presents a very interesting strategic problem. We develop a game-theoretic model of a multiplayer quantum race, and find an approximate Nash equilibrium where all players play the same strategy. In the two-party case, we further show that this strategy is nearly optimal in terms of payoff among all symmetric Nash equilibria. A key role in our analysis of quantum races is played by a more tractable version of the game where there is no payout on a tie; for such races we completely characterize the Nash equilibria in the two-party case. One application of our results is to the stability of the Bitcoin protocol when mining is done by quantum computers. Bitcoin mining is a race to solve a computational search problem, with the winner gaining the right to create a new block. Our results inform the strategies that eventual quantum miners should use, and also indicate that the collision probability---the probability that two miners find a new block at the same time---would not be too high in the case of quantum miners. Such collisions are undesirable as they lead to forking of the Bitcoin blockchain.
This thesis is divided into two parts. In Part I we introduce a new formalism for quantum strategies, which specify the actions of one party in any multi-party interaction involving the exchange of multiple quantum messages among the parties. This fo
rmalism associates with each strategy a single positive semidefinite operator acting only upon the tensor product of the input and output message spaces for the strategy. We establish three fundamental properties of this new representation for quantum strategies and we list several applications, including a quantum version of von Neumanns celebrated 1928 Min-Max Theorem for zero-sum games and an efficient algorithm for computing the value of such a game. In Part II we establish several properties of a class of quantum operations that can be implemented locally with shared quantum entanglement or classical randomness. In particular, we establish the existence of a ball of local operations with shared randomness lying within the space spanned by the no-signaling operations and centred at the completely noisy channel. The existence of this ball is employed to prove that the weak membership problem for local operations with shared entanglement is strongly NP-hard. We also provide characterizations of local operations in terms of linear functionals that are positive and completely positive on a certain cone of Hermitian operators, under a natural notion of complete positivity appropriate to that cone. We end the thesis with a discussion of the properties of no-signaling quantum operations.
We derive general discrimination of quantum states chosen from a certain set, given initial $M$ copies of each state, and obtain the matrix inequality, which describe the bound between the maximum probability of correctly determining and that of erro
r. The former works are special cases of our results.
We describe a quantum mechanical measurement as a variational principle including interaction between the system under measurement and the measurement apparatus. Augmenting the action with a nonlocal term (a double integration over the duration of th
e interaction) results in a theory capable of describing both the measurement process (agreement between system state and pointer state) and the collapse of both systems into a single eigenstate (or superposition of degenerate eigenstates) of the relevant operator. In the absence of the interaction, a superposition of states is stable, and the theory agrees with the predictions of standard quantum theory. Because the theory is nonlocal, the resulting wave equation is an integrodifferential equation (IDE). We demonstrate these ideas using a simple Lagrangian for both systems, as proof of principle. The variational principle is time-symmetric and retrocausal, so the solution for the measurement process is determined by boundary conditions at both initial and final times; the initial condition is determined by the experimental preparation and the final condition is the natural boundary condition of variational calculus. We hypothesize that one or more hidden variables (not ruled out by Bells Theorem, due both to the retrocausality and the nonlocality of the theory) influence the outcome of the measurement, and that distributions of the hidden variables that arise plausibly in a typical ensemble of experimental realizations give rise to outcome frequencies consistent with Borns rule. We outline steps in a theoretical validation of the hypothesis. We discuss the role of both initial and final conditions to determine a solution at intermediate times, the mechanism by which a system responds to measurement, time symmetry of the new theory, causality concerns, and issues surrounding solution of the IDE.
Maximum-likelihood estimation is applied to identification of an unknown quantum mechanical process represented by a ``black box. In contrast to linear reconstruction schemes the proposed approach always yields physically sensible results. Its feasib
ility is demonstrated using the Monte Carlo simulations for the two-level system (single qubit).