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.

In this note, we see first quantum algorithm, Simon's algorithm. It was used for search a string from number of input streams. Here, we enhance its search strategies for search a string into multiple sources. For it, we use n-qubits Hadamard gates for search a string into the multiple sources. Further, it enhances for search an entity into multiple databases as consider of dynamic size. Finally, single entity result generated by removes entities redundancy and cancel out opposite sign entities.

SIMON is a family of the lightweight block ciphers designed by the U.S National Security Agency in 2013 which is a classical Feistel scheme. The round function uses bitwise AND, rotation and XOR operations. This paper studies on differential distribution properties of the general SIMON-like round function F [a, b, c] (x) = (x ⋘a) ⊙(x⋘)⊕(x⋘c) It gives the relationship between the differential probability and the hamming weight of the input difference, and solves the constructing and counting issue of the corresponding input and output differences when the differential probabilities are 1/2, 1/4, 1/8, 1/16, 1/2(n−1), and also proposes a fast algorithm to compute the combined differential (α→ β)·p(α→ β) of the iterative differential characteristic with a computation complexity of O(2r n3). It provides theoretical guidance for the differential cryptanalysis and design of SIMON family.

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

In this letter, we introduce a fast and computationally efficient iterative algorithm for joint zero diagonalization of a set of complex-valued target matrices. The proposed algorithm is actually a low complexity version of FJZD algorithm, it has a computational complexity of O(K N2), where K and N are the number and dimension of the target matrices respectively. Moreover, the proposed algorithm is superior to FJZD in terms of interference to signal ratio. Simulation results demonstrate the good performance of the proposed algorithm.

Daniel Simon's 1994 discovery of an efficient quantum algorithm for finding “hidden shifts” of Z 2 n provided the first algebraic problem for which quantum computers are exponentially faster than their classical counterparts. In this article, we study the generalization of Simon's problem to arbitrary groups. Fixing a finite group G , this is the problem of recovering an involution m = ( m 1 ,…, m n ) ∈ G n from an oracle f with the property that f ( x ⋅ y ) = f ( x ) ⇔ y ∈ {1, m }. In the current parlance, this is the hidden subgroup problem (HSP) over groups of the form G n , where G is a nonabelian group of constant size, and where the hidden subgroup is either trivial or has order two. Although groups of the form G n have a simple product structure, they share important representation--theoretic properties with the symmetric groups S n , where a solution to the HSP would yield a quantum algorithm for Graph Isomorphism. In particular, solving their HSP with the so-called “standard method” requires highly entangled measurements on the tensor product of many coset states. In this article, we provide quantum algorithms with time complexity 2 O (√ n ) that recover hidden involutions m = ( m 1 ,… m n ) ∈ G n where, as in Simon's problem, each m i is either the identity or the conjugate of a known element m which satisfies κ( m ) = −κ(1) for some κ ∈ Ĝ . Our approach combines the general idea behind Kuperberg's sieve for dihedral groups with the “missing harmonic” approach of Moore and Russell. These are the first nontrivial HSP algorithms for group families that require highly entangled multiregister Fourier sampling.

In this paper, we propose a new quantum algorithm for solving the minimum searching problem. This algorithm has the same order of time and space complexities as the algorithm proposed by Dürr and Høyer, but it provides a quadratic reduction in the number of measurements. In addition to the correctness and complexity analysis of the algorithm, we present simulation results considering an NP-hard problem.

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

As it is well known, for any graph G, we have polynomial-time algorithms to get the classical connectivity κ(G) and edge-connectivity \(\lambda (G)\). However, as we have seen in the last chapter, even for some very special graphs, it is very hard to get the exact values of their generalized k-connectivity for general k. A natural question is whether there is a polynomial-time algorithm to get the parameters κ k (G) and \(\lambda _{k}(G)\). In this chapter, we study the complexity of generalized connectivity.

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

It is well-known that Shor's factorization algorithm, Simon's period-finding algorithm, and Deutsch's original XOR algorithm can all be formulated as solutions to a hidden subgroup problem. Here the salient features of the information-processing in the three algorithms are presented from a different perspective, in terms of the way in which the algorithms exploit the non-Boolean quantum logic represented by the projective geometry of Hilbert space. From this quantum logical perspective, the XOR algorithm appears directly as a special case of Simon's algorithm, and all three algorithms can be seen as exploiting the non-Boolean logic represented by the subspace structure of Hilbert space in a similar way. Essentially, a global property of a function (such as a period, or a disjunctive property) is encoded as a subspace in Hilbert space representing a quantum proposition, which can then be efficiently distinguished from alternative propositions, corresponding to alternative global properties, by a measurement (or sequence of measurements) that identifies the target proposition as the proposition represented by the subspace containing the final state produced by the algorithm.

