Search

We use the mapping between two computation frameworks , Adiabatic Grover Search (AGS) and Adiabatic Quantum Computing (AQC), to translate the Grover search algorithm into the AQC regime. We then apply Trotterization on the schedule-dependent Hamiltonian of AGS to obtain the values of variational parameters in the Quantum Approximate Optimization Algorithm (QAOA) framework. The goal is to carry the optimal behavior of Grover search algorithm into the QAOA framework without the iterative machine learning processes., Comment: 5 pages, 2 figures, 1 table. arXiv admin note: substantial text overlap with arXiv:2204.09830

We designed and implemented an efficient tough random symmetric 3-SAT generator and propose two deterministic algorithms that efficiently generate 3-SAT instances with a unique solution. We quantify the first algorithms hardness in terms of CPU time, numbers of restarts, decisions, propagations, conflicts and conflicted literals that occur when a solver tries to solve 3-SAT instances. In this experiment, the clause variable ratio was chosen to be around the conventional critical phase transition number 4.24. The experiment shows that instances generated by our generator are significantly harder than instances generated by the Tough K-SAT generator. The two deterministic algorithms generate 3-SAT instances with the number of clauses scaling as 4n, where n is the number of variables, and (n+6), respectively. By combining these two algorithms along with a simple padding algorithm, we prove a hybrid algorithm that can generate n-variable instances with the number of clauses that scale between (n+6) and 7n(n-1)(n-2). Overall, all proposed SAT generators seek to explore unique difficult to solve SAT problems.

The adjacency matrices of graphs provide the foundation for constructing the Hamiltonians of Continuous-Time Quantum Walks (CTQWs). Various classes of graphs have been identified to be highly reducible and the reduced Hamiltonian preserves the dynamics of the original system. This makes the CTQW implementation feasible in the near term for search problems of large size. Highly reducible Hamiltonians are desirable because existing quantum devices are of limited size in terms of the number of qubits. In this work, we review the recent developments of dimensionality reduction and coupling factor value finding techniques. The CTQWs based on a reduced Hamiltonian can search optimally when the correctly calculated coupling factor is used. We list identified highly reducible graphs and include their optimality proofs when correct coupling factors are used. In addition, we discuss the recent developments on Lackadaisical Quantum Walkers (LQW) (a type of coin-based discrete-time quantum walk) for one- and two-dimensional spatial search. The optimal lower upper bound remains open in one- and two-dimensional Discrete-Time Quantum Walk.

We propose a quantum assisted secure distributed ledger system that is client centric and polyvalent. The multiple attribute lock encryption (MALE) provides asymmetric key encryption to protect the data. The keys are of high randomness as they are generated via the simulation of a quantum walk. Quantum random walkers on a circle structure have been shown to be an efficient pseudo-random number generator. On top of the quantum random walker, we apply the quantum key distribution (QKD) protocol to avoid the double spending problem and to serve as a seed provider for the quantum walk. We further design the key chain update protocol with the help of MALE mechanism after each data access. Both QKD and quantum random walker can be efficiently simulated with current classical computation and near-term quantum technologies. Potential applications of proposed work in smart-city context are briefly discussed as well.

We designed and implemented an efficient tough random symmetric 3-SAT generator. We quantify the hardness in terms of CPU time, numbers of restarts, decisions, propagations, conflicts and conflicted literals that occur when a solver tries to solve 3-SAT instances. In this experiment, the clause variable ratio was chosen to be around the conventional critical phase transition number 4.24. The experiment shows that instances generated by our generator are significantly harder than instances generated by the Tough K-SAT generator. The difference in hardness between two SAT instance generators exponentiates as the number of Boolean variables used increases.

The design of an anomaly/outlier/novelty detection system, for a given application, fundamentally requires, on the one hand, the construction of a numerical score from available datasets, to rank data points as to their closeness to being normal, and on the other hand, the statement of a policy, based on the score, for declaring anomalies. The task of designing an anomaly score is challenging because the probability distribution of what may be considered normal cannot always be assumed a priori, especially in dynamic environments like monitoring a computing system. Hence, most anomaly scores in use presently are based on some form of a direct distance between the data points. The use of the Kullback-Leibler (KL) divergence, for probability distributions, along with a windowing scheme, is explored in this paper, for the design of anomaly scores. Distributions are built from the frequencies of a metric in a given time window. For context, KL is used to compare the distribution of the current window with that of a linear combination of several preceding windows. Ensemble-like scores may be built by using the method on independent metrics. Experiments are conducted to test the proposed method on a University of Victoria dataset and a synthetic dataset.

