A Criterion for Attaining the Welch Bounds with Applications for Mutually Unbiased Bases

The paper gives a short introduction to mutually unbiased bases and the Welch bounds and demonstrates that the latter is a good technical tool to explore the former. In particular, a criterion for a system of vectors to satisfy the Welch bounds with equality is given and applied for the case of MUBs. This yields a necessary and sufficient condition on a set of orthonormal bases to form a complete system of MUBs. This condition takes an especially elegant form in the case of homogeneous systems of MUBs. We express some known constructions of MUBs in this form. Also it is shown how recently obtained results binding MUBs and some combinatorial structures (such as perfect nonlinear functions an…

"Adversary" metodes izmantošana kvantu vaicājošajiem algoritmiem

Disertācijā es izmantoju nesen izstrādātu kvantu vaicājumu sarežģītības precīzu raksturojumu - adversary metodi - lai konstruētu jaunus kvantu algoritmus un apakšējos novērtējumus. Rezultāti ir sekojoši: tika izstrādāta jauna tehnika kvantu algoritmu konstruēšanai: mācīšanas grafi; mācīšanas grafi tika izmantoti lai uzlabotu kvantu vaicājumu sarežģītību trijstūra atrašanas un k-atšķirīguma problēmām; tika pierādīti precīzi apakšējie novērtējumi k-sumas un trijsūra summas problēmām; tika uzbūvēti kvantu algoritmi dažu apakšgrafu meklēšanas problēmām, kas ir optimāli vaicājumu, laik un atmiņas ziņā;tika izstrādāts kvantu klejošanas vispārinājums, kas savieno grafa elektriskās īpašības ar kvan…

Quantum lower bound for inverting a permutation with advice

Given a random permutation $f: [N] \to [N]$ as a black box and $y \in [N]$, we want to output $x = f^{-1}(y)$. Supplementary to our input, we are given classical advice in the form of a pre-computed data structure; this advice can depend on the permutation but \emph{not} on the input $y$. Classically, there is a data structure of size $\tilde{O}(S)$ and an algorithm that with the help of the data structure, given $f(x)$, can invert $f$ in time $\tilde{O}(T)$, for every choice of parameters $S$, $T$, such that $S\cdot T \ge N$. We prove a quantum lower bound of $T^2\cdot S \ge \tilde{\Omega}(\epsilon N)$ for quantum algorithms that invert a random permutation $f$ on an $\epsilon$ fraction of…

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

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 st-connectivity that uses O(n d^{1/2}) quantum queries to the n x n adjacency matrix to decide if vertices s and t are connected, under the promise that they either are connected by a path of length at most d, or are disconnected. We also show that if T is a path, a star with two subdivided legs, or a subdivision of a claw, its presence as a subgraph in the input graph G can be detected with O(n) quantum queries to the adjacency matrix. Under the promise that G either contains T as a subgraph or does not contain T…

Testing convexity of functions over finite domains

We establish new upper and lower bounds on the number of queries required to test convexity of functions over various discrete domains. 1. We provide a simplified version of the non-adaptive convexity tester on the line. We re-prove the upper bound $O(\frac{\log(\epsilon n)}{\epsilon})$ in the usual uniform model, and prove an $O(\frac{\log n}{\epsilon})$ upper bound in the distribution-free setting. 2. We show a tight lower bound of $\Omega(\frac{\log(\epsilon n)}{\epsilon})$ queries for testing convexity of functions $f: [n] \rightarrow \mathbb{R}$ on the line. This lower bound applies to both adaptive and non-adaptive algorithms, and matches the upper bound from item 1, showing that adap…

Span programs for functions with constant-sized 1-certificates

Besides the Hidden Subgroup Problem, the second large class of quantum speed-ups is for functions with constant-sized 1-certificates. This includes the OR function, solvable by the Grover algorithm, the element distinctness, the triangle and other problems. The usual way to solve them is by quantum walk on the Johnson graph. We propose a solution for the same problems using span programs. The span program is a computational model equivalent to the quantum query algorithm in its strength, and yet very different in its outfit. We prove the power of our approach by designing a quantum algorithm for the triangle problem with query complexity O(n35/27) that is better than O(n13/10) of the best p…

Span Programs for Functions with Constant-Sized 1-certificates

Besides the Hidden Subgroup Problem, the second large class of quantum speed-ups is for functions with constant-sized 1-certificates. This includes the OR function, solvable by the Grover algorithm, the distinctness, the triangle and other problems. The usual way to solve them is by quantum walk on the Johnson graph. We propose a solution for the same problems using span programs. The span program is a computational model equivalent to the quantum query algorithm in its strength, and yet very different in its outfit. We prove the power of our approach by designing a quantum algorithm for the triangle problem with query complexity $O(n^{35/27})$ that is better than $O(n^{13/10})$ of the best…

Quantum Algorithms for Learning Symmetric Juntas via Adversary Bound

In this paper, we study the following variant of the junta learning problem. We are given oracle access to a Boolean function f on n variables that only depends on k variables, and, when restricted to them, equals some predefined function h. The task is to identify the variables the function depends on. This is a generalisation of the Bernstein-Vazirani problem (when h is the XOR function) and the combinatorial group testing problem (when h is the OR function). We analyse the general case using the adversary bound, and give an alternative formulation for the quantum query complexity of this problem. We construct optimal quantum query algorithms for the cases when h is the OR function (compl…

ES fondu līdzfinansējums kā mazās un vidējās uzņēmējdarbības veicināšanas līdzeklis Latvijā. ERAF līdzekļu piesaiste SIA „Ēkas siltināšana” piemērā.

Bakalaura darba temats ir „ES fondu līdzfinansējums kā mazās un vidējās uzņēmējdarbības veicināšanas līdzeklis Latvijā. ERAF līdzekļu piesaiste SIA „Ēkas siltināšana” piemērā”. Darbā ir apkopota informācija par mazo un vidējo uzņēmumu (MVU) stāvokli Eiropas Savienībā (ES) un Latvijā, ir apskatīti MVU atbalsta un attīstības pasākumi. Pētījuma centrā ir SIA „Ēkas siltināšana” — Latvijas MVU, kuru var nosaukt par ES reģionālās politikas bērnu. Uzņēmuma pamatdarbība ir ēku siltumnoturības uzlabošanas projekti, kuri tiek realizēti ar Eiropas Reģionālās attīstības fonda (ERAF) līdzfinansējuma piesaisti. Firmas pamatdarbības, kā arī iekšējās un ārējās vides analīze ļauj secināt, kādus stratēģiskus…

On the Power of Non-adaptive Learning Graphs

We introduce a notion of the quantum query complexity of a certificate structure. This is a formalisation of a well-known observation that many quantum query algorithms only require the knowledge of the disposition of possible certificates in the input string, not the precise values therein. Next, we derive a dual formulation of the complexity of a non-adaptive learning graph, and use it to show that non-adaptive learning graphs are tight for all certificate structures. By this, we mean that there exists a function possessing the certificate structure and such that a learning graph gives an optimal quantum query algorithm for it. For a special case of certificate structures generated by cer…

A Criterion for Attaining the Welch Bounds with Applications for Mutually Unbiased Bases

The paper gives a short introduction to mutually unbiased bases and the Welch bounds and demonstrates that the latter is a good technical tool to explore the former. In particular, a criterion for a system of vectors to satisfy the Welch bounds with equality is given and applied for the case of MUBs. This yields a necessary and sufficient condition on a set of orthonormal bases to form a complete system of MUBs. This condition takes an especially elegant form in the case of homogeneous systems of MUBs. We express some known constructions of MUBs in this form. Also it is shown how recently obtained results binding MUBs and some combinatorial structures (such as perfect nonlinear functions an…

Quantum Algorithm for Distribution-Free Junta Testing

Inspired by a recent classical distribution-free junta tester by Chen, Liu, Serverdio, Sheng, and Xie (STOC’18), we construct a quantum tester for the same problem with complexity \(O(k/\varepsilon )\), which constitutes a quadratic improvement.

Daži aspekti bezgalīgo vārdu apstrādei ar Mīlija mašīnām

Darbā ir aplūkota Mīliju mašīnu, kas ir galīgo automātu-transformatoru paveids, uzvedība uz vienpusējiem bezgalīgiem vārdiem. Ir ievests bezgalīgo vārdu kvazisakārtojums pēc pārstrādāšanas ar Mīlija mašīnu. Ir izpētītas dažas algebriskas īpašības daļējam sakārtojumam, kas rodas pēc faktorizācijas pēc kanoniskas ekvivalences attiecības. Papildus, ir dabūti kvalitatīvi rezultāti par noteikto, no kombinatorikas puses interesanto vārdu īpašību saglabāšanu, pielietojot tiem Mīlija mašīnas. Visdziļāk ir aplūkota vienmērīgi rekurento vārdu klase. Ir doti divi pieradījumi, šīs īpašības saglabāšanai, ka arī daži kvantitatīvi rezultāti.

Quantum Algorithm for k-distinctness with Prior Knowledge on the Input

It is known that the dual of the general adversary bound can be used to build quantum query algorithms with optimal complexity. Despite this result, not many quantum algorithms have been designed this way. This paper shows another example of such algorithm. We use the learning graph technique from arXiv:1105.4024 to give a quantum algorithm for $k$-distinctness problem that runs in $o(n^{3/4})$ queries, for a fixed $k$, given some prior knowledge on the structure of the input. The best known quantum algorithm for the unconditional problem uses $O(n^{k/(k+1)})$ queries.

Time and space efficient quantum algorithms for detecting cycles and testing bipartiteness

We study space and time efficient quantum algorithms for two graph problems -- deciding whether an $n$-vertex graph is a forest, and whether it is bipartite. Via a reduction to the s-t connectivity problem, we describe quantum algorithms for deciding both properties in $\tilde{O}(n^{3/2})$ time and using $O(\log n)$ classical and quantum bits of storage in the adjacency matrix model. We then present quantum algorithms for deciding the two properties in the adjacency array model, which run in time $\tilde{O}(n\sqrt{d_m})$ and also require $O(\log n)$ space, where $d_m$ is the maximum degree of any vertex in the input graph.

Non-intersecting Complexity

A new complexity measure for Boolean functions is introduced in this article. It has a link to the query algorithms: it stands between both polynomial degree and non-deterministic complexity on one hand and still is a lower bound for deterministic complexity. Some inequalities and counterexamples are presented and usage in symmetrisation polynomials is considered.

Span-program-based quantum algorithm for the rank problem

Recently, span programs have been shown to be equivalent to quantum query algorithms. It is an open problem whether this equivalence can be utilized in order to come up with new quantum algorithms. We address this problem by providing span programs for some linear algebra problems. We develop a notion of a high level span program, that abstracts from loading input vectors into a span program. Then we give a high level span program for the rank problem. The last section of the paper deals with reducing a high level span program to an ordinary span program that can be solved using known quantum query algorithms.

Separations in Query Complexity Based on Pointer Functions

In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized query complexity for a total boolean function is given by the function $f$ on $n=2^k$ bits defined by a complete binary tree of NAND gates of depth $k$, which achieves $R_0(f) = O(D(f)^{0.7537\ldots})$. We show this is false by giving an example of a total boolean function $f$ on $n$ bits whose deterministic query complexity is $\Omega(n/\log(n))$ while its zero-error randomized query complexity is $\tilde O(\sqrt{n})$. We further show that the quantum query complexity of the same function is $\tilde O(n^{1/4})$, giving the first example of a total function with a super-quadra…

Quantum Dual Adversary for Hidden Subgroups and Beyond

An explicit quantum dual adversary for the S-isomorphism problem is constructed. As a consequence, this gives an alternative proof that the query complexity of the dihedral hidden subgroup problem is polynomial.

The completely distributive lattice of machine invariant sets of infnite words

Applications of Adversary Method in Quantum Query Algorithms

Elektroniskā versija nesatur pielikumus

Time-Efficient Quantum Walks for 3-Distinctness

We present two quantum walk algorithms for 3-Distinctness. Both algorithms have time complexity $\tilde{O}(n^{5/7})$, improving the previous $\tilde{O}(n^{3/4})$ and matching the best known upper bound for query complexity (obtained via learning graphs) up to log factors. The first algorithm is based on a connection between quantum walks and electric networks. The second algorithm uses an extension of the quantum walk search framework that facilitates quantum walks with nested updates.

Learning-Graph-Based Quantum Algorithm for k-distinctness

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 algorithm by Ambainis. The construction uses a modified learning graph approach. Compared to the recent paper by Belovs and Lee arXiv:1108.3022, the algorithm doesn't require any prior information on the input, and the complexity analysis is much simpler. Additionally, we introduce an $O(\sqrt{n}\alpha^{1/6})$ algorithm for the graph collision problem where $\alpha$ is the independence number of the graph.

Adaptive Lower Bound for Testing Monotonicity on the Line

In the property testing model, the task is to distinguish objects possessing some property from the objects that are far from it. One of such properties is monotonicity, when the objects are functions from one poset to another. This is an active area of research. In this paper we study query complexity of $\epsilon$-testing monotonicity of a function $f\colon [n]\to[r]$. All our lower bounds are for adaptive two-sided testers. * We prove a nearly tight lower bound for this problem in terms of $r$. The bound is $\Omega(\frac{\log r}{\log \log r})$ when $\epsilon = 1/2$. No previous satisfactory lower bound in terms of $r$ was known. * We completely characterise query complexity of this probl…

Span Programs and Quantum Algorithms for st-Connectivity and Claw Detection

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 st-connectivity that uses O(n d^{1/2}) quantum queries to the n x n adjacency matrix to decide if vertices s and t are connected, under the promise that they either are connected by a path of length at most d, or are disconnected. We also show that if T is a path, a star with two subdivided legs, or a subdivision of a claw, its presence as a subgraph in the input graph G can be detected with O(n) quantum queries to the adjacency matrix. Under the promise that G either contains T as a subgraph or does not contain T…

Kvantu dizaini: MUB un SIC-POVM

Kvantu dizaini ir simetriskas vektoru konfigurācijas daudzdimensiju telpā. Pazīstamākie no tiem ir MUBu pilnas sistēmas un SIC-POVMi. Tie tiek pielietoti kvantu stāvokļu mērīšanā (kvantu tomogrāfijā), kvantu kriptogrāfijā un citās jomās. Šie objekti veido tā saucamos kompleksos projektīvos 2-dizainus, tas ir, sasniedz vienādību Velča nevienādībā priekš k=2. To izmantojot, mēs izvedam nepieciešamu un pietiekamu nosacījumu, lai vektoru sistēma veidotu MUBu pilno sistēmu vai SIC-POVMu. Šis nosacījums der arī citiem kvantu dizainiem. Atšķirībā no iepriekšējiem kritērijiem, mūsu kritērijs izmanto tikai vektoru ortogonalitāti. Mēs ievedam homogēnas sistēmas: vektoru sistēmas, kurām šis nosacījums…

Some Algebraic Properties of Machine Poset of Infinite Words

The complexity of infinite words is considered from the point of view of a transformation with a Mealy machine that is the simplest model of a finite automaton transducer. We are mostly interested in algebraic properties of the underlying partially ordered set. Results considered with the existence of supremum, infimum, antichains, chains and density aspects are investigated.

Multi-letter reversible and quantum finite automata

The regular language (a+b)*a (the words in alphabet {a, b} having a as the last letter) is at the moment a classical example of a language not recognizable by a one-way quantum finite automaton (QFA). Up to now, there have been introduced many different models of QFAs, with increasing capabilities, but none of them can cope with this language. We introduce a new, quite simple modification of the QFA model (actually even a deterministic reversible FA model) which is able to recognize this language. We also completely characterise the set of languages recognizable by the new model FAs, by finding a "forbidden construction" whose presence or absence in the minimal deterministic (not necessaril…

Adversary Lower Bound for the k-sum Problem

We prove a tight quantum query lower bound $\Omega(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 the alphabet size is sufficiently large. This is an extended and simplified version of an earlier preprint of one of the authors arXiv:1204.5074.

On a Conjecture by Christian Choffrut

It is one of the most famous open problems to determine the minimum amount of states required by a deterministic finite automaton to distinguish a pair of strings, which was stated by Christian Choffrut more than thirty years ago. We investigate the same question for different automata models and we obtain new upper and lower bounds for some of them including alternating, ultrametric, quantum, and affine finite automata.