On Quantum Computation with Some Restricted Amplitudes

Harumichi Nishimura

In this paper, we explore the power of quantum computers with restricted transition amplitudes. In 1997 Adleman, DeMarrais, and Huang showed that quantum Turing machines (QTMs) with the amplitudes from [Formula: see text] are computationally equivalent to ones with the polynomial-time computable amplitudes as machines implementing bounded-error polynomial-time algorithms. We show that QTMs with the amplitudes from [Formula: see text] is polynomial-time equivalent to deterministic Turing machines as machines implementing exact algorithms, i.e., algorithms that output correct answers with certainty. By extending this result, it is shown that exact quantum computers with rational biased coins are equivalent to classical computers. Moreover, we discuss the computational power of exact quantum computers with multiple types of coins. We also show that, from the viewpoint of zero-error polynomial-time algorithms, [Formula: see text] is not more powerful than [Formula: see text] as the set of amplitudes taken by QTMs; however, it is sufficient to solve the factoring problem.

Qiujie Sun

Masashi Kimura

M. I. Dyakonov

The possibility of building a quantum computer is critically analyzed. The main point is that the general state of the hypothetical quantum computer with N qubits is characterized by 2N quantum amplitudes, which are complex numbers restricted by the normalization condition only. It looks highly improbable that it will ever be possible to keep under our control this number of complex parameters even for modest values of [Formula: see text] 50 or 100.

M. I. Dyakonov

In the hypothetical quantum computing one replaces the classical twostate bit by a quantum element (qubit) with two basic states, ↑ and ↓.Its arbitrary state is described by the wave function ψ = a↑+ b↓, where a and b are complex amplitudes, satisfying the normalization condition.Unlike the classical bit, that can be only in one of the two states, ↑ or ↓, the qubit can be in a continuum of states defined by the quantum amplitudes a and b.The qubit is a continuous object.At a given moment, the state of a quantum computer with N qubits is characterized by 2 N quantum amplitudes, which are continuous variables restricted by the normalization condition only.Thus, the hypothetical quantum computer is an analog machine characterized by a super-astronomical number of continuous variables (even for N~100÷1000).Their values cannot be arbitrary, they must be under our control.Thus the answer to the question in title is: When physicists and engineers will learn to keep under control this number of continuous parameters, which means -never.

David Jennings, Kamil Korzekwa, Matteo Lostaglio +1 more

Solving high-dimensional dynamical systems by encoding their state in the amplitudes of a quantum state is expected to be a core application of fault-tolerant quantum computers. However, the conditions under which this paradigm yields quantum advantage can be restrictive, motivating complementary approaches. Here, we introduce Quantum Koopman Algorithms, where quantum amplitudes encode approximately closed sets of observables for a linear or nonlinear dynamics. These amplitudes evolve under the Koopman operator, and we establish conditions for efficient quantum algorithms addressing both dynamical and spectral problems. With this approach, we show that classes of open-system dynamics involving exponentially large fermionic systems can be efficiently simulated on a quantum computer. For nonlinear dynamics, we introduce a novel nonlinear interaction picture that enables quantum simulation beyond existing weak-nonlinearity conditions, and extract late-time spectral data where quantum phase estimation is unavailable.