For decentralised cryptocurrency systems, it is important to provide users an efficient network. One performance bottleneck is the latency issue. To address this issue, we provide four protocols to utilise the resources based on the traffic in the network to alleviate the latency in the network. To facilitate the verification process, we discuss three variant injection protocols: Periodic Injection of Transaction via Evaluation Corridor (PITEC), Probabilistic Injection of Transactions (PIT) and Adaptive Semi-synchronous Transaction Inject (ASTI). The injection protocols are variants based on the given assumptions of the network. The goal is to provide dynamic injection of unverified transactions to enhance the performance of the network. The Adaptive Policy Optimisation (APO) protocols aim at optimising a cryptocurrency system's own house policy. The house policy optimisation is translated into a 0/1 knapsack problem. The APO protocol is a fully polynomial time approximation scheme for the decentralised ledger system.

Systematic dimensionality reduction allows for the optimization of quantum search and transport problems on particular graphs. In the past, the Lanczos Algorithm has been used to perform systematic dimensionality reduction on matrices of graphs including the Complete Graph (CG), the CG with symmetry broken, and Complete Multipartite Graphs (CMPGs), including the Complete Bipartite Graph (CBG). We focus on expanding the scope of these reductions to the CBG with symmetry broken in order to allow the optimization of Quantum Walks on this type of graph.We show that similarly to the CG, the Lanczos Algorithm can be expanded to the CBG with broken symmetry, which has k random edges removed with the constraints that no more than one edge per node is removed and that no edges that connect to the solution node are removed. Unlike the CG with broken edges, which, after reduction, has 3 types of nodes and a resulting 3×3 matrix, the CBG with broken edges reduces to a graph with 5 types of nodes, resulting in a reduction from an NxN matrix to a 5×5 matrix. From these results, it may be further explored whether or not the more general CMPG reduction may also be expanded by breaking the graph’s symmetry, and if so, how the dimensions of the reduced matrices will be affected as the number of partitions grows.

We utilize dimensionality reduction to model and simulate continuous time quantum walks on a multi-partite graph, verifying that they produce a quadratic speedup over classical walks. We also discuss the applicability of dimensionality reduction as a modelling tool to experiments run on quantum hardware.

In a recent work by Novo et al. (Sci. Rep. \(\mathbf 5\), 13304, 2015), the invariant subspace method was applied to the study of continuous-time quantum walk (CTQW). In this work, we adopt the aforementioned method to investigate the optimality of a perturbed quantum walk search of a marked element in a noisy environment on various graphs. We formulate the necessary condition of the noise distribution in the system such that the invariant subspace method remains effective and efficient. Based on the noise, we further formulate how to set the appropriate coupling factor to preserve the optimality of the quantum walker. Thus, a quantum walker based on an N by N Hamiltonian can be efficiently implemented using the near-term quantum technology.

To keep a cryptocurrency system at its optimal performance, it is necessary to utilize the resources and avoid latency in its network. To achieve this goal, dynamically and efficiently injecting the unverified transactions to enable synchronicity based on the current system configuration and the traffic of the network is crucial. To meet this need, we design the pulsed transaction injection parameterization (PTIP) protocol to provide a preliminary dynamic injection mechanism. To further assist the network to achieve its subgoals based on various house policies (such as maximal revenue to the network or maximum throughput of the system), we turn the house policy based optimization into a 0/1 knapsack problem. To efficiently solve these NP-hard problems, we adapt and improve a fully polynomial time approximation scheme (FPTAS) and dynamic programming as components in our approximate optimization algorithm.

Distributed ledger technologies have a central problem that involves the latency. When transactions are to be accepted in the ledger, latency is incurred due to transaction processing and verification. For efficient systems, high latency should be avoided for the governance of the ledger. To help reduce latency, we offer a distributed ledger architecture, Tango, that mimics the Iota-tangle design as articulated by Popov [1] in his seminal paper. We introduce a semi-synchronous transaction entry protocol layer to avoid asynchronism in the system since an asynchronous system has a high latency. We further model periodic pulsed injections into the evaluation layer from the entry layer to regulate the performance of the system.

