Sharp Quantum versus Classical Query Complexity Separations

Abstract. We obtain the strongest separation between quantum and classical query complexity known to date—specifically, we define a black-box problem that requires exponentially many queries in the classical bounded-error case, but can be solved exactly in the quantum case with a single query (and a polynomial number of auxiliary operations). The problem is simple to define and the quantum algorithm solving it is also simple when described in terms of certain quantum Fourier transforms (QFTs) that have natural properties with respect to the algebraic structures of finite fields. These QFTs may be of independent interest, and we also investigate generalizations of them to noncommutative finite rings.     

Quantum implicit computational complexity

We introduce a quantum lambda calculus inspired by Lafont’s Soft Linear Logic and capturing the polynomial quantum complexity classes EQP, BQP and ZQP. The calculus is based on the “classical control and quantum data” paradigm. This is the first example of a formal system capturing quantum complexity classes in the spirit of implicit computational complexity — it is machine-free and no explicit bound (e.g., polynomials) appears in its syntax.     

Quantum and Classical Query Complexities of Local Search Are Polynomially Related

Let f be an integer valued function on a finite set V. We call an undirected graph G(V,E) a neighborhood structure for f. The problem of finding a local minimum for f can be phrased as: for a fixed neighborhood structure G(V,E) find a vertex x∈V such that f(x) is not bigger than any value that f takes on some neighbor of x. The complexity of the algorithm is measured by the number of questions of the form “what is the value of f on x?” We show that the deterministic, randomized and quantum query complexities of the problem are polynomially related. This generalizes earlier results of Aldous (Ann. Probab. 11(2):403–413, [1983]) and Aaronson (SIAM J. Comput. 35(4):804–824, [2006]) and solves the main open problem in Aaronson (SIAM J. Comput. 35(4):804–824, [2006]).     

The Quantum Black-Box Complexity of Majority

   Abstract. We describe a quantum black-box network computing the majority of N bits with zero-sided error ɛ using only

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.     

量子计算机的研究与应用

介绍了量子计算的最新研究方向,简述了量子计算和量子信息技术在保密通信、量子算法、数据库搜索等重要领域的应用。分析了量子计算机与经典计算机相比所具有的优点和目前制约量子计算机应用发展的主要因素,最后展望了其未来发展趋势。     

Space Complexity Vs. Query Complexity

Combinatorial property testing deals with the following relaxation of decision problems: Given a fixed property and an input x, one wants to decide whether x satisfies the property or is “far” from satisfying it. The main focus of property testing is in identifying large families of properties that can be tested with a certain number of queries to the input. In this paper we study the relation between the space complexity of a language and its query complexity. Our main result is that for any space complexity s(n) ≤ log n there is a language with space complexity O(s(n)) and query complexity 2^Ω(s(n)). Our result has implications with respect to testing languages accepted by certain restricted machines. Alon et al. [FOCS 1999] have shown that any regular language is testable with a constant number of queries. It is well known that any language in space o(log log n) is regular, thus implying that such languages can be so tested. It was previously known that there are languages in space O(log n) that are not testable with a constant number of queries and Newman [FOCS 2000] raised the question of closing the exponential gap between these two results. A special case of our main result resolves this problem as it implies that there is a language in space O(log log n) that is not testable with a constant number of queries. It was also previously known that the class of testable properties cannot be extended to all context-free languages. We further show that one cannot even extend the family of testable languages to the class of languages accepted by single counter machines.      

Quantum computation, quantum theory and AI

The main purpose of this paper is to examine some (potential) applications of quantum computation in AI and to review the interplay between quantum theory and AI. For the readers who are not familiar with quantum computation, a brief introduction to it is provided, and a famous but simple quantum algorithm is introduced so that they can appreciate the power of quantum computation. Also, a (quite personal) survey of quantum computation is presented in order to give the readers a (unbalanced) panorama of the field. The author hopes that this paper will be a useful map for AI researchers who are going to explore further and deeper connections between AI and quantum computation as well as quantum theory although some parts of the map are very rough and other parts are empty, and waiting for the readers to fill in.     

Unbounded-error quantum query complexity

This work studies the quantum query complexity of Boolean functions in an unbounded-error scenario where it is only required that the query algorithm succeeds with a probability strictly greater than 1/2. We show that, just as in the communication complexity model, the unbounded-error quantum query complexity is exactly half of its classical counterpart for any (partial or total) Boolean function. Moreover, connecting the query and communication complexity results, we show that the “black-box” approach to convert quantum query algorithms into communication protocols by Buhrman-Cleve—Wigderson [STOC’98] is optimal even in the unbounded-error setting.We also study a related setting, called the weakly unbounded-error setting, where the cost of a query algorithm is given by q+log(1/2(p−1/2)), where q is the number of queries made and p>1/2 is the success probability of the algorithm. In contrast to the case of communication complexity, we show a tight multiplicative Θ(logn) separation between quantum and classical query complexity in this setting for a partial Boolean function. The asymptotic equivalence between them is also shown for some well-studied total Boolean functions.     

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.     

An Explicit Universal Gate-Set for Exchange-Only Quantum Computation

