University of Latvia

output

20022015

most citedSingle-parameter non-adiabatic quantized charge pumping

232 citations

Showing 2012 · quant-phShow all

6 papers · 2 filters

quant-ph2012★ 4 cited

Optimal quantum query bounds for almost all Boolean functions

Andris Ambainis, Arturs Backurs, Juris Smotrovs +1

We show that almost all n-bit Boolean functions have bounded-error quantum query complexity at least n/2, up to lower-order terms. This improves over an earlier n/4 lower bound of…

quant-ph2012★ 7 cited

Adversary Lower Bound for the k-sum Problem

Aleksandrs Belovs, Robert Spalek

We prove a tight quantum query lower bound $Ω (n^{k / (k + 1)})$ for the problem of deciding whether there exist $k$ numbers among $n$ that sum up to a prescribed number, provided that…

quant-ph2012

How Low Can Approximate Degree and Quantum Query Complexity be for Total Boolean Functions?

Andris Ambainis, Ronald de Wolf

It has long been known that any Boolean function that depends on n input variables has both degree and exact quantum query complexity of Omega(log n), and that this bound is achiev…

quant-ph2012★ 31 cited

Learning-Graph-Based Quantum Algorithm for k-distinctness

Aleksandrs Belovs

We present a quantum algorithm solving the $k$ -distinctness problem in $O (n^{1 - 2^{k - 2} / (2^{k} - 1)})$ queries with a bounded error. This improves the previous $O (n^{k / (k + 1)})$ -query al…

quant-ph2012★ 24 cited

Span programs and quantum algorithms for st-connectivity and claw detection

Aleksandrs Belovs, Ben W. Reichardt

We introduce a span program that decides st-connectivity, and generalize the span program to develop quantum algorithms for several graph problems. First, we give an algorithm for…

quant-ph2012★ 104 cited

Optical polarization of nuclear ensembles in diamond

Ran Fischer, Andrey Jarmola, Pauli Kehayias +1

We report polarization of a dense nuclear-spin ensemble in diamond and its dependence on magnetic field and temperature. The polarization method is based on the transfer of electro…