Quantum computing aims to use quantum mechanical effects for the efficient performance of computational tasks. A popular research direction is enlarging the gap between classical and quantum algorithm complexity of the same computational problem. We present new results in quantum query algorithm design for multivalued functions that allow to achieve a large quantum versus classical complexity separation. To compute a basic finite multifunction in a quantum model only one query is enough while classically three queries are required. Then, we present two generalizations and a modification of the original algorithm, and obtain the following complexity gaps: QUD(M') ≤ N versus CUD(M') ≥ 3N, and QRD(M'') = 1 versus N/2 + 1 ≤ CRD(M'') ≤ N.Quantum computing aims to use quantum mechanical effects for the efficient performance of computational tasks. A popular research direction is enlarging the gap between classical and quantum algorithm complexity of the same computational problem. We present new results in quantum query algorithm design for multivalued functions that allow to achieve a large quantum versus classical complexity separation. To compute a basic finite multifunction in a quantum model only one query is enough while classically three queries are required. Then, we present two generalizations and a modification of the original algorithm, and obtain the following complexity gaps: QUD(M') ≤ N versus CUD(M') ≥ 3N, and QRD(M'') = 1 versus N/2 + 1 ≤ CRD(M'') ≤ N.

International Conference on Natural Computation (ICNC)Jul 1, 20130 citations

Quantum versus classical statistical dynamics of an ultracold Bose gas

Jürgen Berges, Thomas Gasenzer

We investigate the conditions under which quantum fluctuations are relevant for the quantitative interpretation of experiments with ultracold Bose gases. This requires to go beyond the description in terms of the Gross-Pitaevskii and Hartree-Fock-Bogoliubov mean-field theories, which can be obtained as classical (statistical) field-theory approximations of the quantum many-body problem. We employ functional-integral techniques based on the two-particle irreducible (2PI) effective action. The role of quantum fluctuations is studied within the nonperturbative 2PI $1∕\mathcal{N}$ expansion to next-to-leading order. At this accuracy level memory integrals enter the dynamic equations, which differ for quantum and classical statistical descriptions. This can be used to obtain a classicality condition for the many-body dynamics. We exemplify this condition by studying the nonequilibrium evolution of a one-dimensional Bose gas of sodium atoms, and discuss some distinctive properties of quantum versus classical statistical dynamics.We investigate the conditions under which quantum fluctuations are relevant for the quantitative interpretation of experiments with ultracold Bose gases. This requires to go beyond the description in terms of the Gross-Pitaevskii and Hartree-Fock-Bogoliubov mean-field theories, which can be obtained as classical (statistical) field-theory approximations of the quantum many-body problem. We employ functional-integral techniques based on the two-particle irreducible (2PI) effective action. The role of quantum fluctuations is studied within the nonperturbative 2PI $1∕\mathcal{N}$ expansion to next-to-leading order. At this accuracy level memory integrals enter the dynamic equations, which differ for quantum and classical statistical descriptions. This can be used to obtain a classicality condition for the many-body dynamics. We exemplify this condition by studying the nonequilibrium evolution of a one-dimensional Bose gas of sodium atoms, and discuss some distinctive properties of quantum versus classical statistical dynamics.

arXiv:cond-mat/0703163Physical Review ASep 11, 200798 citations

The problem of quantum integrability

Stefan Weigert

Physica D Nonlinear PhenomenaApr 1, 199298 citations

Quantum and classical integrability: new approaches in statistical mechanics

R. Bullough, N. M. Bogoliubov, JUSSI TIMONEN

Physica D Nonlinear PhenomenaAug 1, 19913 citations

Applying computational complexity to the emergence of classicality

Arkady Bolotin

Can the computational complexity theory of computer science and mathematics say something new about unresolved problems in quantum physics? Particularly, can the P versus NP question in the computational complexity theory be a factor in the elucidation of the emergency of classicality in quantum mechanics? The paper compares two different ways of deriving classicality from the quantum formalism resulted from two differing hypotheses regarding the P versus NP question -- the approach of the quantum decoherence theory implying that P = NP and the computational complexity approach which assumes that P is not equal to NP.Can the computational complexity theory of computer science and mathematics say something new about unresolved problems in quantum physics? Particularly, can the P versus NP question in the computational complexity theory be a factor in the elucidation of the emergency of classicality in quantum mechanics? The paper compares two different ways of deriving classicality from the quantum formalism resulted from two differing hypotheses regarding the P versus NP question -- the approach of the quantum decoherence theory implying that P = NP and the computational complexity approach which assumes that P is not equal to NP.

arXiv:1309.1801Sep 7, 20131 citation

1∕\mathcal{N}

expansion to next-to-leading order. At this accuracy level memory integrals enter the dynamic equations, which differ for quantum and classical statistical descriptions. This can be used to obtain a classicality condition for the many-body dynamics. We exemplify this condition by studying the nonequilibrium evolution of a one-dimensional Bose gas of sodium atoms, and discuss some distinctive properties of quantum versus classical statistical dynamics.