In the field of Quantum computing, the Peter Shorgave an important algorithm known as Shor's factorization algorithm. With the existing coding it has an issue of finding order and periods finding. Search of new quantum numbers has been already on to strengthen the quantum computing. The development of quantum computer is also slow due to limited availability of simulation. In this paper, we have reported new quantum numbers using Shor's algorithm and simulation. The graphical representation of numbers are shown in this paper.

Seit der Entdeckung von effizienten Quantenalgorithmen für das Faktorisieren von ganzen Zahlen und für die Berechnung von diskreten Logarithmen durch Shor in 1994 wuchs das Interesse an Quantenalgorithmen innerhalb der theoretischen Informatik- und der Physik-Gemeinde. Überraschenderweise ist die Anzahl der Quantenalgorithmen, die bisher entdeckt wurden, vergleichsweise gering, obwohl die Anzahl der Forscher, welche an diesem Gebiet arbeiten, stark angestiegen ist. Die Aufgabe, neue Quantenalgorithmen zu entwerfen, hat sich in der Tat als extrem schwierig herausgestellt. Wir geben einen kurzen Überblick über eine Auswahl von Problemen, für welche effiziente Quantenalgorithmen bekannt sind, und beschreiben kurz die zu Grunde liegenden Ideen. Ein großes Gebiet, bei dem ein Quantenrechner allen klassischen Rechnern überlegen zu sein scheint, sind die verborgenen Untergruppenprobleme. Wir erklären deren Relevanz und geben Motivation für diese abstrakte Problemklasse.

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.

This paper focuses on algebraic attacks on the Simon family of block ciphers. We construct equation systems using multiple plaintext/ciphertext pairs, and show that many variables in the cipher states coming from different plaintexts are linearly related. A simple solving algorithm exploiting these relations is developed and extensively tested on the different Simon variants, giving efficient algebraic attacks on upi?źto 16 rounds of the largest Simon variants.

We obtain the strongest separation between quantum and classical query complexity known to date—specifically, we define a black-box problem that requires exponentially many queries in the classical bounded-error case, but can be solved exactly in the quantum case with a single query (and a polynomial number of auxiliary operations). The problem is simple to define and the quantum algorithm solving it is also simple when described in terms of certain quantum Fourier transforms (QFTs) that have natural properties with respect to the algebraic structures of finite fields. These QFTs may be of independent interest, and we also investigate generalizations of them to noncommutative finite rings.

We analyze the Ohya-Masuda quantum algorithm that solves the so-called “satisfiability” problem, which is an NP-complete problem of the complexity theory. We distinguish three steps in the algorithm, and analyze the second step, in which a coherent superposition of states (a “pure” state) transforms into an “incoherent” mixture presented by a density matrix. We show that, if “nonideal” (in analogy with “nonideal” quantum measurement), this transformation can make the algorithm to fail in some cases. On this basis we give some general notions on the physical implementation of the Ohya-Masuda algorithm.

Quantum computation is a new computing model based on fundamental quantum mechanical principle. Grover's algorithm finds the solution for a searching problem in the square root time of exhaustive search. Brassard, Hoyer, Tapp's algorithm counts the number of solutions for a searching problem. Through exploiting the two quantum algorithms, we propose a quantum algorithm for solving a new cryptography problem -- polynomial root finding problem, which could be used to design a cryptosystem. The algorithm will take O(rootM/t) steps for finding one of the t solutions to the problem, where M is the modular of the equation. The success rate of the algorithm is a constant and the cost of the algorithm depends on the calculations of modular exponentiation and the number of iterations.

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

A quantum algorithm for solving the classical NP-complete problem - the Hamilton circuit is presented. The algorithm employs the quantum SAT and the quantum search. algorithms. The algorithm is square-root faster than classical algorithm, and becomes exponentially faster than classical algorithm if nonlinear quantum mechanical computer is used.

