Quantum Information and the PCP Theorem

Our main result is that the membership x∈SAT (for x of length n) can be proved by a logarithmic-size quantum state |Ψ〉, together with a polynomial-size classical proof consisting of blocks of length polylog(n) bits each, such that after measuring the state |Ψ〉 the verifier only needs to read one block of the classical proof. This shows that if a short quantum witness is available then a (classical) PCP with only one query is possible. Our second result is that the class QIP/qpoly contains all languages. That is, for any language L (even non-recursive), the membership x∈L (for x of length n) can be proved by a polynomial-size quantum interactive proof, where the verifier is a polynomial-size quantum circuit with working space initiated with some quantum state |Ψ _L,n 〉 (depending only on L and n). Moreover, the interactive proof that we give is of only one round, and the messages communicated are classical. The advice |Ψ _L,n 〉 given to the verifier can also be replaced by a classical probabilistic advice, as long as this advice is kept as a secret from the prover. Our result can hence be interpreted as: the class IP/rpoly contains all languages. For the proof of the second result, we introduce the quantum low-degree-extension of a string of bits. The main result requires an additional machinery of quantum low-degree-test. R. Raz’s research was supported by Israel Science Foundation (ISF) grant.     

Adiabatic quantum counting by geometric phase estimation

We design an adiabatic quantum algorithm for the counting problem, i.e., approximating the proportion, α, of the marked items in a given database. As the quantum system undergoes a designed cyclic adiabatic evolution, it acquires a Berry phase 2πα. By estimating the Berry phase, we can approximate α, and solve the problem. For an error bound e{\epsilon}, the algorithm can solve the problem with cost of order (\frac1e)^3/2{(\frac{1}{\epsilon})^{3/2}}, which is not as good as the optimal algorithm in the quantum circuit model, but better than the classical random algorithm. Moreover, since the Berry phase is a purely geometric feature, the result may be robust to decoherence and resilient to certain noise.     

Decoherence control for high-temperature reservoirs

We investigate the decoherence control coupled to a rather general environment, i.e., without using the Markov approximation. Markovian errors generally require high-energy excitations (of the reservoir) and tend to destroy the scalability of the adiabatic quantum computation. Especially, we find that deriving optimal control using the Pontryagin maximum principle, the decoherence can be suppressed even in high-temperature reservoirs. The influences of Ohmic reservoir with Lorentz-Drude regularization are numerically studied in a two-level system under ω _c ≪ ω ₀ condition, here ω ₀ is the characteristic frequency of the quantum system of interest, and ω _c the cut-off frequency of Ohmic reservoir. It implies that designing some engineered reservoirs with the controlled coupling and state of the environment can slow down the decoherence rate and delay the decoherence time. Moreover, we compared the non-Markovian optimal decoherence control with the Markovian one and find that with non-Markovian the engineered artificial reservoirs are better than the Markovian approximate in controlling the decoherence of open, dissipative quantum systems.     

Quantum Algorithms for Learning and Testing Juntas

In this article we develop quantum algorithms for learning and testing juntas, i.e. Boolean functions which depend only on an unknown set of k out of n input variables. Our aim is to develop efficient algorithms: (1) whose sample complexity has no dependence on n, the dimension of the domain the Boolean functions are defined over; (2) with no access to any classical or quantum membership (“black-box”) queries. Instead, our algorithms use only classical examples generated uniformly at random and fixed quantum superpositions of such classical examples; (3) which require only a few quantum examples but possibly many classical random examples (which are considered quite “cheap” relative to quantum examples). Our quantum algorithms are based on a subroutine FS which enables sampling according to the Fourier spectrum of f; the FS subroutine was used in earlier work of Bshouty and Jackson on quantum learning. Our results are as follows: (1) We give an algorithm for testing k-juntas to accuracy ε that uses O(k/ϵ) quantum examples. This improves on the number of examples used by the best known classical algorithm. (2) We establish the following lower bound: any FS-based k-junta testing algorithm requires queries. (3) We give an algorithm for learning k-juntas to accuracy ϵ that uses O(ϵ⁻¹ k log k) quantum examples and O(2 ^k log(1/ϵ)) random examples. We show that this learning algorithm is close to optimal by giving a related lower bound. Supported in part by NSF award CCF-0347282, by NSF award CCF-0523664, and by a Sloan Foundation Fellowship.     