A central problem with distributed ledger technologies involves the latency that must be incurred in processing and verifying transactions to be accepted as permanent records in the ledger. In many applications, high latency is simply not a tolerable aspect of the governance of the ledger. To help reduce latency, we first propose a theoretical pulsed injection protocol then apply innovative inventory theory onto the unverified transactions in the system. To utilize a probabilistic model for the pulsed injection of transactions, we calibrate the optimum pulsed transaction injection batch size to ensure equilibrium and optimal performance of the system.

A central problem with distributed ledger technologies involves the latency that must be incurred in processing and verifying transactions to be accepted as permanent records in the ledger. In many applications, high latency is simply not a tolerable aspect of the governance of the ledger. To help reduce latency, we offer a distributed ledger architecture, Tango, that mimics the Iota-tangle design as articulated by Popov [1] in his seminal paper. A main idea is the introduction of a semi-synchronous transaction entry protocol layer. We model periodic pulsed injections into the evaluation layer from the entry layer.

In this article we assess a novel quantum computation paradigm based on the resonant transition (RT) phenomenon commonly associated with atomic and molecular systems. We thoroughly analyze the intimate connections between the RT-based quantum computation and the well-established adiabatic quantum computation (AQC). Both quantum computing frameworks encode solutions to computational problems in the spectral properties of a Hamiltonian and rely on the quantum dynamics to obtain the desired output state. We discuss how one can adapt any adiabatic quantum algorithm to a corresponding RT version and the two approaches are limited by different aspects of Hamiltonians' spectra. The RT approach provides a compelling alternative to the AQC under various circumstances. To better illustrate the usefulness of the novel framework, we analyze the time complexity of an algorithm for 3-SAT problems and discuss straightforward methods to fine tune its efficiency.

In a recent work by Novo et al. (Sci. Rep. 5, 13304, 2015), the invariant subspace method was applied to the study of continuous-time quantum walk (CTQW). In this work, we adopt the aforementioned method to investigate the optimality of a perturbed quantum walk search of a marked element in a noisy environment on various graphs. We formulate the necessary condition of the noise distribution in the system such that the invariant subspace method remains effective and efficient. Based on the noise, we further formulate how to set the appropriate coupling factor to preserve the optimality of the quantum walker.

Quantum Phase Estimation (QPE) is one of the key techniques used in quantum computation to design quantum algorithms which can be exponentially faster than classical algorithms. Intuitively, QPE allows quantum algorithms to find the hidden structure in certain kinds of problems. In particular, Shor's well-known algorithm for factoring the product of two primes uses QPE. Simulation algorithms, such as Ground State Estimation (GSE) for quantum chemistry, also use QPE. Unfortunately, QPE can be computationally expensive, either requiring many trials of the computation (repetitions) or many small rotation operations on quantum bits. Selecting an efficient QPE approach requires detailed characterizations of the trade- offs and overheads of these options. In this paper, we explore three different algorithms that trade off trials versus rotations. We perform a detailed characterization of their behavior on two important quantum algorithms (Shor's and GSE). We also develop an analytical model that characterizes the behavior of a range of algorithms in this tradeoff space. TABLE I: Comparison of three QPE Methods, with the ide- alized assumption of perfect rotation precision. (With more realistic imperfect rotation precisions, AQFT will have a non- zero number of trials since it uses repeated trials to regain precision.) ACPA is a middle ground between KHT and AQFT in terms of the number of rotations and trials involved.

We investigate the cost of three phase estimation procedures that require only constant-precision phase shift operators. The cost is in terms of the number of elementary gates, not just the number of measurements. Faster phase estimation requires the minimal number of measurements with a \log * factor of reduction when the required precision n is large. The arbitrary constant-precision approach (ACPA) requires the minimal number of elementary gates with a minimal factor of 14 of reduction in comparison to Kitaev's approach. The reduction factor increases as the precision gets higher in ACPA. Kitaev's approach is with a reduction factor of 14 in comparison to the faster phase estimation in terms of elementary gate counts., Comment: 12 pages