In this paper, we analyze the effect of making equivalent transformations for the central path from \( xs=\mu e \) to \( xs=\mu v \), so we obtain a new search direction. For a full-Newton step interior-point algorithm based on this search direction, we have the best known complexity bound is \( \mathrm{ O}(\sqrt{\mathrm{ n}}\ \mathrm{ lon}\varepsilon /\mathrm{ n}) \). Which coincides with the best known iteration bound for feasible interior-point method(IPM). Finally, we concentrate on its numerical implementation where a strategy on the update barrier parameter is made for its numerical performances.

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

Delay-constraint minimum cost multicast tree problem is a classical combinatorial optimization problem. It has been proved to be a NP-complete problem. Many algorithms have been proposed to solve the problem. This paper proposed a tree-based quantum optimization algorithm for the multicast tree problem. In this algorithm, the probability amplitude of each side was stored in a quantum, and the quantum evolved by quantum gate, each quantum moved in the direction of better solution. The evolutionary process merged the trees rather than paths directly to accelerate the convergence and improved the quality of solutions. Simulation results showed that the algorithm in this paper performed well at searching and convergence speed.

This paper investigates the computability of mathematical relations in a quantum query model. The important task in complexity theory is to find examples with a large gap between classical and quantum algorithm complexity of the same computational problem. We present new results in quantum query algorithm design that allow achieving a large separation between classical and quantum query complexity of a specific relation. We demonstrate an example where quantum query algorithm for a finite relation needs more than two times fewer queries than the best possible classical analogue. We also show that relation can be extended to infinite family of relations with an input of general size N.

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 describe a new polynomial-time quantum algorithm that solves the hidden subgroup problem (HSP) for a special class of metacyclic groups, namely $\mathbb{Z}_{p} \rtimes \mathbb{Z}_{q^s}$, with q |(p−1) and p/q=poly(log p), where p, q are any odd prime numbers and s is any positive integer. This solution generalizes previous algorithms presented in the literature. In a more general setting, without imposing a relation between p and q, we obtain a quantum algorithm with time and query complexity $2^{O(\sqrt{\log p})}$. In any case, those results improve the classical algorithm, which needs ${\Omega}(\sqrt{p})$ queries.

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.

Superposition principle of quantum theory is introduced in this paper. The genetic algorithm has been described by quantum superposition theory. It implies genetic algorithm is essentially a kind of quantum algorithm in the classical computer on the reduced order to achieve. It through genetic manipulation to input superposition states data into classical computer. In the evolutionary process, a lot of implicit modes have been measured, so as to realize the parallel search and processing in the model space. It is implicit parallelism of genetic algorithm. The quantum theory can also be used to analyze the problem?s computational complexity. Quantum superposition theory and entropy are used to get the problem?s lower bound of computational complexity. Using this method the problem?s lower bound of computational complexity is only decided by itself. It is independent of the algorithm?s details.

In this paper, a new algorithm to simplify the Sphere-decoding of V-BLAST architecture is deduced. The system bit error ratio (BER) and complexity are simulated to compare the performance when sphere-decoding algorithm is used with the performance when classical sphere-decoding algorithm is used. According to simulation, the complexity of the modified sphere-decoding algorithm is much lower than the complexity of classical sphere-decoding.

We consider the problem of generalizing some quantum algorithms so that they will work on input domains whose cardinalities are not necessarily powers of two. When analyzing the algorithms we assume that generating superpositions of arbitrary subsets of basis states whose cardinalities are not necessarily powers of two perfectly is possible. We have taken Ballhysa's model as a template and have extended it to Chi, Kim and Lee's generalizations of the Deutsch-Jozsa algorithm and to Simon's algorithm. With perfectly equal superpositions of input sets of arbitrary size, Chi, Kim and Lee's generalized Deutsch-Jozsa algorithms, both for evenly-distributed and evenly-balanced functions, worked with one-sided error property. For Simon's algorithm the success probability of the generalized algorithm is the same as that of the original for input sets of arbitrary cardinalities with equiprobable superpositions, since the property that the measured strings are all those which have dot product zero with the string we search, for the case where the function is 2-to-1, is not lost.

This paper presents a principle of minimum complexity in evolving systems. Minimum complexity is supported by results and observations from genetic algorithm research and information complexity theory. This paper introduces minimum complexity and presents quantitative evidence for minimum complexity in messy genetic evolution. There also appears to be a strong correlation with our theory and what is observed in biological genetics.