Generic Quantum Markov Semigroups: the Gaussian Gauge Invariant Case

We study a class of generic quantum Markov semigroups on the algebra of all bounded operators on a Hilbert space arising from the stochastic limit of a discrete system with generic Hamiltonian H _S , acting on , interacting with a Gaussian, gauge invariant, reservoir. The selfadjoint operator H _S determines a privileged orthonormal basis of . These semigroups leave invariant diagonal and off-diagonal bounded operators with respect to this basis. The action on diagonal operators describes a classical Markov jump process. We construct generic semigroups from their formal generators by the minimal semigroup method and discuss their conservativity (uniqueness). When the semigroup is irreducible we prove uniqueness of the equilibrium state and show that, starting from an arbitrary initial state, the semigroup converges towards this state. We also prove that the exponential speed of convergence of the quantum Markov semigroup coincides with the exponential speed of convergence of the classical (diagonal) semigroup towards its unique invariant measure. The exponential speed is computed or estimated in some examples.     

Quantum Algorithms for Weighing Matrices and Quadratic Residues

Abstract. In this article we investigate how we can employ the structure of combinatorial objects like Hadamard matrices and weighing matrices to devise new quantum algorithms. We show how the properties of a weighing matrix can be used to construct a problem for which the quantum query complexity is significantly lower than the classical one. It is pointed out that this scheme captures both Bernstein and Vazirani's inner-product protocol, as well as Grover's search algorithm. In the second part of the article we consider Paley's construction of Hadamard matrices, which relies on the properties of quadratic characters over finite fields. We design a query problem that uses the Legendre symbol χ (which indicates if an element of a finite field F _q is a quadratic residue or not). It is shown how for a shifted Legendre function f _s (i)=χ(i+s) , the unknown s ∈ F _q can be obtained exactly with only two quantum calls to f _s . This is in sharp contrast with the observation that any classical, probabilistic procedure requires more than log q + log ((1-ɛ )/2) queries to solve the same problem.     

Physical Limits on Self-Replication Processes

Using few very general axioms which should be satisfied by any reasonable theory consistent with the Second Law of Thermodynamics we argue that: a) “no-cloning theorem” is meaningful for a very general theoretical scheme including both quantum and classical models, b) in order to describe self-replication, Wigner’s “cloning” process should be replaced by a more general “broadcasting”, c) “separation of species” is possible only in a non-homogeneous environment, d) “parent” and “offspring” must be strongly correlated. Motivated by the existing results on broadcasting which show that only classical information can self-replicate perfectly we discuss briefly a classical toy model with “quantum features” — overlapping pure states and “entangled states” for composite systems.     

Continuous-time quantum walks on semi-regular spidernet graphs via quantum probability theory

We analyze continuous-time quantum and classical random walk on spidernet lattices. In the framework of Stieltjes transform, we obtain density of states, which is an efficiency measure for the performance of classical and quantum mechanical transport processes on graphs, and calculate the spacetime transition probabilities between two vertices of the lattice. Then we analytically show that there are two power law decays ∼ t ⁻³ and ∼ t ^−1.5 at the beginning of the transport for transition probability in the continuous-time quantum and classical random walk, respectively. This results illustrate the decay of quantum mechanical transport processes is quicker than that of the classical one. Due to the result, the characteristic time t _c , which is the time when the first maximum of the probabilities occur on an infinite graph, for the quantum walk is shorter than that of the classical walk. Therefore, we can interpret that the quantum transport speed on spidernet is faster than that of the classical one. In the end, we investigate the results by numerical analysis for two examples.     

Real space process algebra

The real time process algebra of Baeten and Bergstra [Formal Aspects of Computing,3, 142–188 (1991)] is extended to real space by requiring the presence of spatial coordinates for each atomic action, in addition to the required temporal attribute. It is found that asynchronous communication cannot easily be avoided. Based on the state operators of Baeten and Bergstra [Information and Computation,78, 205–245 (1988)] and following Bergstra et al. [Proc. Seminar on Concurrency, LNCS 197, Springer, 1985, pp. 76–95], asychronous communication mechanisms are introduced as an additional feature of real space process algebra. The overall emphasis is on the introductory explanation of the features of real space process algebra, and characteristic examples are given for each of these.     

