QIC Abstracts

 Vol.9 No.5&6 May 1, 2009

Research Articles: 
Designing an ion trap for quantum simulation (pp0361-0375)
I.M. Buluta and S. Hasegawa
Planar Coulomb crystals have been recently proposed for the implementation of quantum simulation and computation. In order to put this idea into practice we designed a specialized RF ion trap system. The design is based on extensive numerical simulations of planar Coulomb crystals in RF traps and the estimation of the error in quantum simulation and computation. Our trap would have reduced heating rates and large axial confinement frequencies would be available. Moreover, it provides very good optical access and it is easy to construct and operate.

Quantum direct communication with mutual authentication (pp0376-0394)
C.-A. Yen, S.-J. Horng, H.-S. Goan, T.-W. Kao, and Y.-H. Chou
In this paper, we first point out that some recently proposed quantum direct communication (QDC) protocols with authentication are vulnerable under some specific attacks, and the secrete message will leak out to the authenticator who is introduced to authenticate users participating in the communication. We then propose a new protocol that is capable of achieving secure QDC with authentication as long as the authenticator would do the authentication job faithfully. Our quantum protocol introduces a mutual authentication procedure, uses the quantum Bell states, and applies unitary transformations in the authentication process. Then it exploits and utilizes the entanglement swapping and local unitary operations in the communication processes. Thus, after the authentication process, the client users are left alone to communicate with each other, and the authenticator has no access to the secrete message. In addition, our protocol does not require a direct quantum link between any two users, who want to communicate with each other. This may also be an appealing advantage in the implementation of a practical quantum communication network.

The regime of good control (pp0395-0405)
J. Li and K. Jacobs
We derive the equations of motion describing the feedback control of quantum systems in the regime of ``good control", in which the control is sufficient to keep the system close to the desired state. One can view this regime as the quantum equivalent of the ``linearized" regime for feedback control of classical nonlinear systems. Strikingly, while the dynamics of a single qubit in this regime is indeed linear, that of all larger systems remains nonlinear, in contrast to the classical case. As a first application of these equations, we determine the steady-state performance of feedback protocols for a single qubit that use unbiased measurements.

Mixing doubly stochastic quantum channels with the completely depolarizing channel (pp0406-0413)
J. Watrous
It is proved that every doubly stochastic quantum channel that is properly averaged with the completely depolarizing channel can be written as a convex combination of unitary channels. It follows that within the space of doubly stochastic quantum channels, there is a ball with positive radius around the completely depolarizing channel within which all channels are convex combinations of unitary channels.

Quantum wavelet transforms of any order (pp0414-0422)
F. Arguello
Many classical algorithms are known to efficiently compute the wavelet transforms. However, those classical algorithms cannot be directly translated to quantum algorithms. Recently, efficient and complete quantum algorithms for two representative wavelet transforms (quantum Haar and quantum Daubechies of fourth order) have been proposed. In this paper, we generalize these algorithms in order to they can be applied to Daubechies wavelet kernels of any order. Specifically, we develop a method that efficiently factorize those kernels. The factorization is compatible with the existing pyramidal and packet quantum wavelet algorithms. All steps of the algorithm are unitary and easily implementable on a quantum computer.

Synthesis of quantum circuits for $d$-level systems by using cosine-sine (pp0423-0443)
Y. Nakajima, Y. Kawano, H. Sekigawa, M. Nakanishi, S. Yamashita, and Y. Nakashima
We study the problem of designing minimal quantum circuits for any operations on $n$ qudits by means of the cosine-sine decomposition. Our method is based on a divide-and-conquer strategy. In that strategy, the size of the produced quantum circuit depends on whether the partitioning is balanced. We provide a new cosine-sine decomposition based on a balanced partitioning for $d$-level systems. The produced circuit is not asymptotically optimal except when $d$ is a power of two, but, when the number of qudits $n$ is small, our method can produce the smallest quantum circuit compared to the circuits produced by other synthesis methods. For example, when $d=3$ (three-level systems) and $n=2$ (two qudits), then the number of two-qudit operations called CINC, which is a generalized versions of CNOT, is 36 whereas the previous method needs 156 CINC gates. Moreover, we show that our method is useful for designing a polynomial-size quantum circuit for the radix-$d$ quantum Fourier transform.

