Search

Квалiфiкацiйна робота мiстить: 92 сторiнки, 10 рисункiв, 3 таблицi, 77 джерел. У роботi вперше проводиться квантовий криптоаналiз малоресурсного симетричного блокового шифру «Кипарис», за результатами якого на його трираундову схему шифрування побудована полiномiальна атака розрiзнення випадкового тексту вiд шифротексту, а також субекспоненцiйна атака вiдновлення ключiв на четвертому та п’ятому раундах. Окрiм цього, отриманi оцiнки складностi проведення атак для повної кiлькостi раундiв у квантовiй моделi обчислень. Також доведена стiйкiсть до ротацiйного криптоаналiзу версiї «Кипарис-256» та отримана ймовiрнiсть ротацiї для «Кипарис-512», яка майже не вiдрiзняється вiд ймовiрностi випадкової перестановки. У роботi доведена вразливiсть узагальненої схеми Фейстеля типу III у квантовiй моделi обчислень, де кiлькiсть раундiв збiгається з кiлькiстю частин, на якi розбивається вiдкритий текст на входi у схему шифрування. Метою роботи є дослiдження стiйкостi малоресурсного симетричного блокового шифру «Кипарис» до квантового та ротацiйного криптоаналiзiв. Об’єктом дослiдження є iнформацiйнi процеси в системах захисту iнформацiї. Предметом дослiдження є стiйкiсть до квантового та ротацiйного криптоаналiзiв малоресурсного симетричного блокового шифру «Кипарис». The thesis contains: 92 pages, 10 figures, 3 tables, 77 sources. In this thesis, for the first time, a quantum cryptanalysis of the lightweight symmetric block cipher «Cypress» is introduced. According to the results of which a polynomial attack of distinguishing a random text from a ciphertext was carried out againts its three-round encryption scheme, and a subexponential key-recovery attack againts its fourth and fifth rounds. Furthermore in this thesis were obtained estimates the complexity of attacks for the total number of rounds in the quantum adversary model. Proven resistance to rotational attacks for version «Cypress-256». The obtained probability of rotational cryptanalysis against «Cypress-512» is close to the probability of a random permutation. It is also proven that the type III Generalized Feistel Scheme is not immune against quantum computing attacks if the number of rounds coincides with the number of parts into which the plaintext is divided at the entrance to the encryption scheme. The purpose of the thesis is investigate the resistance of the lightweight symmetric block cipher «Cypress» to quantum and rotational cryptanalysis. The research object is information processes in information security systems. The research subject is resistance to quantum and rotational cryptanalysis of lightweight symmetric block cipher «Cypress».

Simon's problem plays an important role in the history of quantum algorithms, as it inspired Shor to discover the celebrated quantum algorithm solving integer factorization in polynomial time. Besides, the quantum algorithm for Simon's problem has been recently applied to break symmetric cryptosystems. Generalized Simon's problem, denoted by GSP ( p , n , k ) , is a natural extension of Simon's problem: Given a function f : Z p n → X where X is a finite set and the promise that for any x , y ∈ Z p n , f ( x ) = f ( y ) iff x − y ∈ S for a subgroup S ≤ Z p n of rank k n , the goal is to find S. In this paper we consider the query complexity of the problem, that is, the minimum number of queries to f required to find S. First, it is not difficult to design a quantum algorithm solving the above problem with query complexity of O ( n − k ) . However, so far it is not clear what is the classical query complexity of the problem, and revealing this complexity is necessary for clarifying the computational power gap between quantum and classical computing on the problem. To tackle this problem, we prove that any classical (deterministic or randomized) algorithm for GSP ( p , n , k ) has to query at least Ω ( max ⁡ { k , p n − k } ) values and any classical nonadaptive deterministic algorithm for GSP ( p , n , k ) has to query at least Ω ( max ⁡ { k , k ⋅ p n − k } ) values. Hence, we clearly show the classical computing model is less powerful than the quantum counterpart, in terms of query complexity for the generalized Simon's problem. Moreover, we obtain an upper bound O ( max ⁡ { k , k ⋅ p n − k } ) on the classical deterministic query complexity of GSP ( p , n , k ) , by devising a subtle classical algorithm based on group theory and the divide-and-conquer approach. Therefore, we have an almost full characterization of the classical deterministic query complexity of the generalized Simon's problem.