On the Interpretation of Energy as the Rate of Quantum Computation

Over the last few decades, developments in the physical limits of computing and quantum computing have increasingly taught us that it can be helpful to think about physics itself in computational terms. For example, work over the last decade has shown that the energy of a quantum system limits the rate at which it can perform significant computational operations, and suggests that we might validly interpret energy as in fact being the speed at which a physical system is “computing,” in some appropriate sense of the word. In this paper, we explore the precise nature of this connection. Elementary results in quantum theory show that the Hamiltonian energy of any quantum system corresponds exactly to the angular velocity of state-vector rotation (defined in a certain natural way) in Hilbert space, and also to the rate at which the state-vector’s components (in any basis) sweep out area in the complex plane. The total angle traversed (or area swept out) corresponds to the action of the Hamiltonian operator along the trajectory, and we can also consider it to be a measure of the “amount of computational effort exerted” by the system, or effort for short. For any specific quantum or classical computational operation, we can (at least in principle) calculate its difficulty, defined as the minimum effort required to perform that operation on a worst-case input state, and this in turn determines the minimum time required for quantum systems to carry out that operation on worst-case input states of a given energy. As examples, we calculate the difficulty of some basic 1-bit and n-bit quantum and classical operations in an simple unconstrained scenario     

N-qubit quantum teleportation, information splitting and superdense coding through the composite GHZ–Bell channel

We introduce a general odd qubit entangled system composed of GHZ and Bell pairs and explicate its usefulness for quantum teleportation, information splitting and superdense coding. After demonstrating the superdense coding protocol on the five qubit system, we prove that ‘2N + 1’ classical bits can be sent by sending ‘N + 1’ quantum bits using this channel. It is found that the five-qubit system is also ideal for arbitrary one qubit and two qubit teleportation and quantum information splitting (QIS). For the single qubit QIS, three different protocols are feasible, whereas for the two qubit QIS, only one protocol exists. Protocols for the arbitrary N-qubit state teleportation and quantum information splitting are then illustrated.     

Partial decoherence of histories and the Diósi test

In the decoherent histories approach to quantum theory, attention focuses on the conditions under which probabilities may be assigned to sets of quantum histories. A variety of conditions have been proposed, but the most important one is decoherence, which means that the interference between every pair of histories in the set is zero. Weaker conditions have been considered, such as consistency, or linear positivity, but these are ruled out by the requirement of consistent composition of subsystems, proposed by Diósi. Here we propose a new condition which we call partial decoherence, and is the requirement that every history has zero interference with its negation. This is weaker than decoherence and stronger than linear positivity (but its relation to consistency is less simply defined—it is neither stronger nor weaker). Most importantly, it satisfies the Diósi condition. A strengthened Diósi condition is proposed, which partial decoherence narrowly fails, due to an unusual property of inhomogeneous histories. In an appendix an example is given of a set of histories which are consistent but not decoherent.     

Geometric Factors in Electromagnetic Field Commutators and the Quantum Information Control of Vacuum Fluctuations

The electromagnetic field commutation relations are defined in terms of geometric factors that are double averages over two finite four-dimensional space-time regions. The square root of any of the uncertainty relations derived from the aforementioned commutators is taken as a critical field, in the sense that any electromagnetic field much larger than it can be treated as classical. Another critical electromagnetic field associated with the quantum information control of vacuum fluctuations can be chosen as the square root of the mean quadratic fluctuation of each quantity of electromagnetic field, when the number of photons is defined and is equal to zero. Any electromagnetic field expectation value could be measured if it is much greater than the last critical field. This article covers a magnitude order comparison between the critical fields and its consequences for measuring the electromagnetic field information. Presented at the 38th Symposium on Mathematical Physics “Quantum Entanglement & Geometry”, Toruń, June 4-7, 2006.     

Experimental Concatenation of Quantum Error Correction with Decoupling

