On Finding Sensitivity of Quantum and Classical Gates

We consider a fault model of Boolean gates, both classical and quantum, where some of the inputs may not be connected to the actual gate hardware. This model is somewhat similar to the stuck-at model which is a very popular model in testing Boolean circuits. We consider the problem of detecting such faults; the detection algorithm can query the faulty gate and its complexity is the number of such queries. This problem is related to determining the sensitivity of Boolean functions. We show how quantum parallelism can be used to detect such faults. Specifically, we show that a quantum algorithm can detect such faults more efficiently than a classical algorithm for a Parity gate and an AND gate. We give explicit constructions of quantum detector algorithms and show lower bounds for classical algorithms. We show that the model for detecting such faults is similar to algebraic decision trees and extend some known results from quantum query complexity to prove some of our results.

Determining Acceptance Possibility for a Quantum Computation is Hard for the Polynomial Hierarchy

It is shown that determining whether a quantum computation has a non-zero probability of accepting is at least as hard as the polynomial time hierarchy. This hardness result also applies to determining in general whether a given quantum basis state appears with nonzero amplitude in a superposition, or whether a given quantum bit has positive expectation value at the end of a quantum computation. This result is achieved by showing that the complexity class NQP of Adleman, Demarrais, and Huang, a quantum analog of NP, is equal to the counting class coC=P.

Key Agreement Against Quantum Adversaries

Key agreement is a cryptographic scenario between two legitimate parties, who need to establish a common secret key over a public authenticated channel, and an eavesdropper who intercepts all their messages in order to learn the secret. We consider query complexity in which we count only the number of evaluations (queries) of a given black-box function, and classical communication channels. Ralph Merkle provided the first unclassified scheme for secure communications over insecure channels. When legitimate parties are willing to ask O(N) queries for some parameter N, any classical eavesdropper needs Omega(N^2) queries before being able to learn their secret, which is is optimal. However, a quantum eavesdropper can break this scheme in O(N) queries. Furthermore, it was conjectured that any scheme, in which legitimate parties are classical, could be broken in O(N) quantum queries. In this thesis, we introduce protocols à la Merkle that fall into two categories. When legitimate parties are restricted to use classical computers, we offer the first secure classical scheme. It requires Omega(N^{13/12}) queries of a quantum eavesdropper to learn the secret. We give another protocol having security of Omega(N^{7/6}) queries. Furthermore, for any k>= 2, we introduce a classical protocol in which legitimate parties establish a secret in O(N) queries while the optimal quantum eavesdropping strategy requires Theta(N^{1/2+k/{k+1}}) queries, approaching Theta(N^{3/2}) when k increases. When legitimate parties are provided with quantum computers, we present two quantum protocols improving on the best known scheme before this work. Furthermore, for any k>= 2, we give a quantum protocol in which legitimate parties establish a secret in O(N) queries while the optimal quantum eavesdropping strategy requires Theta(N^{1+{k}/{k+1}})} queries, approaching Theta(N^{2}) when k increases.

From Classical to Quantum Secret Sharing

Dans ce mémoire, nous nous pencherons tout particulièrement sur une primitive cryptographique connue sous le nom de partage de secret. Nous explorerons autant le domaine classique que le domaine quantique de ces primitives, couronnant notre étude par la présentation d’un nouveau protocole de partage de secret quantique nécessitant un nombre minimal de parts quantiques c.-à-d. une seule part quantique par participant. L’ouverture de notre étude se fera par la présentation dans le chapitre préliminaire d’un survol des notions mathématiques sous-jacentes à la théorie de l’information quantique ayant pour but primaire d’établir la notation utilisée dans ce manuscrit, ainsi que la présentation d’un précis des propriétés mathématique de l’état de Greenberger-Horne-Zeilinger (GHZ) fréquemment utilisé dans les domaines quantiques de la cryptographie et des jeux de la communication. Mais, comme nous l’avons mentionné plus haut, c’est le domaine cryptographique qui restera le point focal de cette étude. Dans le second chapitre, nous nous intéresserons à la théorie des codes correcteurs d’erreurs classiques et quantiques qui seront à leur tour d’extrême importances lors de l’introduction de la théorie quantique du partage de secret dans le chapitre suivant. Dans la première partie du troisième chapitre, nous nous concentrerons sur le domaine classique du partage de secret en présentant un cadre théorique général portant sur la construction de ces primitives illustrant tout au long les concepts introduits par des exemples présentés pour leurs intérêts autant historiques que pédagogiques. Ceci préparera le chemin pour notre exposé sur la théorie quantique du partage de secret qui sera le focus de la seconde partie de ce même chapitre. Nous présenterons alors les théorèmes et définitions les plus généraux connus à date portant sur la construction de ces primitives en portant un intérêt particulier au partage quantique à seuil. Nous montrerons le lien étroit entre la théorie quantique des codes correcteurs d’erreurs et celle du partage de secret. Ce lien est si étroit que l’on considère les codes correcteurs d’erreurs quantiques étaient de plus proches analogues aux partages de secrets quantiques que ne leur étaient les codes de partage de secrets classiques. Finalement, nous présenterons un de nos trois résultats parus dans A. Broadbent, P.-R. Chouha, A. Tapp (2009); un protocole sécuritaire et minimal de partage de secret quantique a seuil (les deux autres résultats dont nous traiterons pas ici portent sur la complexité de la communication et sur la simulation classique de l’état de GHZ).