Quantum communication complexity of block-composed functions (pp0444-0460)
Y.-Y. Shi and Y.-F. Zhu
A major open problem in communication complexity is whether or not quantum protocols can be exponentially more efficient than classical ones for computing a {\em total} Boolean function in the two-party interactive model. Razborov's result ({\em Izvestiya: Mathematics}, 67(1):145--159, 2002) implies the conjectured negative answer for functions $F$ of the following form: $F(x, y)=f_n(x_1\cdot y_1, x_2\cdot y_2, ..., x_n\cdot y_n)$, where $f_n$ is a {\em symmetric} Boolean function on $n$ Boolean inputs, and $x_i$, $y_i$ are the $i$'th bit of $x$ and $y$, respectively. His proof critically depends on the symmetry of $f_n$. We develop a lower-bound method that does not require symmetry and prove the conjecture for a broader class of functions. Each of those functions $F$ is the ``block-composition'' of a ``building block'' $g_k : \{0, 1\}^k \times \{0, 1\}^k \rightarrow \{0, 1\}$, and an $f_n : \{0, 1\}^n \rightarrow \{0, 1\}$, such that $F(x, y) = f_n( g_k(x_1, y_1), g_k(x_2, y_2), ..., g_k(x_n, y_n) )$, where $x_i$ and $y_i$ are the $i$'th $k$-bit block of $x, y\in\{0, 1\}^{nk}$, respectively. We show that as long as g_k itself is "hard'' enough, its block-composition with an arbitrary f_n has polynomially related quantum and classical communication complexities. For example, when g_k is the Inner Product function with k=\Omega(\log n), the deterministic communication complexity of its block-composition with any f_n is asymptotically at most the quantum complexity to the power of 7.

On the CNOT -cost of TOFFOLI gates (pp0461-0486)
V.V. Shende and I.L. Markov
The three-input \TOFFOLI\ gate is the workhorse of circuit synthesis for classical logic operations on quantum data,
e.g., reversible arithmetic circuits. In physical implementations, however, \TOFFOLI\ gates are decomposed into six \CNOT\ gates and several one-qubit gates. Though this decomposition has been known for at least 10 years, we provide here the first demonstration of its \CNOT-optimality. We study three-qubit circuits which contain less than six \CNOT\ gates and implement a block-diagonal operator, then show that they implicitly describe the cosine-sine decomposition of a related operator. Leveraging the canonical nature of such decompositions to limit one-qubit gates appearing in respective circuits, we prove that the $n$-qubit analogue of the \TOFFOLI\ requires at least $2n$ \CNOT\ gates. Additionally, our results offer a complete classification of three-qubit diagonal operators by their \CNOT -cost, which holds even if ancilla qubits are available.

Locality bounds on Hamiltonians for stabilizer codes (pp0487-0499)
S.S. Bullock and D.P. O'Leary
In this paper, we study the complexity of Hamiltonians whose groundstate is a stabilizer code. We introduce various notions of $k$-locality of a stabilizer code, inherited from the associated stabilizer group. A choice of generators leads to a Hamiltonian with the code in its groundspace. We establish bounds on the locality of any other Hamiltonian whose groundspace contains such a code, whether or not its Pauli tensor summands commute. Our results provide insight into the cost of creating an energy gap for passive error correction and for adiabatic quantum computing. The results simplify in the cases of XZ-split codes such as Calderbank-Shor-Steane stabilizer codes and topologically-ordered stabilizer codes arising from surface cellulations.

Quantum algorithms for shifted subset problems (pp0500-0512)
A. Montanaro
We consider a recently proposed generalisation of the abelian hidden subgroup problem: the {\em shifted subset problem}. The problem is to determine a subset $S$ of some abelian group, given access to quantum states of the form $\ket{S+x}$, for some unknown shift $x$. We give quantum algorithms to find Hamming spheres and other subsets of the boolean cube $\{0,1\}^n$. The algorithms have time complexity polynomial in $n$ and give rise to exponential separations from classical computation.

On parallel composition  of zero-knowledge proofs with black-box quantum (pp0513-05532)
R. Jain, A. Kolla, G. Midrijanis, and B.W. Reichardt
Let $L$ be a language decided by a constant-round quantum Arthur-Merlin ($\QAM$) protocol with negligible soundness error and all but possibly the last message being classical. We prove that if this protocol is zero knowledge with a black-box, quantum simulator $\cS$, then $L \in \BQP$. Our result also applies to any language having a three-round quantum interactive proof ($\QIP$), with all but possibly the last message being classical, with negligible soundness error and a black-box quantum simulator. These results in particular make it unlikely that certain protocols can be composed in parallel in order to reduce soundness error, while maintaining zero knowledge with a black-box quantum simulator. They generalize analogous classical results of Goldreich and Krawczyk (1990). Our proof goes via a reduction to quantum black-box search. We show that the existence of a black-box quantum simulator for such protocols when $L \notin \BQP$ would imply an impossibly-good quantum search algorithm.

Exact quantum lower bound for Grover's problem (pp0533-0540)
C. Dohotaru and P. Hoyer   
One of the most important quantum algorithms ever discovered is Grover's algorithm for searching an unordered set. We give a new lower bound in the query model which proves that Grover's algorithm is exactly optimal. Similar to existing methods for proving lower bounds, we bound the amount of information we can gain from a single oracle query, but we bound this information in terms of angles. This allows our proof to be simple, self-contained, based on only elementary mathematics, capturing our intuition, while obtaining at the same time an exact bound.

back to QIC online Front page