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.
One of the strongest techniques available for showing lower bounds on quantum communication complexity is the logarithm of the approximation rank of the communication matrix--the minimum rank of a matrix which is entrywise close to the communication
matrix. This technique has two main drawbacks: it is difficult to compute, and it is not known to lower bound quantum communication complexity with entanglement. Linial and Shraibman recently introduced a norm, called gamma_2^{alpha}, to quantum communication complexity, showing that it can be used to lower bound communication with entanglement. Here the parameter alpha is a measure of approximation which is related to the allowable error probability of the protocol. This bound can be written as a semidefinite program and gives bounds at least as large as many techniques in the literature, although it is smaller than the corresponding alpha-approximation rank, rk_alpha. We show that in fact log gamma_2^{alpha}(A)$ and log rk_{alpha}(A)$ agree up to small factors. As corollaries we obtain a constant factor polynomial time approximation algorithm to the logarithm of approximate rank, and that the logarithm of approximation rank is a lower bound for quantum communication complexity with entanglement.
We prove that every key agreement protocol in the random oracle model in which the honest users make at most $n$ queries to the oracle can be broken by an adversary who makes $O(n^2)$ queries to the oracle. This improves on the previous $widetilde{Om
ega}(n^6)$ query attack given by Impagliazzo and Rudich (STOC 89) and resolves an open question posed by them. Our bound is optimal up to a constant factor since Merkle proposed a key agreement protocol in 1974 that can be easily implemented with $n$ queries to a random oracle and cannot be broken by any adversary who asks $o(n^2)$ queries.
We show that every construction of one-time signature schemes from a random oracle achieves black-box security at most $2^{(1+o(1))q}$, where $q$ is the total number of oracle queries asked by the key generation, signing, and verification algorithms.
That is, any such scheme can be broken with probability close to $1$ by a (computationally unbounded) adversary making $2^{(1+o(1))q}$ queries to the oracle. This is tight up to a constant factor in the number of queries, since a simple modification of Lamports one-time signatures (Lamport 79) achieves $2^{(0.812-o(1))q}$ black-box security using $q$ queries to the oracle. Our result extends (with a loss of a constant factor in the number of queries) also to the random permutation and ideal-cipher oracles. Since the symmetric primitives (e.g. block ciphers, hash functions, and message authentication codes) can be constructed by a constant number of queries to the mentioned oracles, as corollary we get lower bounds on the efficiency of signature schemes from symmetric primitives when the construction is black-box. This can be taken as evidence of an inherent efficiency gap between signature schemes and symmetric primitives.
In this paper, we present a new, graph-based modeling approach and a polynomial-sized linear programming (LP) formulation of the Boolean satisfiability problem (SAT). The approach is illustrated with a numerical example.
This paper gives the definitions of an anomalous super-increasing sequence and an anomalous subset sum separately, proves the two properties of an anomalous super-increasing sequence, and proposes the REESSE2+ public-key encryption scheme which inclu
des the three algorithms for key generation, encryption and decryption. The paper discusses the necessity and sufficiency of the lever function for preventing the Shamir extremum attack, analyzes the security of REESSE2+ against extracting a private key from a public key through the exhaustive search, recovering a plaintext from a ciphertext plus a knapsack of high density through the L3 lattice basis reduction method, and heuristically obtaining a plaintext through the meet-in-the-middle attack or the adaptive-chosen-ciphertext attack. The authors evaluate the time complexity of REESSE2+ encryption and decryption algorithms, compare REESSE2+ with ECC and NTRU, and find that the encryption speed of REESSE2+ is ten thousand times faster than ECC and NTRU bearing the equivalent security, and the decryption speed of REESSE2+ is roughly equivalent to ECC and NTRU respectively.
This paper has been withdrawn because Theorem 21 and Corollary 22 are in error; The modeling idea is OK, but it needs 9-dimensional variables instead of the 8-dimensional variables defined in notations 6.9. Examples of the correct model (with 9-ind
ex variables) are: (1) Diaby, M., Linear Programming Formulation of the Set Partitioning Problem, International Journal of Operational Research 8:4 (August 2010) pp. 399-427; (2) Diaby, M., Linear Programming Formulation of the Vertex Coloring Problem, International Journal of Mathematics in Operational Research 2:3 (May 2010) pp. 259-289; (3) Diaby, M., The Traveling Salesman Problem: A Linear Programming Formulation, WSEAS Transactions on Mathematics, 6:6 (June 2007) pp. 745-754.
We survey recent results on the topological complexity of context-free omega-languages which form the second level of the Chomsky hierarchy of languages of infinite words. In particular, we consider the Borel hierarchy and the Wadge hierarchy of non-
deterministic or deterministic context-free omega-languages. We study also decision problems, the links with the notions of ambiguity and of degrees of ambiguity, and the special case of omega-powers.
We study the complexity of computing the projection of an arbitrary $d$-polytope along $k$ orthogonal vectors for various input and output forms. We show that if $d$ and $k$ are part of the input (i.e. not a constant) and we are interested in output-
sensitive algorithms, then in most forms the problem is equivalent to enumerating vertices of polytopes, except in two where it is NP-hard. In two other forms the problem is trivial. We also review the complexity of computing projections when the projection directions are in some sense non-degenerate. For full-dimensional polytopes containing origin in the interior, projection is an operation dual to intersecting the polytope with a suitable linear subspace and so the results in this paper can be dualized by interchanging vertices with facets and projection with intersection. To compare the complexity of projection and vertex enumeration, we define new complexity classes based on the complexity of Vertex Enumeration.
Knot and link invariants naturally arise from any braided Hopf algebra. We consider the computational complexity of the invariants arising from an elementary family of finite-dimensional Hopf algebras: quantum doubles of finite groups (denoted D(G),
for a group G). Regarding algorithms for these invariants, we develop quantum circuits for the quantum Fourier transform over D(G); in general, we show that when one can uniformly and efficiently carry out the quantum Fourier transform over the centralizers Z(g) of the elements of G, one can efficiently carry out the quantum Fourier transform over D(G). We apply these results to the symmetric groups to yield efficient circuits for the quantum Fourier transform over D(S_n). With such a Fourier transform, it is straightforward to obtain additive approximation algorithms for the related link invariant. Additionally, we show that certain D(G) invariants (such as D(A_n) invariants) are BPP-hard to additively approximate, SBP-hard to multiplicatively approximate, and #P-hard to exactly evaluate. Finally, we make partial progress on the question of simulating anyonic computation in groups uniformly as a function of the group size. In this direction, we provide efficient quantum circuits for the Clebsch-Gordan transform over D(G) for fluxon irreps, i.e., irreps of D(G) characterized by a conjugacy class of G. For general irreps, i.e., those which are associated with a conjugacy class of G and an irrep of a centralizer, we present an efficient implementation under certain conditions such as when there is an efficient Clebsch-Gordan transform over the centralizers. We remark that this also provides a simulation of certain anyonic models of quantum computation, even in circumstances where the group may have size exponential in the size of the circuit.