We experimentally explore the reduction of decoherence via concatenating quantum error correction (QEC) with decoupling in liquid-state NMR quantum information processing. Decoupling provides an efficient means of suppressing decoherence from noise sources with long correlation times, and then QEC can be used more profitably for the remaining noise sources. PACS: 03.67.Lx, 03.65.Bz     

Solutions of Multi-dimensional Hyperbolic Systems of Conservation Laws by Square Entropy Condition Satisfying Discontinuous Galerkin Method

In this paper, we study formally high-order accurate discontinuous Galerkin methods on general arbitrary grid for multi-dimensional hyperbolic systems of conservation laws [Cockburn, B., and Shu, C.-W. (1989, Math. Comput. 52, 411–435, 1998, J. Comput. Phys. 141, 199–224); Cockburn et al. (1989, J. Comput. Phys. 84, 90–113; 1990, Math. Comput. 54, 545–581). We extend the notion of E-flux [Osher (1985) SIAM J. Numer. Anal. 22, 947–961] from scalar to system, and found that after flux splitting upwind flux [Cockburn et al. (1989) J. Comput. Phys. 84, 90–113] is a Riemann solver free E-flux for systems. Therefore, we are able to show that the discontinuous Galerkin methods satisfy a cell entropy inequality for square entropy (in semidiscrete sense) if the multi-dimensional systems are symmetric. Similar result [Jiang and Shu (1994) Math. Comput. 62, 531–538] was obtained for scalar equations in multi-dimensions. We also developed a second-order finite difference version of the discontinuous Galerkin methods. Numerical experiments have been obtained with excellent results.      

The Quantum Setting with Randomized Queries for Continuous Problems

The standard setting of quantum computation for continuous problems uses deterministic queries and the only source of randomness for quantum algorithms is through measurement. Without loss of generality we may consider quantum algorithms which use only one measurement. This setting is related to the worst case setting on a classical computer in the sense that the number of qubits needed to solve a continuous problem must be at least equal to the logarithm of the worst case information complexity of this problem. Since the number of qubits must be finite, we cannot solve continuous problems on a quantum computer with infinite worst case information complexity. This can even happen for continuous problems with small randomized complexity on a classical computer. A simple example is integration of bounded continuous functions. To overcome this bad property that limits the power of quantum computation for continuous problems, we study the quantum setting in which randomized queries are allowed. This type of query is used in Shor’s algorithm. The quantum setting with randomized queries is related to the randomized classical setting in the sense that the number of qubits needed to solve a continuous problem must be at least equal to the logarithm of the randomized information complexity of this problem. Hence, there is also a limit to the power of the quantum setting with randomized queries since we cannot solve continuous problems with infinite randomized information complexity. An example is approximation of bounded continuous functions. We study the quantum setting with randomized queries for a number of problems in terms of the query and qubit complexities defined as the minimal number of queries/qubits needed to solve the problem to within ɛ by a quantum algorithm. We prove that for path integration we have an exponential improvement for the qubit complexity over the quantum setting with deterministic queries.     

Controlling quantum information processing in hybrid systems on chips

We investigate quantum information processing, transfer and storage in hybrid systems comprised of diverse blocks integrated on chips. Strong coupling between superconducting (SC) qubits and ensembles of ultracold atoms or NV-center spins is mediated by a microwave transmission-line resonator that interacts near-resonantly with the atoms or spins. Such hybrid devices allow us to benefit from the advantages of each block and compensate for their disadvantages. Specifically, the SC qubits can rapidly implement quantum logic gates, but are “noisy” (prone to decoherence), while collective states of the atomic or spin ensemble are “quiet”(protected from decoherence) and thus can be employed for storage of quantum information. To improve the overall performance (fidelity) of such devices we discuss dynamical control to optimize quantum state-transfer from a “noisy” qubit to the “quiet” storage ensemble. We propose to maximize the fidelity of transfer and storage in a spectrally inhomogeneous spin ensemble, by pre-selecting the optimal spectral portion of the ensemble. Significant improvements of the overall fidelity of hybrid devices are expected under realistic conditions. Experimental progress towards the realization of these schemes is discussed.