Routing in wireless multihop networks (WMHNs) relies on a delicate balance of diverse and often conflicting parameters, when aiming for maximizing the WMHN performance. Classified as a non-deterministic polynomial-time hard problem, routing in WMHNs requires sophisticated methods. As a benefit of observing numerous variables in parallel, quantum computing offers a promising range of algorithms for complexity reduction by exploiting the principle of quantum parallelism (QP), while achieving the optimum full-search-based performance. In fact, the so-called non-dominated quantum optimization (NDQO) algorithm has been proposed for addressing the multiobjective routing problem with the goal of achieving a near-optimal performance, while imposing a complexity of the order of $O(N)$ and $O(N\sqrt {N})$ in the best and worst case scenarios, respectively. However, as the number of nodes in the WMHN increases, the total number of routes increases exponentially, making its employment infeasible despite the complexity reduction offered. Therefore, we propose a novel optimal quantum-assisted algorithm, namely, the non-dominated quantum iterative optimization (NDQIO) algorithm, which exploits the synergy between the hardware and the QP for the sake of achieving a further complexity reduction, which is on the order of $O(\sqrt {N})$ and $O(N\sqrt {N})$ in the best and worst case scenarios, respectively. In addition, we provide simulation results for demonstrating that our NDQIO algorithm achieves an average complexity reduction of almost an order of magnitude compared with the near-optimal NDQO algorithm, while having the same order of power consumption.

We present a quantum algorithm for computing the Ramsey numbers whose computational complexity grows super-exponentially with the number of vertices of a graph on a classical computer. The problem is mapped to a decision problem on a quantum computer, a probe qubit is coupled to a register that represents the problem and detects the energy levels of the problem Hamiltonian. The decision problem is solved by determining whether the probe qubit exhibits resonance dynamics. The algorithm shows a quadratic speedup over its classical counterparts, and the degenerate ground state problem in the adiabatic quantum evolution algorithm for this problem is avoided., Comment: 10 pages, 3 figures

It has recently been shown that quantum computers can efficiently solve the Heisenberg hidden subgroup problem, a problem whose classical query complexity is exponential. This quantum algorithm was discovered within the framework of using pretty-good measurements for obtaining optimal measurements in the hidden subgroup problem. Here we show how to solve the Heisenberg hidden subgroup problem using arguments based instead on the symmetry of certain hidden subgroup states. The symmetry we consider leads naturally to a unitary transform known as the Clebsch-Gordan transform over the Heisenberg group. This gives a new representation theoretic explanation for the pretty-good measurement derived algorithm for efficiently solving the Heisenberg hidden subgroup problem and provides evidence that Clebsch-Gordan transforms over finite groups are a new primitive in quantum algorithm design., Comment: 30 pages, uses qic.sty

