- Span programs are a model of computation that have been used to design quantum algorithms, mainly in the query model. For any decision problem, there exists a span program that leads to an algorithm with optimal quantum query complexity, but finding such an algorithm is generally challenging. We consider new ways of designing quantum algorithms using span programs. We show how any span program that decides a problem $f$ can also be used to decide "property testing" versions of $f$, or more generally, approximate the span program witness size, a property of the input related to $f$. For example, using our techniques, the span program for OR, which can be used to design an optimal algorithm for the OR function, can also be used to design optimal algorithms for: threshold functions, in which we want to decide if the Hamming weight of a string is above a threshold or far below, given the promise that one of these is true; and approximate counting, in which we want to estimate the Hamming weight of the input. We achieve these results by relaxing the requirement that 1-inputs hit some target exactly in the span program, which could make design of span programs easier. We also give an exposition of span program structure, which increases the understanding of this important model. One implication is alternative algorithms for estimating the witness size when the phase gap of a certain unitary can be lower bounded. We show how to lower bound this phase gap in some cases. As applications, we give the first upper bounds in the adjacency query model on the quantum time complexity of estimating the effective resistance between $s$ and $t$, $R_{s,t}(G)$, of $\tilde O(\frac{1}{\epsilon^{3/2}}n\sqrt{R_{s,t}(G)})$, and, when $\mu$ is a lower bound on $\lambda_2(G)$, by our phase gap lower bound, we can obtain $\tilde O(\frac{1}{\epsilon}n\sqrt{R_{s,t}(G)/\mu})$, both using $O(\log n)$ space.
- In this article we propose a stroboscopic approach to complex vector reconstruction in the context of quantum tomography. There are two underlying assumptions behind our reasoning. The first one claims that the evolution of a d-level pure quantum system is given by the Schrödinger equation with a time-independent Hamiltonian and the other states that the knowledge about the quantum state is provided from projective measurements, also called intensity measurements. The problem of quantum state reconstruction is connected with the notion known as phase retrieval - recovering a complex vector from modulus of inner product with frame vectors. We believe that the stroboscopic approach can significantly improve the effectiveness of the vector reconstruction as it aims to decrease the number of distinct projectors by taking advantage of the knowledge about the evolution. General conditions and observations are applied to a specific unitary model.
- Jul 03 2015 quant-ph arXiv:1507.00423v1We show that the particle number distribution of diamond modes, modes that are localised in a finite space-time region, are thermal for the Minkowski vacuum state of a massless scalar field, an analogue to the Unruh effect. The temperature of the diamond is inversely proportional to its size. An inertial observer can detect this thermal radiation by coupling to the diamond modes using an appropriate energy scaled detector. We further investigate the correlations between various diamonds and find that entanglement between adjacent diamonds dominates.
- Jul 03 2015 quant-ph arXiv:1507.00402v1Based on homodyne detection, we discuss how the presence of an event horizon affects quantum communication between an inertial partner, Alice, and a uniformly accelerated partner, Rob. We show that there exists a low frequency cutoff for Rob's homodyne detector that maximizes the signal to noise ratio and it approximately corresponds to the Unruh frequency. In addition, the low frequency cutoff which minimizes the conditional variance between Alice's input state and Rob's output state is also approximately equal to the Unruh frequency. Thus the Unruh frequency provides a natural low frequency cutoff in order to optimize quantum communication of both classical and quantum information between Alice and Rob.
- Given a directed acyclic graph $G,$ and a set of values $y$ on the vertices, the Isotonic Regression of $y$ is a vector $x$ that respects the partial order described by $G,$ and minimizes $||x-y||,$ for a specified norm. This paper gives improved algorithms for computing the Isotonic Regression for all weighted $\ell_{p}$-norms with rigorous performance guarantees. Our algorithms are quite practical, and their variants can be implemented to run fast in practice.
- Jul 03 2015 quant-ph arXiv:1507.00628v1We inverse engineer realizable time-dependent semiclassical pulses to invert or manipulate a two- level system faster than adiabatically when the rotating-wave approximation cannot be applied. Different inversion routes, based on a counterdiabatic approach or invariants, lead quite generally to singular fields. Making use of the relation between the invariants of motion and the Hamiltonian, and canceling the troublesome singularities, an inversion scheme is put forward for the regime in which the pulse spans few oscillations. For many oscillations an alternative numerical minimization method is proposed and demonstrated.
- Jul 03 2015 quant-ph arXiv:1507.00626v1We study a general family of quantum protocols for position verification and present a new class of attacks based on the Clifford hierarchy. These attacks outperform current strategies based on port-based teleportation for a large class of practical protocols. We then introduce the Interleaved Product protocol, a new scheme for position verification involving only the preparation and measurement of single-qubit states for which the best available attacks have a complexity exponential in the number of classical bits transmitted.
- We consider two entangled accelerating qubits coupled with real scalar fields, each described by the Unruh-Wald model. It is demonstrated that because of the Unruh effect, the bipartite entanglement of the two qubits suddenly dies when the acceleration of one or more qubits are large enough. We also consider three entangled accelerating qubits in GHZ state and in W state, with equal acceleration-frequency ratio, and found that in either state, the tripartite entanglement suddenly dies at a certain value of acceleration-frequency ratio. The equivalence between the Rindler metric and the Schwarzchild metric in the vicinity of the horizon of a black hole implies that for the two entangled qubits outside a black hole, the entanglement suddenly dies when one or both of the qubits are close enough to the horizon, while for the three entangled qubits in GHZ or W state, the tripartite entanglement suddenly dies when these qubits are close enough to the horizon.
- Anonymous Veto (AV) and Dining cryptographers (DC) are two basic primitives for the cryptographic problems that can hide the identity of the sender(s) of classical information. They can be achieved by classical methods and the security is based on computational hardness or requires pairwise shared private keys. In this regard, we present a secure quantum protocol for both DC and AV problems by exploiting the GHZ correlation. We first solve a generalized version of the DC problem with the help of multiparty GHZ state. This allow us to provide a secure quantum protocol for the AV problem. Security of both the protocols rely on some novel and fundamental features of the GHZ correlation known as GHZ paradox.
- Jul 03 2015 astro-ph.GA arXiv:1507.00721v1
- Jul 03 2015 astro-ph.CO arXiv:1507.00718v1
- Jul 03 2015 math.DS arXiv:1507.00714v1
- Jul 03 2015 astro-ph.GA arXiv:1507.00713v1
- Jul 03 2015 cs.CR arXiv:1507.00712v1
- Jul 03 2015 astro-ph.GA arXiv:1507.00709v1
- Jul 03 2015 astro-ph.SR arXiv:1507.00708v1
- Jul 03 2015 astro-ph.GA astro-ph.HE arXiv:1507.00706v1
- Jul 03 2015 math.OC arXiv:1507.00705v1
- Jul 03 2015 astro-ph.GA astro-ph.HE arXiv:1507.00704v1
- Jul 03 2015 cond-mat.mes-hall cond-mat.mtrl-sci arXiv:1507.00703v1
- Jul 03 2015 math.GT arXiv:1507.00699v1
- Jul 03 2015 math.DS arXiv:1507.00698v1
- Jul 03 2015 nucl-th arXiv:1507.00697v1
- Jul 03 2015 math.PR arXiv:1507.00696v1
- Jul 03 2015 math.AP arXiv:1507.00694v1
- Jul 03 2015 cs.SI arXiv:1507.00691v1
- Jul 03 2015 cond-mat.str-el arXiv:1507.00689v1
- Jul 03 2015 math.AG arXiv:1507.00688v1
- Jul 03 2015 cs.NA arXiv:1507.00687v1
- Jul 03 2015 physics.optics arXiv:1507.00686v1
- Jul 03 2015 math.NT arXiv:1507.00684v1
- Jul 03 2015 stat.AP arXiv:1507.00683v1
- Jul 03 2015 math.AG arXiv:1507.00682v1
- Jul 03 2015 math.DG arXiv:1507.00681v1
- Jul 03 2015 gr-qc arXiv:1507.00680v1
- Jul 03 2015 math.PR arXiv:1507.00678v1
- Jul 03 2015 astro-ph.CO astro-ph.GA arXiv:1507.00676v1