Analysis of Quantum Computers and Randomness

Cristian S. Calude

Stefan Heinrich

We give a short introduction to quantum computing and its relation to numerical analysis. We survey recent research on quantum algorithms and quantum complexity theory for two basic numerical problems – high dimensional integration and approximation. Having matching upper and lower complexity bounds for the quantum setting, we are in a position to compare them with those for the classical deterministic and randomized setting, previously obtained in information-based complexity theory. This enables us to assess the possible speedups quantum computation could provide over classical deterministic or randomized algorithms for these numerical problems.

Yutaka Shikano, Kentaro Tamura, Rudy Raymond

All computing devices, including quantum computers, must exhibit that for a given input, an output is produced in accordance with the program. The outputs generated by quantum computers that fulfill these requirements are not temporally correlated, however. In a quantum-computing device comprising solid-state qubits such as superconducting qubits, any operation to rest the qubits to their initial state faces a practical problem. We applied a statistical analysis to a collection of random numbers output from a 20-qubit superconducting-qubit cloud quantum computer using the simplest random number generation scheme. The analysis indicates temporal correlation in the output of some sequences obtained from the 20 qubits. This temporal correlation is not related to the relaxation time of each qubit. We conclude that the correlation could be a result of a systematic error.

Tad Hogg

Quantum computer algorithms can exploit the structure of random satisfiability problems. This paper extends a previous empirical evaluation of such an algorithm and gives an approximate asymptotic analysis accounting for both the average and variation of amplitudes among search states with the same costs. The analysis predicts good performance, on average, for a variety of problems including those near a phase transition associated with a high concentration of hard cases. Based on empirical evaluation for small problems, modifying the algorithm in light of this analysis improves its performance. The algorithm improves on both GSAT, a commonly used conventional heuristic, and quantum algorithms ignoring problem structure.