Valiant-Vazirani showed in 1985 [VV85] that solving NP with the promise that yes instances have only one witness is powerful enough to solve the entire NP class (under randomized reductions). We are interested in extending this result to the quantu
m setting. We prove extensions to the classes Merlin-Arthur MA and Quantum-Classical-Merlin-Arthur QCMA. Our results have implications for the complexity of approximating the ground state energy of a quantum local Hamiltonian with a unique ground state and an inverse polynomial spectral gap. We show that the estimation (to within polynomial accuracy) of the ground state energy of poly-gapped 1-D local Hamiltonians is QCMA-hard [AN02], under randomized reductions. This is in stark contrast to the case of constant gapped 1-D Hamiltonians, which is in NP [Has07]. Moreover, it shows that unless QCMA can be reduced to NP by randomized reductions, there is no classical description of the ground state of every poly-gapped local Hamiltonian that allows efficient calculation of expectation values. Finally, we discuss a few of the obstacles to the establishment of an analogous result to the class Quantum-Merlin-Arthur (QMA). In particular, we show that random projections fail to provide a polynomial gap between two witnesses.
In (single-server) Private Information Retrieval (PIR), a server holds a large database $DB$ of size $n$, and a client holds an index $i in [n]$ and wishes to retrieve $DB[i]$ without revealing $i$ to the server. It is well known that information the
oretic privacy even against an `honest but curious server requires $Omega(n)$ communication complexity. This is true even if quantum communication is allowed and is due to the ability of such an adversarial server to execute the protocol on a superposition of databases instead of on a specific database (`input purification attack). Nevertheless, there have been some proposals of protocols that achieve sub-linear communication and appear to provide some notion of privacy. Most notably, a protocol due to Le Gall (ToC 2012) with communication complexity $O(sqrt{n})$, and a protocol by Kerenidis et al. (QIC 2016) with communication complexity $O(log(n))$, and $O(n)$ shared entanglement. We show that, in a sense, input purification is the only potent adversarial strategy, and protocols such as the two protocols above are secure in a restricted variant of the quantum honest but curious (a.k.a specious) model. More explicitly, we propose a restricted privacy notion called emph{anchored privacy}, where the adversary is forced to execute on a classical database (i.e. the execution is anchored to a classical database). We show that for measurement-free protocols, anchored security against honest adversarial servers implies anchored privacy even against specious adversaries. Finally, we prove that even with (unlimited) pre-shared entanglement it is impossible to achieve security in the standard specious model with sub-linear communication, thus further substantiating the necessity of our relaxation. This lower bound may be of independent interest (in particular recalling that PIR is a special case of Fully Homomorphic Encryption).
Grovers algorithm confers on quantum computers a quadratic advantage over classical computers for searching in an arbitrary data set, a scenario that describes Bitcoin mining. It has previously been argued that the only side-effect of quantum mining
would be an increased difficulty. In this work, we argue that a crucial argument in the analysis of Bitcoin security breaks down when quantum mining is performed. Classically, a Bitcoin fork occurs rarely, i.e., when two miners find a block almost simultaneously, due to propagation time effects. The situation differs dramatically when quantum miners use Grovers algorithm, which repeatedly applies a procedure called a Grover iteration. The chances of finding a block grow quadratically with the number of Grover iterations applied. Crucially, a miner does not have to choose how many iterations to apply in advance. Suppose Alice receives Bobs new block. To maximize her revenue, she should stop and measure her state immediately in the hopes that her block (rather than Bobs) will become part of the longest chain. The strong correlation between the miners actions and the fact that they all measure their states at the same time may lead to more forks -- which is known to be a security risk for Bitcoin. We propose a mechanism that, we conjecture, will prevent this form of quantum mining, thereby circumventing the high rate of forks.
The security of the Bitcoin system is based on having a large amount of computational power in the hands of honest miners. Such miners are incentivized to join the system and validate transactions by the payments issued by the protocol to anyone who
creates blocks. As new bitcoins creation rate decreases (halving every 4 years), the revenue derived from transaction fees start to have an increasingly important role. We argue that Bitcoins current fee market does not extract revenue well when blocks are not congested. This effect has implications for the scalability debate: revenue from transaction fees may decrease if block size is increased. The current mechanism is a pay your bid auction in which included transactions pay the amount they suggested. We propose two alternative auction mechanisms: The Monopolistic Price Mechanism, and the Random Sampling Optimal Price Mechanism (due to Goldberg et al.). In the monopolistic price mechanism, the miner chooses the number of accepted transactions in the block, and all transactions pay exactly the smallest bid included in the block. The mechanism thus sets the block size dynamically (up to a bound required for fast block propagation and other security concerns). We show, using analysis and simulations, that this mechanism extracts revenue better from users, and that it is nearly incentive compatible: the profit due to strategic bidding relative to honest biding decreases as the number of bidders grows. Users can then simply set their bids truthfully to exactly the amount they are willing to pay to transact, and do not need to utilize fee estimate mechanisms, do not resort to bid shading and do not need to adjust transaction fees (via replace-by-fee mechanisms) if the mempool grows. We discuss these and other properties of our mechanisms, and explore various desired properties of fee market mechanisms for crypto-currencies.
A broad range of quantum optimisation problems can be phrased as the question whether a specific system has a ground state at zero energy, i.e. whether its Hamiltonian is frustration free. Frustration-free Hamiltonians, in turn, play a central role f
or constructing and understanding new phases of matter in quantum many-body physics. Unfortunately, determining whether this is the case is known to be a complexity-theoretically intractable problem. This makes it highly desirable to search for efficient heuristics and algorithms in order to, at least, partially answer this question. Here we prove a general criterion - a sufficient condition - under which a local Hamiltonian is guaranteed to be frustration free by lifting Shearers theorem from classical probability theory to the quantum world. Remarkably, evaluating this condition proceeds via a fully classical analysis of a hard-core lattice gas at negative fugacity on the Hamiltonians interaction graph which, as a statistical mechanics problem, is of interest in its own right. We concretely apply this criterion to local Hamiltonians on various regular lattices, while bringing to bear the tools of spin glass physics which permit us to obtain new bounds on the SAT/UNSAT transition in random quantum satisfiability. These also lead us to natural conjectures for when such bounds will be tight, as well as to a novel notion of universality for these computer science problems. Besides providing concrete algorithms leading to detailed and quantitative insights, this underscores the power of marrying classical statistical mechanics with quantum computation and complexity theory.
