SPIN

Deutsch–Jozsa problem (D–J) has exact quantum 1-query complexity (“exact” means no error), but requires super-exponential queries for the optimal classical deterministic decision trees. D–J problem is equivalent to a symmetric partial Boolean function, and in fact, all symmetric partial Boolean functions having exact quantum 1-query complexity have been found out and these functions can be computed by D–J algorithm. A special case is that all symmetric Boolean functions with exact quantum 1-query complexity follow directly and these functions are also all total Boolean functions with exact quantum 1-query complexity obviously. Then there are pending problems concerning partial Boolean functions having exact quantum 1-query complexity and new results have been found, but some problems are still open. In this paper, we review these results regarding exact quantum 1-query complexity and in particular, we also obtain a new result that a partial Boolean function with exact quantum 1-query complexity is constructed and it cannot be computed by D–J algorithm. Further problems are pointed out for future study.

For quantum search via the continuous-time quantum walk, the evolution of the whole system is usually limited in a small subspace. In this paper, we discuss how the symmetries of the graphs are related to the existence of such an invariant subspace, which also suggests a dimensionality reduction method based on group representation theory. We observe that in the one-dimensional subspace spanned by each desired basis state which assembles the identically evolving original basis states, we always get a trivial representation of the symmetry group. So, we could find the desired basis by exploiting the projection operator of the trivial representation. Besides being technical guidance in this type of problem, this discussion also suggests that all the symmetries are used up in the invariant subspace and the asymmetric part of the Hamiltonian is very important for the purpose of quantum search.

Unstructured searching, which is to find the marked element from a given unstructured data set, is a widely studied problem in computer science. It is well known that Grover algorithm provides a quadratic speedup to solve unstructured search problem compared with the classical algorithm. This algorithm has received a lot of attention due to the strong versatility. In this manuscript, we report experimental results of searching a unique target from 16 elements on five different quantum devices of IBM quantum Experience (IBMQ). We first implement the original Grover algorithm on these devices. However, the experiment probability of success of finding the correct target is almost the same as random choice. We then optimize the quantum circuit size of the search algorithm. The oracle operator and diffusion operator are two of the most costly operators in Grover algorithm. For the 16-element quantum search algorithm, both the oracle operator and diffusion operator consist of a triple controlled $Z$ gate ($CCCZ$) and some single-qubit gates. So we optimize the implementation of the $CCCZ$ gate according to the qubits layout of different quantum devices. On the ibmq_santiago, the experimental success rate of the 16-element quantum search algorithm is increased to $41.82\%$ by the optimization, which is better than all the published experiments implemented on IBMQ devices. For other IBMQ devices, the experimental success rate of 16-element quantum search also has been significantly improved. We then try to further reduce the size of the quantum circuit by modifying the Grover algorithm, with a tolerable loss of the theoretical success probability. On ibmq_quito, the experimental success rate is further improved from 25.23% to 27.56% after optimization. These experimental results show the importance of circuit optimization and algorithm optimization in the Noisy-Intermediate-Scale Quantum (NISQ) era.

While quantum computing provides an exponential advantage in solving the system of linear equations, there is little work to solve the system of nonlinear equations with quantum computing. We propose quantum Newton’s method (QNM) for solving $N$-dimensional system of nonlinear equations based on Newton’s method. In QNM, we solve the system of linear equations in each iteration of Newton’s method with quantum linear system solver. We use a specific quantum data structure and $l_{\infty }$ tomography with sample error ${ϵ}_s$ to implement the classical-quantum data conversion process between the two iterations of QNM, thereby constructing the whole process of QNM. The complexity of QNM in each iteration is $O({log}^{4}N∕{ϵ}_s^2)$. Through numerical simulation, we find that when ${ϵ}_s\gg 1∕\sqrt{N}$, QNM is still effective, so the complexity of QNM is sublinear with $N$, which provides quantum advantage compared with the optimal classical algorithm.