The hitting time is the required minimum time for a Markov chain-based walk (classical or quantum) to reach a target state in the state space. We investigate the effect of the perturbation on the hitting time of a quantum walk. We obtain an upper bound for the perturbed quantum walk hitting time by applying Szegedy's work and the perturbation bounds with Weyl's perturbation theorem on classical matrix. Based on the definition of quantum hitting time given in MNRS algorithm, we further compute the delayed perturbed hitting time (DPHT) and delayed perturbed quantum hitting time (DPQHT). We show that the upper bound for DPQHT is actually greater than the difference between the square root of the upper bound for a perturbed random walk and the square root of the lower bound for a random walk., 9 pages

While Quantum phase estimation (QPE) is at the core of many quantum algorithms known to date, its physical implementation (algorithms based on quantum Fourier transform (QFT)) is highly constrained by the requirement of high-precision controlled phase shift operators, which remain difficult to realize. In this paper, we introduce an alternative approach to approximately implement QPE with arbitrary constant-precision controlled phase shift operators. The new quantum algorithm bridges the gap between QPE algorithms based on QFT and Kitaev's original approach. For approximating the eigenphase precise to the nth bit, Kitaev's original approach does not require any controlled phase shift operator. In contrast, QPE algorithms based on QFT or approximate QFT require controlled phase shift operators with precision of at least Pi/2n. The new approach fills the gap and requires only arbitrary constant-precision controlled phase shift operators. From a physical implementation viewpoint, the new algorithm outperforms Kitaev's approach., Comment: 14 pages, 6 figures and 1 table

We achieve a quantum speed-up of fully polynomial randomized approximation schemes (FPRAS) for estimating partition functions that combine simulated annealing with the Monte-Carlo Markov Chain method and use non-adaptive cooling schedules. The improvement in time complexity is twofold: a quadratic reduction with respect to the spectral gap of the underlying Markov chains and a quadratic reduction with respect to the parameter characterizing the desired accuracy of the estimate output by the FPRAS. Both reductions are intimately related and cannot be achieved separately. First, we use Grover’s fixed point search, quantum walks and phase estimation to efficiently prepare approximate coherent encodings of stationary distributions of the Markov chains. The speed-up we obtain in this way is due to the quadratic relation between the spectral and phase gaps of classical and quantum walks. Second, we generalize the method of quantum counting, showing how to estimate expected values of quantum observables. Using this method instead of classical sampling, we obtain the speed-up with respect to accuracy.

Due to the great difficulty in scalability, quantum computers are limited in the number of qubits during the early stages of the quantum computing regime. In addition to the required qubits for storing the corresponding eigenvector, suppose we have additional k qubits available. Given such a constraint k, we propose an approach for the phase estimation for an eigenphase of exactly n-bit precision. This approach adopts the standard recursive circuit for quantum Fourier transform (QFT) and adopts classical bits to implement such a task. Our algorithm has the complexity of O(n \log k), instead of O(n^2) in the conventional QFT, in terms of the total invocation of rotation gates. We also design a scheme to implement the factorization algorithm by using k available qubits via either the continued fractions approach or the simultaneous diophantine approximation., 11 pages, 4 figures

We present an efficient general method for realizing a quantum walk operator corresponding to an arbitrary sparse classical random walk. Our approach is based on Grover and Rudolph's method for preparing coherent versions of efficiently integrable probability distributions. This method is intended for use in quantum walk algorithms with polynomial speedups, whose complexity is usually measured in terms of how many times we have to apply a step of a quantum walk, compared to the number of necessary classical Markov chain steps. We consider a finer notion of complexity including the number of elementary gates it takes to implement each step of the quantum walk with some desired accuracy. The difference in complexity for various implementation approaches is that our method scales linearly in the sparsity parameter and poly-logarithmically with the inverse of the desired precision. The best previously known general methods either scale quadratically in the sparsity parameter, or polynomially in the inverse precision. Our approach is especially relevant for implementing quantum walks corresponding to classical random walks like those used in the classical algorithms for approximating permanents and sampling from binary contingency tables. In those algorithms, the sparsity parameter grows with the problem size, while maintaining high precision is required., Modified abstract, clarified conclusion, added application section in appendix and updated references