Simon's problem is one of the most important problems demonstrating the power of quantum computers, which achieves a large separation between quantum and classical query complexities. However, Simon's discussion on his problem was limited to bounded-error setting, which means his algorithm can not always get the correct answer. Exact quantum algorithms for Simon's problem have also been proposed, which deterministically solve the problem with O(n) queries. Also the quantum lower bound \Omega(n) for Simon's problem is known. Although these algorithms are either complicated or specialized, their results give an O(n) versus \Omega(\sqrt{2^{n}}) separation in exact query complexities for Simon's problem (\Omega(\sqrt{2^{n}}) is the lower bound for classical probabilistic algorithms), but it has not been proved whether this separation is optimal. In this paper, we propose another exact quantum algorithm for solving Simon's problem with O(n) queries, which is simple, concrete and does not rely on special query oracles. Our algorithm combines Simon's algorithm with the quantum amplitude amplification technique to ensure its determinism. In particular, we show that Simon's problem can be solved by a classical deterministic algorithm with O(\sqrt{2^{n}}) queries (as we are aware, there were no classical deterministic algorithms for solving Simon's problem with O(\sqrt{2^{n}}) queries). Combining some previous results, we obtain the optimal separation in exact query complexities for Simon's problem: \Theta({n}) versus \Theta({\sqrt{2^{n}}})., Comment: 16 pages; some minor changes have been made; comments are welcome

We deal with the problem of finding a maximum of a function from the Holder class on a quantum computer. We show matching lower and upper bounds on the complexity of this problem. We prove upper bounds by constructing an algorithm that uses a pre-existing quantum algorithm for finding maximum of a discrete sequence. To prove lower bounds we use results for finding the logical OR of sequence of bits. We show that quantum computation yields a quadratic speed-up over deterministic and randomized algorithms.

We perform a mathematical analysis of the classical computational complexity of two genuine quantum-mechanical problems, which are inspired in the calculation of the expected magnetizations and the entanglement between subsystems for a quantum spin system. These problems, which we respectively call SES and SESSP, are specified in terms of pure slightly-entangled quantum states of n qubits, and rigorous mathematical proofs that they belong to the NP-Complete complexity class are presented. Both SES and SESSP are, therefore, computationally equivalent to the relevant 3-SAT problem, for which an efficient algorithm is yet to be discovered., 5 pages

This paper presents a fast algorithm for solving the n-queens problem. The basic idea of this algorithm is to use pre-computed solutions in 75% of the cases, while the remaining cases are solved by calling the Sosic's algorithm. The novelty of this algorithm is in the observation that these pre-computable cases exhibit a modular nature. In addition, the pre-computed solutions run 100 times faster than Sosic's algorithm in most cases.

We present a quantum algorithm which identifies with certainty a hidden subgroup of an arbitrary finite group G in only a polynomial (in log |G|) number of calls to the oracle. This is exponentially better than the best classical algorithm. However our quantum algorithm requires exponential time, as in the classical case. Our algorithm utilizes a new technique for constructing error-free algorithms for non-decision problems on quantum computers., To appear in Information Processing Letters (IPL)

An algorithm complexity, or its efficiency, meaning its time of evaluation is the focus of primary care in algorithmic problems solving. Raising the used memory may reduce the complexity of algorithm drastically. We present an example of two algorithms on finite set, where change the approach to the same problem and introduction a memory array allows decrease the complexity of the algorithm from the order O(n2) up to the order O(n).

The hidden subgroup problem is the foundation of many quantum algorithms. An efficient solution is known for the problem over abelian groups, employed by both Simon's algorithm and Shor's factoring and discrete log algorithms. The nonabelian case, however, remains open; an efficient solution would give rise to an efficient quantum algorithm for graph isomorphism. We fully analyze a natural generalization of the algorithm for the abelian case to the nonabelian case and show that the algorithm determines the normal core of a hidden subgroup: in particular, normal subgroups can be determined. We show, however, that this immediate generalization of the abelian algorithm does not efficiently solve graph isomorphism.

We report an experimental demonstration of a one-way implementation of a quantum algorithm solving Simon's Problem - a black box period-finding problem which has an exponential gap between the classical and quantum runtime. Using an all-optical setup and modifying the bases of single-qubit measurements on a five-qubit cluster state, key representative functions of the logical two-qubit version's black box can be queried and solved. To the best of our knowledge, this work represents the first experimental realization of the quantum algorithm solving Simon's Problem. The experimental results are in excellent agreement with the theoretical model, demonstrating the successful performance of the algorithm. With a view to scaling up to larger numbers of qubits, we analyze the resource requirements for an n-qubit version. This work helps highlight how one-way quantum computing provides a practical route to experimentally investigating the quantum-classical gap in the query complexity model., 9 pages, 5 figures

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 previously known algorithm by Magniez et al.

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., Comment: 19 pages, 2 figures, major changes

We determine the complexity of several constraint satisfaction problems using the quantum adiabatic algorithm in its simplest implementation. We do so by studying the size dependence of the gap to the first excited state of "typical" instances. We find that at large sizes N, the complexity increases exponentially for all models that we study. We also compare our results against the complexity of the analogous classical algorithm WalkSAT and show that the harder the problem is for the classical algorithm the harder it is also for the quantum adiabatic algorithm., 9 pages, 7 figures

A class of problems is described which can be solved more efficiently by quantum computation than by any classical or stochastic method. The quantum computation solves the problem with certainty in exponentially less time than any classical deterministic computation.

We present quantum query and time complexity bounds for group testing problems. For a set S and a binary operation on S, we consider the decision problem whether a groupoid, semigroup or quasi-group is a group. Our quantum algorithms for these problems improve the best known classical complexity bounds. We also present upper and lower bounds for testing associativity, distributivity and commutativity.

We propose the use of a quantum algorithm to deal with the problem of searching with errors in the framework of two-person games. Specifically, we present a solution to the Ulam's problem that polynomially reduces its query complexity and makes it independent from the dimension of the search space., 4 pages, RevTeX file, revised version

We consider the problem of testing the commutativity of a black-box group specified by its k generators. The complexity (in terms of k) of this problem was first considered by Pak, who gave a randomized algorithm involving O(k) group operations. We construct a quite optimal quantum algorithm for this problem whose complexity is in O(k2/3). The algorithm uses and highlights the power of the quantization method of Szegedy. For the lower bound of Ω(k2/3), we introduce a new technique of reduction for quantum query complexity. Along the way, we prove the optimality of the algorithm of Pak for the randomized model.

Simon in his FOCS’94 paper was the first to show an exponential gap between classical and quantum computation. The problem he dealt with is now part of a well-studied class of problems, the hidden subgroup problems. We study Simon’s problem from the point of view of quantum query complexity and give here a first nontrivial lower bound on the query complexity of a hidden subgroup problem, namely Simon’s problem. More generally, we give a lower bound which is optimal up to a constant factor for any Abelian group.

We examine the number T of queries that a quantum network requires to compute several Boolean functions on {0,1}^N in the black-box model. We show that, in the black-box model, the exponential quantum speed-up obtained for partial functions (i.e. problems involving a promise on the input) by Deutsch and Jozsa and by Simon cannot be obtained for any total function: if a quantum algorithm computes some total Boolean function f with bounded-error using T black-box queries then there is a classical deterministic algorithm that computes f exactly with O(T^6) queries. We also give asymptotically tight characterizations of T for all symmetric f in the exact, zero-error, and bounded-error settings. Finally, we give new precise bounds for AND, OR, and PARITY. Our results are a quantum extension of the so-called polynomial method, which has been successfully applied in classical complexity theory, and also a quantum extension of results by Nisan about a polynomial relationship between randomized and deterministic decision tree complexity., 10 pages, LaTeX, no figures, final version to appear in FOCS'98

Consider a Boolean function $\chi: X \to \{0,1\}$ that partitions set $X$ between its good and bad elements, where $x$ is good if $\chi(x)=1$ and bad otherwise. Consider also a quantum algorithm $\mathcal A$ such that $A |0\rangle= \sum_{x\in X} \alpha_x |x\rangle$ is a quantum superposition of the elements of $X$, and let $a$ denote the probability that a good element is produced if $A |0\rangle$ is measured. If we repeat the process of running $A$, measuring the output, and using $\chi$ to check the validity of the result, we shall expect to repeat $1/a$ times on the average before a solution is found. *Amplitude amplification* is a process that allows to find a good $x$ after an expected number of applications of $A$ and its inverse which is proportional to $1/\sqrt{a}$, assuming algorithm $A$ makes no measurements. This is a generalization of Grover's searching algorithm in which $A$ was restricted to producing an equal superposition of all members of $X$ and we had a promise that a single $x$ existed such that $\chi(x)=1$. Our algorithm works whether or not the value of $a$ is known ahead of time. In case the value of $a$ is known, we can find a good $x$ after a number of applications of $A$ and its inverse which is proportional to $1/\sqrt{a}$ even in the worst case. We show that this quadratic speedup can also be obtained for a large family of search problems for which good classical heuristics exist. Finally, as our main result, we combine ideas from Grover's and Shor's quantum algorithms to perform amplitude estimation, a process that allows to estimate the value of $a$. We apply amplitude estimation to the problem of *approximate counting*, in which we wish to estimate the number of $x\in X$ such that $\chi(x)=1$. We obtain optimal quantum algorithms in a variety of settings., Comment: 32 pages, no figures

We compare classical and quantum query complexities of total Boolean functions. It is known that for worst-case complexity, the gap between quantum and classical can be at most polynomial [3]. We show that for average-case complexity under the uniform distribution, quantum algorithms can be exponentially faster than classical algorithms. Under non-uniform distributions the gap can even be super-exponential. We also prove some general bounds for average-case complexity and show that the average-case quantum complexity of MAJORITY under the uniform distribution is nearly quadratically better than the classical complexity.

We compare classical and quantum query complexities of total Boolean functions. It is known that for worst-case complexity, the gap between quantum and classical can be at most polynomial. We show that for average-case complexity under the uniform distribution, quantum algorithms can be exponentially faster than classical algorithms. Under non-uniform distributions the gap can even be super-exponential. We also prove some general bounds for average-case complexity and show that the average-case quantum complexity of MAJORITY under the uniform distribution is nearly quadratically better than the classical complexity., Comment: 14 pages, LaTeX. Some parts rewritten. This version to appear in the Journal of Physics A

Let H = −Δ + V, where V is a multiplication operator by a real-valued function V(x) on Rn which is uniformly Hölder continuous and (1 + ¦x¦2)ϱ2 V(x) ∈ L∞(Rn) for some ϱ > 4. The relationship between existence of positive solutions, with growth conditions, of Hg = 0 and asymptotic behaviors as t → ∞ of e−th is established. Using it B. Simon's problem for H on R2 is solved.

We introduce a quantum lambda calculus inspired by Lafont’s Soft Linear Logic and capturing the polynomial quantum complexity classes EQP, BQP and ZQP. The calculus is based on the “classical control and quantum data” paradigm. This is the first example of a formal system capturing quantum complexity classes in the spirit of implicit computational complexity — it is machine-free and no explicit bound (e.g., polynomials) appears in its syntax.

We investigate the power of quantum computers when they are required to return an answer that is guaranteed to be correct after a time that is upper-bounded by a polynomial in the worst case. We show that a natural generalization of Simon's problem can be solved in this way, whereas previous algorithms required quantum polynomial time in the expected sense only, without upper bounds on the worst-case running time. This is achieved by generalizing both Simon's and Grover's algorithms and combining them in a novel way. It follows that there is a decision problem that can be solved in exact quantum polynomial time, which would require expected exponential time on any classical bounded-error probabilistic computer if the data is supplied as a black box.