Modern recommendation systems leverage historical behavior information to generate precise recommendation results for users. However, when the data scale of users and items is large, it is difficult to generate recommendation results in time. Tang proposed a quantum-inspired recommendation algorithm, which could solve the recommendation problem in constant time complexity. However, Tang’s approach is based on a set of assumptions which rely heavily on some empirical parameters. The time complexity for calculating parameters is high. Thus, this approach cannot be directly applied in industrial applications. In this paper, we propose a method, namely, Quantum-inspired Recommendation system with threshold Proportion Interception (QRPI), which is based on the quantum-inspired recommendation system and more suitable for industrial environments. Compared with the existing widely used recommendation algorithms, we show through numerical experiments that our solution can achieve almost the same performance with better efficiency.

Quantum computing has shown great potential and advantages in solving integer factorization and disordered database search. However, it is not easy to solve specific problems with quantum computing device efficiently and widely, because a lot of professional background knowledge is required. In order to solve this problem, we propose an optimization problem’s automatic hybird quantum framework (OpAQ) for solving user-specified problems on a hybrid computing architecture including both quantum and classical computing resources. Such a solver can allow nonprofessionals who are not familiar with quantum physics and quantum computing to use quantum computing device to solve some classically difficult problems easily. Combinatorial optimization problem is one of the most important problems in both academic and industry. In this paper, we mainly focus on these problems and solve them with OpAQ, which is based on quantum approximation optimization algorithm (QAOA). We evaluate the performance of our approach in solving Graph Coloring, Max-cut, Traveling Salesman and Knapsack Problem. The experimental results show that quantum solver can achieve almost the same optimal solutions with the classical.

Computing the distance parameters of a network, including the diameter, radius, eccentricities and the all-pairs shortest paths (APSP) is a central problem in distributed computing. This paper investigates the distance parameters in the quantum CONGEST models and establishes almost linear lower bounds on eccentricities and APSP, which match the classical upper bounds. Our results imply that there is not quantum speedup for these two problems. In contrast with the diameter and radius, exchanging quantum messages is able to save the communication when the networks have low diameters [F. L. Gall and F. Magniez, Sublinear-time quantum computation of the diameter in CONGEST networks, in Proc. 2018 ACM Symp. Principles of Distributed Computing (PODC), (2018), pp. 337–346; F. Magniez and A. Nayak, arXiv:2002.11795]. We obtain the lower bounds via a reduction from the two-way quantum communication complexity of the set intersection [A. A. Razborov, Izv. Math. 159 (2003)].

In the NISQ era, quantum computers have insufficient qubits to support quantum error correction, which can only perform shallow quantum algorithms under noisy conditions. Aiming to improve the fidelity of quantum circuits, it is necessary to reduce the circuit depth as much as possible to mitigate the coherent noise. To address the issue, we propose PaF, a Pattern matching-based quantum circuit rewriting algorithm Framework to optimize quantum circuits. The algorithm framework finds all sub-circuits satisfied in the input quantum circuit according to the given external pattern description, then replaces them with better circuit implementations. To extend the capabilities of PaF, a general pattern description format is proposed to make rewriting patterns in existing work become machine-readable. In order to evaluate the effectiveness of PaF, we employ the BIGD benchmarks in QUEKO benchmark suite to test the performance and the result shows that PaF provides a maximal speedup of $8\times$ by using few patterns.

Adiabatic quantum computing (AQC) is a computation protocol to solve difficult problems exploiting quantum advantage, directly applicable to optimization problems. In performing the AQC, different configurations of the Hamiltonian path could lead to dramatic differences in the computation efficiency. It is thus crucial to configure the Hamiltonian path to optimize the computation performance of AQC. Here we apply a reinforcement learning approach to configure AQC for integer programming, where we find the learning process automatically converges to a quantum algorithm that exhibits scaling advantage over the trivial AQC using a linear Hamiltonian path. This reinforcement-learning-based approach for quantum adiabatic algorithm design for integer programming can well be adapted to the quantum resources in different quantum computation devices, due to its built-in flexibility.