Interactive quantum information theory

La théorie de l'information quantique s'est développée à une vitesse fulgurante au cours des vingt dernières années, avec des analogues et extensions des théorèmes de codage de source et de codage sur canal bruité pour la communication unidirectionnelle. Pour la communication interactive, un analogue quantique de la complexité de la communication a été développé, pour lequel les protocoles quantiques peuvent performer exponentiellement mieux que les meilleurs protocoles classiques pour certaines tâches classiques. Cependant, l'information quantique est beaucoup plus sensible au bruit que l'information classique. Il est donc impératif d'utiliser les ressources quantiques à leur plein potentiel. Dans cette thèse, nous étudions les protocoles quantiques interactifs du point de vue de la théorie de l'information et étudions les analogues du codage de source et du codage sur canal bruité. Le cadre considéré est celui de la complexité de la communication: Alice et Bob veulent faire un calcul quantique biparti tout en minimisant la quantité de communication échangée, sans égard au coût des calculs locaux. Nos résultats sont séparés en trois chapitres distincts, qui sont organisés de sorte à ce que chacun puisse être lu indépendamment. Étant donné le rôle central qu'elle occupe dans le contexte de la compression interactive, un chapitre est dédié à l'étude de la tâche de la redistribution d'état quantique. Nous prouvons des bornes inférieures sur les coûts de communication nécessaires dans un contexte interactif. Nous prouvons également des bornes atteignables avec un seul message, dans un contexte d'usage unique. Dans un chapitre subséquent, nous définissons une nouvelle notion de complexité de l'information quantique. Celle-ci caractérise la quantité d'information, plutôt que de communication, qu'Alice et Bob doivent échanger pour calculer une tâche bipartie. Nous prouvons beaucoup de propriétés structurelles pour cette quantité, et nous lui donnons une interprétation opérationnelle en tant que complexité de la communication quantique amortie. Dans le cas particulier d'entrées classiques, nous donnons une autre caractérisation permettant de quantifier le coût encouru par un protocole quantique qui oublie de l'information classique. Deux applications sont présentées: le premier résultat général de somme directe pour la complexité de la communication quantique à plus d'une ronde, ainsi qu'une borne optimale, à un terme polylogarithmique près, pour la complexité de la communication quantique avec un nombre de rondes limité pour la fonction « ensembles disjoints ». Dans un chapitre final, nous initions l'étude de la capacité interactive quantique pour les canaux bruités. Étant donné que les techniques pour distribuer de l'intrication sont bien étudiées, nous nous concentrons sur un modèle avec intrication préalable parfaite et communication classique bruitée. Nous démontrons que dans le cadre plus ardu des erreurs adversarielles, nous pouvons tolérer un taux d'erreur maximal de une demie moins epsilon, avec epsilon plus grand que zéro arbitrairement petit, et ce avec un taux de communication positif. Il s'ensuit que les canaux avec bruit aléatoire ayant une capacité positive pour la transmission unidirectionnelle ont une capacité positive pour la communication interactive quantique. Nous concluons avec une discussion de nos résultats et des directions futures pour ce programme de recherche sur une théorie de l'information quantique interactive.

An investigation of the germylene addition reaction, GeH2+C2H2: Time-resolved gas-phase kinetic studies and quantum chemical calculations of the reaction energy surface