A single physical interaction might not be universal for quantum computation in general. It has been shown, however, that in some cases it can achieve universal quantum computation over a subspace. For example, by encoding logical qubits into arrays of multiple physical qubits, a single isotropic or anisotropic exchange interaction can generate a universal logical gate-set. Recently, encoded universality for the exchange interaction was explicitly demonstrated on three-qubit arrays, the smallest nontrivial encoding. We now present the exact specification of a discrete universal logical gate-set on four-qubit arrays. We show how to implement the single qubit operations exactly with at most 3 nearest neighbor exchange operations and how to generate the encoded controlled-NOT with 27 parallel nearest neighbor exchange interactions or 50 serial gates, obtained from extensive numerical optimization using genetic algorithms and Nelder–Mead searches. We also give gate-switching times for the three-qubit encoding to much higher accuracy than previously and provide the full speci.cation for exact CNOT for this encoding. Our gate-sequences are immediately applicable to implementations of quantum circuits with the exchange interaction. PACS: 03.67.Lx, 03.65.Ta, 03.65.Fd, 89.70.+c     

Toward a Complexity of Online Learning: Learners in Online First-Year Writing

In response to the growing presence of online first-year writing courses, this paper describes a case study of two online first-year writing courses and addresses the questions: What do students in an online first-year writing course perceive as good study habits, and what helps them succeed? Data includes surveys, online discussions, course management statistics, and selected interviews. The study is supported by social cognitive theory described by psychologist Albert Bandura; this methodology allows for examination of internal, external, and behavioral characteristics of participating students. Results of the study indicate that students who rated themselves as making good use of study time also succeeded in the course. Insights from students include information about study activities, management of study time, access to technology, and attitudes about online courses. A surprising result of the study was that students did not consider communication with peers as a productive study activity, despite a deliberate attempt by instructors to build peer interaction into the course. Yet students also reported high levels of engagement and positive attitudes about online learning. The social cognitive lens provides helpful insights about these complex findings by examining the external, internal, and behavioral aspects of online first-year writing students in this study.     

Grover量子搜索算法的仿真实现

利用核磁共振(NMR)实验技术来实现量子计算,是当前各种验证量子算法最为有效的方法之一,但这个方法首先必须把量子算法编译成在现代超导核磁共振谱仪上能够直接执行的NMR脉冲序列,即NMR量子计算程序。在NMR技术中通常只要施加合适的射频脉冲,便可以达到使核自旋翻转以实现某种逻辑功能的目的,该文讨论了如何设计多量子位核磁共振(NMR)脉冲序列来实现Grower量子搜索算法,并在量子仿真器(QCE)上进行了实验验证。     

When Online Dating Partners Meet Offline: The Effect of Modality Switching on Relational Communication Between Online Daters

Despite the popularity of online dating sites, little is known about what occurs when online dating partners choose to communicate offline. Drawing upon the modality switching perspective, the present study assessed a national sample of online daters to determine whether face‐to‐face (FtF) relational outcomes could be predicted by the amount of online communication prior to the initial FtF meeting. Results were consistent with the hypothesized curvilinear relationship between the amount of online communication and perceptions of relational messages (intimacy, composure, informality, social orientation), forecasts of the future of the relationship, and information seeking behavior when meeting their partner FtF. The results provide support for the modality switching perspective, and offer important insight for online daters.     

Nonadaptive quantum query complexity

We study the power of nonadaptive quantum query algorithms, which are algorithms whose queries to the input do not depend on the result of previous queries. First, we show that any bounded-error nonadaptive quantum query algorithm that computes a total boolean function depending on n variables must make Ω(n) queries to the input in total. Second, we show that, if there exists a quantum algorithm that uses k nonadaptive oracle queries to learn which one of a set of m boolean functions it has been given, there exists a nonadaptive classical algorithm using queries to solve the same problem. Thus, in the nonadaptive setting, quantum algorithms for these tasks can achieve at most a very limited speed-up over classical query algorithms.     

Quantum lower bounds for the Goldreich-Levin problem

At the heart of the Goldreich-Levin theorem is the problem of determining an n-bit string a by making queries to two oracles, referred to as IP (inner product) and EQ (equivalence). The IP oracle, on input x, returns a bit that is biased towards a⋅x (the modulo two inner product of a with x) in the following sense. For a random x, the probability that IP(x)=a⋅x is at least . The EQ oracle, on input x, returns a bit specifying whether or not x=a. It has been shown that a quantum algorithm can solve this problem with O(1/?) IP and EQ queries, whereas any classical algorithm requires Ω(n/?²) such queries. Also, the quantum algorithm requires only O(n/?) auxiliary one- and two-qubit gates in addition to its queries. We show that the above quantum algorithm is optimal in terms of both EQ and IP queries. Specifically, Ω(1/?) EQ queries are necessary, and Ω(1/?) IP queries are necessary if the number of EQ queries is .     

一种新的自适应量子遗传算法

现有基于 Bloch 球面坐标的量子进化算法存在收敛速度慢和鲁棒性不稳定的问题。为此,提出基于斐波那契特性更新的自适应量子遗传算法。在最优解的搜索过程中,考虑目标函数在搜索点的变化率,建立自适应因子λ,反映搜索点处目标适应度值相对于相邻两代最佳目标函数值一阶差分的变化,调整λ以改善算法收敛的方向和速度。分析量子旋转门转角步长调整策略,建立基于斐波那契数列特性的转角步长函数Δφ和Δθ的更新规则。应用该算法求解多维复杂函数的极值优化问题,时间复杂度理论分析和仿真结果证明,该算法在收敛速度、效率和稳定鲁棒性等方面均有明显改善。