QIC Abstracts

 Vol.11 No.3&4 March 1, 2011

Research Articles:

Quantum adiabatic algorithms, small gaps, and different paths (pp0181-0214)
          
Edward Farhi, Jeffrey Goldstone, David Gosset, Sam Gutmann, Harvey B. Meyer, and Peter Shor
We construct a set of instances of 3SAT which are not solved efficiently using the simplest quantum adiabatic algorithm. These instances are obtained by picking random clauses all consistent with two disparate planted solutions and then penalizing one of them with a single additional clause. We argue that by randomly modifying the beginning Hamiltonian, one obtains (with substantial probability) an adiabatic path that removes this difficulty. This suggests that the quantum adiabatic algorithm should in general be run on each instance with many different random paths leading to the problem Hamiltonian. We do not know whether this trick will help for a random instance of 3SAT (as opposed to an instance from the particular set we consider), especially if the instance has an exponential number of disparate assignments that violate few clauses. We use a continuous imaginary time Quantum Monte Carlo algorithm in a novel way to numerically investigate the ground state as well as the first excited state of our system. Our arguments are supplemented by Quantum Monte Carlo data from simulations with up to 150 spins.

Uniform approximation by (quantum) polynomials (pp0215-0225)
          
Andrew Drucker and Ronald de Wolf
We show that quantum algorithms can be used to re-prove a classical theorem in approximation theory, Jackson's Theorem, which gives a nearly-optimal quantitative version of Weierstrass's Theorem on uniform approximation of continuous functions by polynomials. We provide two proofs, based respectively on quantum counting and on quantum phase estimation.

Information reconciliation for QKD (pp0226-0238)
          
David Elkouss, Jesus Martinez-Mateo, and Vicente Martin
Quantum key distribution (QKD) relies on quantum and classical procedures in order to achieve the growing of a secret random string ---the key--- known only to the two parties executing the protocol. Limited intrinsic efficiency of the protocol, imperfect devices and eavesdropping produce errors and information leakage from which the set of measured signals ---the raw key--- must be stripped in order to distill a final, information theoretically secure, key. The key distillation process is a classical one in which basis reconciliation, error correction and privacy amplification protocols are applied to the raw key. This cleaning process is known as information reconciliation and must be done in a fast and efficient way to avoid cramping the performance of the QKD system. Brassard and Salvail proposed a very simple and elegant protocol to reconcile keys in the secret-key agreement context, known as \textit{Cascade}, that has become the de-facto standard for all QKD practical implementations. However, it is highly interactive, requiring many communications between the legitimate parties and its efficiency is not optimal, imposing an early limit to the maximum tolerable error rate. In this paper we describe a low-density parity-check reconciliation protocol that improves significantly on these problems. The protocol exhibits better efficiency and limits the number of uses of the communications channel. It is also able to adapt to different error rates while remaining efficient, thus reaching longer distances or higher secure key rate for a given QKD system.

New families of asymmetric quantum BCH codes (pp0239-0252)
          
Giuliano G. La Guardia
Several families of nonbinary asymmetric quantum Bose-Chaudhuri-Hocquenghem (BCH) codes are presented in this paper. These quantum codes have parameters better than the ones available in the literature. Additionally, such codes can be applied in quantum systems where the asymmetry between qudit-flip and phase-shift errors is large.

Localization of quantum walks on a deterministic recursive tree (pp0253-0261)
          
Xin-Ping Xu
Localization of quantum walks can be characterized by the return probability, i.e., the probability for the walker returning to its original site. In this paper, we consider localization of continuous-time quantum walks in terms of return probability on a deterministic recursive tree, which is generated by adding one node and connecting it to each node of the existing tree recursively. We obtain an approximate form for the return probability using the complete eigenvalues and eigenstates of Laplace matrix of the structure. It is found that the return probability depends on the initial node of the excitation. When the walk starts at the central nodes, the return probability converges to a constant value even in the limit of infinite system, in contrast to an exponential decay of the return probability if the walk starts at the outlying nodes. We also observe a bipartite structure for the distribution of return probability, and provide theoretical interpretation for all our findings. Our results suggest that quantum walks display significant localization and well-bedded structure of return probability on heterogeneous trees.

Block-based quantum-logic synthesis 262 (pp0262-0277)
          
Mehdi Saeedi, Mona Arabzadeh, Morteza Saheb Zamani, and Mehdi Sedighi
In this paper, the problem of constructing an efficient quantum circuit for the implementation of an arbitrary quantum computation is addressed. To this end, a basic block based on the cosine-sine decomposition method is suggested which contains $l$ qubits. In addition, a previously proposed quantum-logic synthesis method based on quantum Shannon decomposition is recursively applied to reach unitary gates over $l$ qubits. Then, the basic block is used and some optimizations are applied to remove redundant gates. It is shown that the exact value of $l$ affects the number of one-qubit and CNOT gates in the proposed method. In comparison to the previous synthesis methods, the value of $l$ is examined consequently to improve either the number of CNOT gates or the total number of gates.
The proposed approach is further analyzed by considering the nearest neighbor limitation. According to our evaluation, the number of CNOT gates is increased by at most a factor of $\frac{5}{3}$ if the nearest neighbor interaction is applied.