Time resolved studies of germylene, GeH2, generated by laser flash photolysis of 3,4-dimethylgermacyclopentene-3, have been carried out to obtain rate constants for its bimolecular reaction with acetylene, C2H2. The reaction was studied in the gas-phase over the pressure range 1-100 Tort, with SF6 as bath gas, at 5 temperatures in the range 297-553 K. The reaction showed a very slight pressure dependence at higher temperatures. The high pressure rate constants (obtained by extrapolation at the three higher temperatures) gave the Arrhenius equation: log(k(infinity)/cm(3) molecule(-1) s(-1)) (-10.94 +/- 0.05) + (6.10 +/- 0.36 kJ mol(-1))/RTln10. These Arrhenius parameters are consistent with a fast reaction occurring at approximately 30% of the collision rate at 298 K. Quantum chemical calculations (both DFT and ab initio G2//B3LYP and G2//QCISD) of the GeC2H4 potential energy surface (PES), show that GeH2 + C2H2 react initially to form germirene which can isomerise to vinylgermylene with a relatively low barrier. RRKM modelling, based on a loose association transition state, but assuming vinylgermylene is the end product (used in combination with a weak collisional deactivation model) predicts a strong pressure dependence using the calculated energies, in conflict with the experimental evidence. The detailed GeC2H4 PES shows considerable complexity with ten other accessible stable minima (B3LYP level), the three most stable of which are all germylenes. Routes through this complex surface were examined in detail. The only product combination which appears capable of satisfying the (P-3) + C2H4.C2H4 was confirmed as a product by GC observed lack of a strong pressure dependence is Ge(P-3) + C2H4. C2H4 was confirmed as a product by GC analysis. Although the formation of these products are shown to be possible by singlet-triplet curve crossing during dissociation of 1-germiranylidene (1-germacyclopropylidene), it seems more likely (on thermochernical grounds) that the triplet biradical, (GeCH2CH2.)-Ge-., is the immediate product precursor. Comparisons are made with the reaction of SiH2 with C2H2.

A parallel quantum histogram architecture

A parallel formulation of an algorithm for the histogram computation of n data items using an on-the-fly data decomposition and a novel quantum-like representation (QR) is developed. The QR transformation separates multiple data read operations from multiple bin update operations thereby making it easier to bind data items into their corresponding histogram bins. Under this model the steps required to compute the histogram is n/s + t steps, where s is a speedup factor and t is associated with pipeline latency. Here, we show that an overall speedup factor, s, is available for up to an eightfold acceleration. Our evaluation also shows that each one of these cells requires less area/time complexity compared to similar proposals found in the literature.

The low-lying electronic states of BeP: a reliable and accurate quantum mechanical prediction

A very high level of theoretical treatment (complete active space self-consistent field CASSCF/MRCI/aug-cc-pV5Z) was used to characterize the spectroscopic properties of a manifold of quartet and doublet states of the species BeP, as yet experimentally unknown. Potential energy curves for 11 electronic states were obtained, as well as the associated vibrational energy levels, and a whole set of spectroscopic constants. Dipole moment functions and vibrationally averaged dipole moments were also evaluated. Similarities and differences between BeN and BeP were analysed along with the isovalent SiB species. The molecule BeP has a X (4)Sigma(-) ground state, with an equilibrium bond distance of 2.073 angstrom, and a harmonic frequency of 516.2 cm(-1); it is followed closely by the states (2)Pi (R(e) = 2.081 angstrom, omega(e) = 639.6 cm(-1)) and (2)Sigma(-) (R(e) = 2.074 angstrom, omega(e) = 536.5 cm(-1)), at 502 and 1976 cm(-1), respectively. The other quartets investigated, A (4)Pi (R(e) = 1.991 angstrom, omega(e) = 555.3 cm(-1)) and B (4)Sigma(-) (R(e) = 2.758 angstrom, omega(e) = 292.2 cm(-1)) lie at 13 291 and 24 394 cm(-1), respectively. The remaining doublets ((2)Delta, (2)Sigma(+)(2) and (2)Pi(3)) all fall below 28 000 cm(-1). Avoided crossings between the (2)Sigma(+) states and between the (2)Pi states add an extra complexity to this manifold of states.

Quantum modeling of bioconjugated nanomaterials

In recent years, the bio-conjugated nanostructured materials have emerged as a new class of materials for the bio-sensing and medical diagnostics applications. In spite of their multi-directional applications, interfacing nanomaterials with bio-molecules has been a challenge due to somewhat limited knowledge about the underlying physics and chemistry behind these interactions and also for the complexity of biomolecules. The main objective of this dissertation is to provide such a detailed knowledge on bioconjugated nanomaterials toward their applications in designing the next generation of sensing devices. Specifically, we investigate the changes in the electronic properties of a boron nitride nanotube (BNNT) due to the adsorption of different bio-molecules, ranging from neutral (DNA/RNA nucleobases) to polar (amino acid molecules). BNNT is a typical member of III-V compounds semiconductors with morphology similar to that of carbon nanotubes (CNTs) but with its own distinct properties. More specifically, the natural affinity of BNNTs toward living cells with no apparent toxicity instigates the applications of BNNTs in drug delivery and cell therapy. Our results predict that the adsorption of DNA/RNA nucleobases on BNNTs amounts to different degrees of modulation in the band gap of BNNTs, which can be exploited for distinguishing these nucleobases from each other. Interestingly, for the polar amino acid molecules, the nature of interaction appeared to vary ranging from Coulombic, van der Waals and covalent depending on the polarity of the individual molecules, each with a different binding strength and amount of charge transfer involved in the interaction. The strong binding of amino acid molecules on the BNNTs explains the observed protein wrapping onto BNNTs without any linkers, unlike carbon nanotubes (CNTs). Additionally, the widely varying binding energies corresponding to different amino acid molecules toward BNNTs indicate to the suitability of BNNTs for the biosensing applications, as compared to the metallic CNTs. The calculated I-V characteristics in these bioconjugated nanotubes predict notable changes in the conductivity of BNNTs due to the physisorption of DNA/RNA nucleobases. This is not the case with metallic CNTs whose transport properties remained unaltered in their conjugated systems with the nucleobases. Collectively, the bioconjugated BNNTs are found to be an excellent system for the next generation sensing devices.

Quantum dynamics as a physical resource

How useful is a quantum dynamical operation for quantum information processing? Motivated by this question, we investigate several strength measures quantifying the resources intrinsic to a quantum operation. We develop a general theory of such strength measures, based on axiomatic considerations independent of state-based resources. The power of this theory is demonstrated with applications to quantum communication complexity, quantum computational complexity, and entanglement generation by unitary operations.

Quantum computing and polynomial equations over the finite field Z(2)

What is the computational power of a quantum computer? We show that determining the output of a quantum computation is equivalent to counting the number of solutions to an easily computed set of polynomials defined over the finite field Z(2). This connection allows simple proofs to be given for two known relationships between quantum and classical complexity classes, namely BQP subset of P-#P and BQP subset of PP.

Optimal control, geometry, and quantum computing

We prove upper and lower bounds relating the quantum gate complexity of a unitary operation, U, to the optimal control cost associated to the synthesis of U. These bounds apply for any optimal control problem, and can be used to show that the quantum gate complexity is essentially equivalent to the optimal control cost for a wide range of problems, including time-optimal control and finding minimal distances on certain Riemannian, sub-Riemannian, and Finslerian manifolds. These results generalize the results of [Nielsen, Dowling, Gu, and Doherty, Science 311, 1133 (2006)], which showed that the gate complexity can be related to distances on a Riemannian manifold.

Complexity and chirality indices for molecular informatics::differential geometry approach

Novel molecular complexity measures are designed based on the quantum molecular kinematics. The Hamiltonian matrix constructed in a quasi-topological approximation describes the temporal evolution of the modelled electronic system and determined the time derivatives for the dynamic quantities. This allows to define the average quantum kinematic characteristics closely related to the curvatures of the electron paths, particularly, the torsion reflecting the chirality of the dynamic system. A special attention has been given to the computational scheme for this chirality measure. The calculations on realistic molecular systems demonstrate reasonable behaviour of the proposed molecular complexity indices.

A quantum Jensen-Shannon graph kernel for unattributed graphs

In this paper, we use the quantum Jensen-Shannon divergence as a means of measuring the information theoretic dissimilarity of graphs and thus develop a novel graph kernel. In quantum mechanics, the quantum Jensen-Shannon divergence can be used to measure the dissimilarity of quantum systems specified in terms of their density matrices. We commence by computing the density matrix associated with a continuous-time quantum walk over each graph being compared. In particular, we adopt the closed form solution of the density matrix introduced in Rossi et al. (2013) [27,28] to reduce the computational complexity and to avoid the cumbersome task of simulating the quantum walk evolution explicitly. Next, we compare the mixed states represented by the density matrices using the quantum Jensen-Shannon divergence. With the quantum states for a pair of graphs described by their density matrices to hand, the quantum graph kernel between the pair of graphs is defined using the quantum Jensen-Shannon divergence between the graph density matrices. We evaluate the performance of our kernel on several standard graph datasets from both bioinformatics and computer vision. The experimental results demonstrate the effectiveness of the proposed quantum graph kernel.