COMPLEXITY MEASURE: A QUANTUM INFORMATION APPROACH

In the past decades, all of the efforts at quantifying systems complexity with a general tool has usually relied on using Shannon's classical information framework to address the disorder of the system through the Boltzmann-Gibbs-Shannon entropy, or one of its extensions. However, in recent years, there were some attempts to tackle the quantification of algorithmic complexities in quantum systems based on the Kolmogorov algorithmic complexity, obtaining some discrepant results against the classical approach. Therefore, an approach to the complexity measure is proposed here, using the quantum information formalism, taking advantage of the generality of the classical-based complexities, and being capable of expressing these systems' complexity on other framework than its algorithmic counterparts. To do so, the Shiner-Davison-Landsberg (SDL) complexity framework is considered jointly with linear entropy for the density operators representing the analyzed systems formalism along with the tangle for the entanglement measure. The proposed measure is then applied in a family of maximally entangled mixed state.

On the Complexity of Quantum ACC

For any q > 1, let MOD_q be a quantum gate that determines if the number of 1's in the input is divisible by q. We show that for any q,t > 1, MOD_q is equivalent to MOD_t (up to constant depth). Based on the case q=2, Moore has shown that quantum analogs of AC^(0), ACC[q], and ACC, denoted QAC^(0)_wf, QACC[2], QACC respectively, define the same class of operators, leaving q > 2 as an open question. Our result resolves this question, implying that QAC^(0)_wf = QACC[q] = QACC for all q. We also prove the first upper bounds for QACC in terms of related language classes. We define classes of languages EQACC, NQACC (both for arbitrary complex amplitudes) and BQACC (for rational number amplitudes) and show that they are all contained in TC^(0). To do this, we show that a TC^(0) circuit can keep track of the amplitudes of the state resulting from the application of a QACC operator using a constant width polynomial size tensor sum. In order to accomplish this, we also show that TC^(0) can perform iterated addition and multiplication in certain field extensions.

Quantum nonlocality, cryptography and complexity

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Lower bounds on the complexity of simulating quantum gates

We give a simple proof of a formula for the minimal time required to simulate a two-qubit unitary operation using a fixed two-qubit Hamiltonian together with fast local unitaries. We also note that a related lower bound holds for arbitrary n-qubit gates.

Document ranking with quantum probabilities

In this thesis we investigate the use of quantum probability theory for ranking documents. Quantum probability theory is used to estimate the probability of relevance of a document given a user's query. We posit that quantum probability theory can lead to a better estimation of the probability of a document being relevant to a user's query than the common approach, i. e. the Probability Ranking Principle (PRP), which is based upon Kolmogorovian probability theory. Following our hypothesis, we formulate an analogy between the document retrieval scenario and a physical scenario, that of the double slit experiment. Through the analogy, we propose a novel ranking approach, the quantum probability ranking principle (qPRP). Key to our proposal is the presence of quantum interference. Mathematically, this is the statistical deviation between empirical observations and expected values predicted by the Kolmogorovian rule of additivity of probabilities of disjoint events in configurations such that of the double slit experiment. We propose an interpretation of quantum interference in the document ranking scenario, and examine how quantum interference can be effectively estimated for document retrieval. To validate our proposal and to gain more insights about approaches for document ranking, we (1) analyse PRP, qPRP and other ranking approaches, exposing the assumptions underlying their ranking criteria and formulating the conditions for the optimality of the two ranking principles, (2) empirically compare three ranking principles (i. e. PRP, interactive PRP, and qPRP) and two state-of-the-art ranking strategies in two retrieval scenarios, those of ad-hoc retrieval and diversity retrieval, (3) analytically contrast the ranking criteria of the examined approaches, exposing similarities and differences, (4) study the ranking behaviours of approaches alternative to PRP in terms of the kinematics they impose on relevant documents, i. e. by considering the extent and direction of the movements of relevant documents across the ranking recorded when comparing PRP against its alternatives. Our findings show that the effectiveness of the examined ranking approaches strongly depends upon the evaluation context. In the traditional evaluation context of ad-hoc retrieval, PRP is empirically shown to be better or comparable to alternative ranking approaches. However, when we turn to examine evaluation contexts that account for interdependent document relevance (i. e. when the relevance of a document is assessed also with respect to other retrieved documents, as it is the case in the diversity retrieval scenario) then the use of quantum probability theory and thus of qPRP is shown to improve retrieval and ranking effectiveness over the traditional PRP and alternative ranking strategies, such as Maximal Marginal Relevance, Portfolio theory, and Interactive PRP. This work represents a significant step forward regarding the use of quantum theory in information retrieval. It demonstrates in fact that the application of quantum theory to problems within information retrieval can lead to improvements both in modelling power and retrieval effectiveness, allowing the constructions of models that capture the complexity of information retrieval situations. Furthermore, the thesis opens up a number of lines for future research. These include: (1) investigating estimations and approximations of quantum interference in qPRP; (2) exploiting complex numbers for the representation of documents and queries, and; (3) applying the concepts underlying qPRP to tasks other than document ranking.

Plasma nanoscience : from controlled complexity to practical simplicity

