We propose an adiabatic quantum algorithm for generating a quantum pure state encoding of the PageRank vector, the most widely used tool in ranking the relative importance of internet pages. We present extensive numerical simulations which provide evidence that this algorithm prepares the quantum PageRank state in a time which scales polylogarithmically in the number of webpages. The top ranked log(n) entries of the quantum PageRank state can be estimated with a polynomial quantum speedup. Moreover, the quantum Pagerank state can be used in “q-sampling” protocols for testing properties of distributions, which require exponentially fewer measurements than all classical schemes designed for the same task. This can be used to decide whether to run a classical update of the PageRank.
Adiabatic quantum computation.—Even though classical PageRank computation time scales modestly with the problem size n, in practice its evaluation for the actual WWW already takes weeks, a time which can only be expected to grow if current computational methods remain the norm, given the rapid pace of expansion of the web. Furthermore, it is often desirable to have multiple personalization vectors. We now show how adiabatic quantum computation (AQC) might be able to help in the optimization of the resources needed to provide an up-to-date PageRank.
An interesting problem for future research is to apply compressed sensing techniques—which have recently been extended to quantum state tomography—to the problem of efficiently extracting the relevant information contained in the quantum PageRank state. Finally, it would be interesting to formulate a quantum circuit version of our PageRank algorithm. Perhaps the results obtained in concerning the efficient solution of linear systems of equations could be used for this purpose.
We develop an approach to machine learning and anomaly detection via quantum adiabatic evolution. In the training phase we identify an optimal set of weak classifiers, to form a single strong classifier. In the testing phase we adiabatically evolve one or more strong classifiers on a superposition of inputs in order to find certain anomalous elements in the classification space. Both the training and testing phases are executed via quantum adiabatic evolution. We apply and illustrate this approach in detail to the problem of software verification and validation.
We have developed a quantum adiabatic machine learning approach and applied it to the problem of training a quantum software error classifier. We have also shown how to use this classifier in quantum-parallel on the space of all possible inputoutput pairs of a given implemented software program P. The training procedure involves selecting a set of weak classifiers, which are linearly combined, with binary weights, into two strong classifiers.
The first quantum aspect of our approach is an adiabatic quantum algorithm which finds the optimal set of binary weights as the ground state of a certain Hamiltonian. We presented two alternatives for this algorithm. The first, inspired
by (two research papers) gives weight to single weak classifiers to find an optimal set. The second algorithm for weak classifier selection chooses pairs of weak classifiers to form the optimal set and is based on a set of sufficient conditions for a completely accurate strong classifier that we have developed.
The second quantum aspect of our approach is an explicit procedure for using the optimal strong classifiers in order to search the entire space of input-output pairs in quantum parallel for the existence of an error in P. Such an error is identified by performing an adiabatic quantum evolution, whose manifold of low-energy final states favors erroneous states.
A possible improvement of our approach involves adding intermediate training spaces, which track intermediate program execution states. This has the potential to fine-tune the weak classifiers, and overcome a limitation imposed by the desire to restrict our Hamiltonians to low-order interactions, yet still account for high-order correlations between bits in the inputoutput states.
An additional improvement involves finding optimal interpolation paths s(t) from the initial to the final Hamiltonian for both the classifier training and classifier implementation problems.
We have applied our quantum adiabatic machine learning approach to a problem with real-world applications in flight control systems, which has facilitated both algorithmic development and characterization of the success of training strong classifiers using a set of weak classifiers involving minimal bit correlations.
It is believed that the presence of anticrossings with exponentially small gaps between the lowest two energy levels of the system Hamiltonian, can render adiabatic quantum optimization ineffiient. Here, we present a simple adiabatic quantum algorithm designed to eliminate exponentially small gaps caused by anticrossings between eigenstates that correspond with the local and global minima of the problem Hamiltonian. In each iteration of the algorithm, information is gathered about the local minima that are reached after passing the anticrossing non-adiabatically. This information is then used to penalize pathways to the corresponding local minima, by adjusting the initial Hamiltonian. This is repeated for multiple clusters of local minima as needed. We generate 64-qubit random instances of the maximum independent set problem, skewed to be extremely hard, with between 10^5 and 10^6 highly-degenerate local minima. Using quantum Monte Carlo simulations, it is found that the algorithm can trivially solve all the instances in about 10 iterations.
There is a somewhat simple proof of equivalence to conventional quantum computing by Mizel et al, although the interested reader may prefer the thorough proof by Aharonov who has showed that any quantum circuit can be simulated by an adiabatic quantum algorithm.
Interestingly these proofs show that an AQC is capable of performing all operations
that are executable on a conventional quantum computer. Although no proof exists to show that a conventional quantum computer can reproduce the same operations as an AQC. Due to this phenomenal turn of events, much interest has been generated among physicists and computer scientists for research into the AQC. To the extent that it is now believed that the AQC is a form of the universal quantum computer theorised by Deutsch.
Most realistic solid state devices considered as qubits are not true two-state systems but multi-level systems. They can approximately be considered as qubits only if the energy separation of the upper energy levels from the lowest two is very large. If this condition is not met, the upper states may affect the evolution and therefore cannot be neglected. Here, we consider devices with double-well potential as basic logical elements, and study the effect of higher energy levels, beyond the lowest two, on adiabatic quantum optimization. We show that the extra levels can be modeled by adding additional (ancilla) qubits coupled to the original (logical) qubits. The presence of these levels is shown to have no effect on the final ground state. We also study their influence on the minimum gap for a set of 8-qubit spin glass instances.
The graph-theoretic Ramsey numbers are notoriously difficult to calculate. In fact, for the two color Ramsey numbers R(m, n) with m, n great than or equal to 3, only nine are currently known. We present a quantum algorithm for the computation of the Ramsey numbers R(m, n). We show how the computation of R(m, n) can be mapped to a combinatorial optimization problem whose solution can be found using adiabatic quantum evolution. We numerically simulate this adiabatic quantum algorithm and show that it correctly determines the Ramsey numbers R(3, 3) and R(2, s) for 5 less than or equal to s less than or equal to 7. We then discuss the algorithm’s experimental implementation, and close by showing that Ramsey number computation belongs to the quantum complexity class QMA
In computational complexity theory, QMA, which stands for Quantum Merlin Arthur, is the quantum analog of the deterministic complexity class NP or the probabilistic complexity class MA. It is related to BQP in the same way NP is related to P, or MA is related to BPP.