Entanglement in massive coupled oscillators 278 (pp0278-0299)
          
Nathan L. Harshman and William F. Flynn

This article investigates entanglement of the motional states of massive coupled oscillators. The specific realization of an idealized diatomic molecule in one-dimension is considered, but the techniques developed apply to any massive particles with two degrees of freedom and a quadratic Hamiltonian. We present two methods, one analytic and one approximate, to calculate the interatomic entanglement for Gaussian and non-Gaussian pure states as measured by the purity of the reduced density matrix. The cases of free and trapped molecules and hetero- and homonuclear molecules are treated. In general, when the trap frequency and the molecular frequency are very different, and when the atomic masses are equal, the atoms are highly-entangled for molecular coherent states and number states. Surprisingly, while the interatomic entanglement can be quite large even for molecular coherent states, the covariance of atomic position and momentum observables can be entirely explained by a classical model with appropriately chosen statistical uncertainty.

Universal quantum computing in linear nearest neighbor architectures (pp0300-0312)
          
Preethika Kumar and Steven R. Skinner

We introduce a scheme for realizing universal quantum computing in a linear nearest neighbor architecture with fixed couplings. We first show how to realize a controlled-NOT gate operation between two adjacent qubits without having to isolate the two qubits from qubits adjacent to them. The gate operation is implemented by applying two consecutive pulses of equal duration, but varying amplitudes, on the target qubit. Since only a single control parameter is required in implementing our scheme, it is very efficient. We next show how our scheme can be used to realize single qubit rotations and two-qubit controlled-unitary operations. As most proposals for solid state implementations of a quantum computer use a one-dimensional line of qubits, the schemes presented here will be extremely useful.

Efficient photon sorter in a high-dimensional state space 313 (pp0313-0325)
          
Warner A. Miller
An increase in the dimension of state space for quantum key distribution (QKD) can decrease its fidelity requirements while also increasing its bandwidth. A significant obstacle for QKD with qu$d$its ($d\geq 3$) has been an efficient and practical quantum state sorter for photons whose complex fields are modulated in both amplitude and phase. We propose such a sorter based on a multiplexed thick hologram, constructed e.g. from photo-thermal refractive (PTR) glass. We validate this approach using coupled-mode theory with parameters consistent with PTR glass to simulate a holographic sorter. The model assumes a three-dimensional state space spanned by three tilted planewaves. The utility of such a sorter for broader quantum information processing applications can be substantial.

Global geometric entanglement in transverse-field XY spin chains: finite and infinite systems 326 (pp0326-0354)
          
Tzu-Chieh Wei, Smitha Vishveshwara, and Paul M. Goldbart
The entanglement in quantum XY spin chains of arbitrary length is investigated via the geometric measure of entanglement. The emergence of entanglement is explained intuitively from the perspective of perturbations. The model is solved exactly and the energy spectrum is determined and analyzed in particular for the lowest two levels for both finite and infinite systems.  The overlaps for these two levels are calculated analytically for arbitrary number of spins. The entanglement is hence obtained by maximizing over a single parameter. The corresponding ground-state
entanglement surface is then determined over the entire phase diagram, and its behavior can be used to delineate the boundaries in the phase diagram. For example, the field-derivative of the entanglement becomes singular along the critical line. The form of the divergence is derived analytically and it turns out to be dictated by the universality class controlling the quantum phase transition. The behavior of the entanglement near criticality can be understood via a scaling hypothesis, analogous to that for free energies. The entanglement density vanishes along the so-called disorder line in the phase diagram, the ground space is doubly degenerate and spanned by two product states. The entanglement for the superposition of the lowest two states is also calculated. The exact value of the entanglement depends on the specific form of superposition. However, in the thermodynamic limit the entanglement density turns out to be independent of the superposition. This proves that the entanglement density is insensitive to whether the ground state is chosen to be the spontaneously $Z_2$ symmetry broken one or not. The finite-size scaling of entanglement at critical points is also investigated from two different view points. First, the maximum in the field-derivative of the entanglement density is computed and fitted to a logarithmic dependence of the system size, thereby deducing the correlation length exponent for the Ising class using only the behavior of entanglement. Second, the entanglement density itself is shown to possess a correction term inversely proportional to the system size, with the coefficient being universal (but with different values for the ground state and the first excited state, respectively).

back to QIC online Front page