Plasma Nanoscience is a multidisciplinary research field which aims to elucidate the specific roles, purposes, and benefits of the ionized gas environment in assembling and processing nanoscale objects in natural, laboratory and technological situations. Compared to neutral gas-based routes, in low-temperature weakly-ionized plasmas there is another level of complexity related to the necessity of creating and sustaining a suitable degree of ionization and a much larger number of species generated in the gas phase. The thinner the nanotubes, the stronger is the quantum confinement of electrons and more unique size-dependent quantum effects can emerge. Furthermore, due to a very high mobility of electrons, the surfaces are at a negative potential compared to the plasma bulk. Therefore, there are non-uniform electric fields within the plasma sheath. The electric field lines start in the plasma bulk and converge to the sharp tips of the developing one-dimensional nanostructures.

Proton NMR studies of dihalogenated phenyl benzamides: two-dimensional higher quantum methodologies

The scalar coupled proton NMR spectra of many organic molecules possessing more than one phenyl ring are generally complex due to degeneracy of transitions arising from the closely resonating protons, in addition to several short- and long- range couplings experienced by each proton. Analogous situations are generally encountered in derivatives of halogenated benzanilides. Extraction of information from such spectra is challenging and demands the differentiation of spectrum pertaining to each phenyl ring and the simplification of their spectral complexity. The present study employs the blend of independent spin system filtering and the spin-state selective detection of single quantum (SO) transitions by the two-dimensional multiple quantum (MQ) methodology in achieving this goal. The precise values of the scalar couplings of very small magnitudes have been derived by double quantum resolved experiments. The experiments also provide the relative signs of heteronuclear couplings. Studies on four isomers of dilhalogenated benzanilides are reported in this work.

Quantum and non-Markovian effects in the electron transfer reaction dynamics in the Marcus inverted region

Electron transfer reactions in large molecules may often be coupled to both the polar solvent modes and the intramolecular vibrational modes of the molecule. This can give rise to a complex dynamics which may in some systems, like betaine, be controlled more by vibrational rather than by solvent effects. Additionally, a significant contribution from an ultrafast relaxation component in the solvation dynamics may enhance the complexity. To explain the wide range of behavior that has been observed experimentally, Barbara et al. recently proposed that a model of an electron transfer reaction should minimally consist of a low-frequency classical solvent mode (X), a low-frequency vibrational mode (Q), and a high-frequency quantum mode (q) (J. Phys. Chem. 1991, 96, 3728). In the present work, a theoretical study of this model is described. This study generalizes earlier work by including the biphasic solvent response and the dynamics of the low-frequency vibrational mode in the presence of a delocalized, extended reaction zone. A novel Green's function technique has been developed which allowed us to study the non-Markovian dynamics on a multidimensional surface. The contributions from the high-frequency vibrational mode and the ultrafast component in the non-Markovian solvent dynamics are found to be primarily responsible for the dramatic increase in charge transfer rate over the prediction of the classical theories that neglect both these factors. These, along with a large coupling between the reactant and the product states, may combine to render the electron transfer rate both very large and constant over a wide range of solvent relaxation rates. A study on the free energy gap dependence of the electron transfer rate reveals that the rates are sensitive to changes in the quantum frequency particularly when the free energy gap is very large.

Experimental implementation of quantumUlam’s problem in a nuclear magnetic resonance quantum information processor

The Ulam’s problem is a two person game in which one of the player tries to search, in minimum queries, a number thought by the other player. Classically the problem scales polynomially with the size of the number. The quantum version of the Ulam’s problem has a query complexity that is independent of the dimension of the search space. The experimental implementation of the quantum Ulam’s problem in a Nuclear Magnetic Resonance Information Processor with 3 quantum bits is reported here.

Quantum Interference and Entanglement of Surface Plasmons

Surface plasma waves arise from the collective oscillations of billions of electrons at the surface of a metal in unison. The simplest way to quantize these waves is by direct analogy to electromagnetic fields in free space, with the surface plasmon, the quantum of the surface plasma wave, playing the same role as the photon. It follows that surface plasmons should exhibit all of the same quantum phenomena that photons do, including quantum interference and entanglement.

Unlike photons, however, surface plasmons suffer strong losses that arise from the scattering of free electrons from other electrons, phonons, and surfaces. Under some circumstances, these interactions might also cause “pure dephasing,” which entails a loss of coherence without absorption. Quantum descriptions of plasmons usually do not account for these effects explicitly, and sometimes ignore them altogether. In light of this extra microscopic complexity, it is necessary for experiments to test quantum models of surface plasmons.

In this thesis, I describe two such tests that my collaborators and I performed. The first was a plasmonic version of the Hong-Ou-Mandel experiment, in which we observed two-particle quantum interference between plasmons with a visibility of 93 ± 1%. This measurement confirms that surface plasmons faithfully reproduce this effect with the same visibility and mutual coherence time, to within measurement error, as in the photonic case.

The second experiment demonstrated path entanglement between surface plasmons with a visibility of 95 ± 2%, confirming that a path-entangled state can indeed survive without measurable decoherence. This measurement suggests that elastic scattering mechanisms of the type that might cause pure dephasing must have been weak enough not to significantly perturb the state of the metal under the experimental conditions we investigated.

These two experiments add quantum interference and path entanglement to a growing list of quantum phenomena that surface plasmons appear to exhibit just as clearly as photons, confirming the predictions of the simplest quantum models.