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.
We construct the states that are invariant under the action of the generalized squeezing operator $exp{(z{a^{dagger k}}-z^*a^k)}$ for arbitrary positive integer $k$. The states are given explicitly in the number representation. We find that for a giv
en value of $k$ there are $k$ such states. We show that the states behave as $n^{-k/4}$ when occupation number $ntoinfty$. This implies that for any $kgeq3$ the states are normalizable. For a given $k$, the expectation values of operators of the form $(a^{dagger} a)^j$ are finite for positive integer $j < (k/2-1)$ but diverge for integer $jgeq (k/2-1)$. For $k=3$ we also give an explicit form of these states in the momentum representation in terms of Bessel functions.
Consider many instances of an arbitrary quadripartite pure state of four quantum systems ABCD. Alice holds the AC part of each state, Bob holds B, while D represents all other parties correlated with ABC. Alice is required to redistribute the C syste
ms to Bob while asymptotically preserving the overall purity. We prove that this is possible using Q qubits of communication and E ebits of shared entanglement between Alice and Bob, provided that Q geq I(C;D|B)/2 and Q+E geq H(C|B), proving the optimality of the Luo-Devetak outer bound. The optimal qubit rate provides the first known operational interpretation of quantum conditional mutual information. We also show how our protocol leads to a fully operational proof of strong subadditivity and uncover a general organizing principle, in analogy to thermodynamics, that underlies the optimal rates.
In this paper, an efficient arbitrated quantum signature scheme is proposed by combining quantum cryptographic techniques and some ideas in classical cryptography. In the presented scheme, the signatory and the receiver can share a long-term secret k
ey with the arbitrator by utilizing the key together with a random number. While in previous quantum signature schemes, the key shared between the signatory and the arbitrator or between the receiver and the arbitrator could be used only once, and thus each time when a signatory needs to sign, the signatory and the receiver have to obtain a new key shared with the arbitrator through a quantum key distribution protocol. Detailed theoretical analysis shows that the proposed scheme is efficient and provably secure.
An experiment proposed by Yurke and Stoler, and similar to that realized experimentally by Sciarrino et al., is analyzed. In Sciarrinos realization, identical photons from a degenerated down-conversion pair are used, i.e. the photons met in the past.
In the experiment analyzed here the particles are also identical, but from different sources. As long as one can tell from which source came each particle, the joint wave function remains factorizable. However, a configuration is created in which one cannot tell anymore which particle came from which source. As a result, the wave function becomes non-factorizable, symmetrical (for bosons) or antisymmetrical (for fermions). In part of the cases the situation is even more surprising: the particles never meet, s.t. the symmetry (antisymmetry) is produced at-a-distance without the particles having had the possibility to interact in any way.
We present a bounded-error quantum algorithm for evaluating Min-Max trees. For a tree of size N our algorithm makes N^{1/2+o(1)} comparison queries, which is close to the optimal complexity for this problem.
It is demonstrated that, if one remains in the framework of quantum mechanics taken alone, stationary states (energy eigenstates) are in no way singled out with respect to nonstationary ones, and moreover the stationary states would be difficult if p
ossible to realize in practice. Owing to the nonstationary states any quantum system can absorb or emit energy in arbitrary continuous amounts. The peculiarity of the stationary states appears only if electromagnetic radiation that must always accompany nonstationary processes in real systems is taken into account. On the other hand, when the quantum system absorbs or emits energy in the form of a wave the determining role is played by resonance interaction of the system with the wave. Here again the stationary states manifest themselves. These facts and influence of the resonator upon the incident wave enable one to explain all effects ascribed to manifestation of the corpuscular properties of light (the photoelectric effect, the Compton effect etc.) solely on a base of the wave concept of light.
We develop an extension of Bohmian mechanics to a curved background space-time containing a singularity. The present paper focuses on timelike singularities. We use the naked timelike singularity of the super-critical Reissner-Nordstrom geometry as a
n example. While one could impose boundary conditions at the singularity that would prevent the particles from falling into the singularity, we are interested here in the case in which particles have positive probability to hit the singularity and get annihilated. The wish for reversibility, equivariance, and the Markov property then dictates that particles must also be created by the singularity, and indeed dictates the rate at which this must occur. That is, a stochastic law prescribes what comes out of the singularity. We specify explicit equations of a non-rigorous model involving an interior-boundary condition on the wave function at the singularity, which can be used also in oth
We prove an area law for the entanglement entropy in gapped one dimensional quantum systems. The bound on the entropy grows surprisingly rapidly with the correlation length; we discuss this in terms of properties of quantum expanders and present a co
njecture on completely positive maps which may provide an alternate way of arriving at an area law. We also show that, for gapped, local systems, the bound on Von Neumann entropy implies a bound on R{e}nyi entropy for sufficiently large $alpha<1$ and implies the ability to approximate the ground state by a matrix product state.
The Schr{o}dinger equation is solved exactly for some well known potentials. Solutions are obtained reducing the Schr{o}dinger equation into a second order differential equation by using an appropriate coordinate transformation. The Nikiforov-Uvarov
method is used in the calculations to get energy eigenvalues and the corresponding wave functions.
