|
Vol.19
No.15&16,
December 1, 2019
Research Articles:
Learning DNFs under product distributions via
mu--biased
quantum Fourier sampling
(pp1261-1278)
Varun Kanade, Andrea Rocchetto, and Simone Severini
We show that DNF formulae can be
quantum PAC-learned in polynomial time under product distributions using
a quantum example oracle. The current best classical algorithm runs in
superpolynomial time. Our result extends the work by Bshouty and Jackson
(1998) that proved that DNF formulae are efficiently learnable
under the uniform distribution using a quantum example oracle. Our proof
is based on a new quantum algorithm that efficiently samples the
coefficients of a $\mu$--biased
Fourier transform.
State-independent quantum key distribution with two-way classical
communication
(pp1279-1293)
Radha Pyari Sandhir
A quantum key distribution
protocol is proposed that is a variation of BB84 that provides raw key
generation from correlations that violate a Bell-type inequality for
single qubit systems and not entangled pairs. Additionally, it 1) is
state-independent, 2) involves two-way classical communication, and 3)
does not require basis matching between the two parties. The
Brukner-Taylor-Cheung-Vedral (BTCV) time-like form of the Bell-CHSH
inequality \cite{Bruk04,Tayl04}
is employed as an eavesdropping check; sequential measurements lead to
an inequality identical in form to the Bell-CHSH inequality, which
relies only on the measurements performed with no regard for the qubit
states. We show that this form manifests naturally from the non-commutativity
of observables.
Variance of the sum of independent quantum computing errors
(pp1294-1312)
Jesus Lacalle and Luis
Miguel Pozo Coronado
The sum of quantum computing
errors is the key element both for the estimation and control of errors
in quantum computing and for its statistical study. In this article we
analyze the sum of two independent quantum computing errors,
$X_1$
and $X_2$,
and we obtain the formula of the variance of the sum of these errors:
$$V(X_1+X_2)=V(X_1)+V(X_2)-\frac{V(X_1)V(X_2)}{2}.$$
We conjecture that this result holds true
for general quantum computing errors and we prove the formula for
independent isotropic quantum computing errors.
Exploiting Faraday rotation to jam quantum key distribution via
polarized photons
(pp1313-1324)
Maximilian Daschner, David I. Kaiser, and Joseph A.
Formaggio
Quantum key distribution (QKD)
involving polarized photons could be vulnerable to a jamming (or
denial-of-service) attack, in which a third party applies an external
magnetic field to rotate the plane of polarization of photons headed
toward one of the two intended recipients. Sufficiently large Faraday
rotation of one of the polarized beams would prevent Alice and Bob from
establishing a secure quantum channel. We investigate requirements to
induce such rotation both for free-space transmission and for
transmission via optical fiber, and find reasonable ranges of parameters
in which a jamming attack could be successful against fiber-based QKD,
even for systems that implement automated recalibration for
polarization-frame alignment. The jamming attack could be applied
selectively and indefinitely by an adversary without revealing her
presence, and could be further combined with various eavesdropping
attacks to yield unauthorized information.
Quantum and classical algorithms for
approximate submodular function minimization
(pp1325-1249)
Yassine Hamoudi, Patrick Rebentrost, Ansis Rosmanis, and
Muklos Santha
Submodular functions are set
functions mapping every subset of some ground set of size
$n$
into the real numbers and satisfying the diminishing returns property.
Submodular minimization is an
important field in discrete optimization theory due to its relevance for
various branches of mathematics, computer science and economics. The
currently fastest strongly polynomial algorithm for exact minimization~\cite{LSW15}
runs in time $\so{n^3 \cdot \eo +
n^4}$ where
$\eo$
denotes the cost to evaluate the function on any set. For functions with
range $[-1,1]$,
the best $\eps$-additive
approximation algorithm~\cite{CLSW17}
runs in time $\so{n^{5/3}/\eps^{2}
\cdot \eo}$.In this paper we
present a classical and a quantum algorithm for approximate
submodular
minimization. Our classical result improves on the algorithm of
\cite{CLSW17}
and runs in time $\so{n^{3/2}/\eps^2
\cdot \eo}$. Our quantum algorithm
is, up to our knowledge, the first attempt to use quantum computing for
submodular optimization. The
algorithm runs in time $\so{n^{5/4}/\eps^{5/2}
\cdot \log(1/\eps) \cdot \eo}$. The
main ingredient of the quantum result is a new method for sampling with
high probability $T$
independent elements from any discrete probability distribution of
support size $n$
in time $\bo{\sqrt{Tn}}$.
Previous quantum algorithms for this problem were of complexity
$\bo{T\sqrt{n}}$.
back to QIC online Front page
|
