On the Hitting Times of Quantum Versus Random Walks

The hitting time of a classical random walk (Markov chain) is the time required to detect the presence of—or equivalently, to find—a marked state. The hitting time of a quantum walk is subtler to define; in particular, it is unknown whether the detection and finding problems have the same time complexity. In this paper we define new Monte Carlo type classical and quantum hitting times, and we prove several relationships among these and the already existing Las Vegas type definitions. In particular, we show that for some marked state the two types of hitting time are of the same order in both the classical and the quantum case. Then, we present new quantum algorithms for the detection and finding problems. The complexities of both algorithms are related to the new, potentially smaller, quantum hitting times. The detection algorithm is based on phase estimation and is particularly simple. The finding algorithm combines a similar phase estimation based procedure with ideas of Tulsi from his recent theorem (Tulsi A.: Phys. Rev. A 78:012310 2008) for the 2D grid. Extending his result, we show that we can find a unique marked element with constant probability and with the same complexity as detection for a large class of quantum walks—the quantum analogue of state-transitive reversible ergodic Markov chains. Further, we prove that for any reversible ergodic Markov chain P, the quantum hitting time of the quantum analogue of P has the same order as the square root of the classical hitting time of P. We also investigate the (im)possibility of achieving a gap greater than quadratic using an alternative quantum walk. In doing so, we define a notion of reversibility for a broad class of quantum walks and show how to derive from any such quantum walk a classical analogue. For the special case of quantum walks built on reflections, we show that the hitting time of the classical analogue is exactly the square of the quantum walk.     

Layered Working-Set Trees

The working-set bound [Sleator and Tarjan in J. ACM 32(3), 652–686, 1985] roughly states that searching for an element is fast if the element was accessed recently. Binary search trees, such as splay trees, can achieve this property in the amortized sense, while data structures that are not binary search trees are known to have this property in the worst case. We close this gap and present a binary search tree called a layered working-set tree that guarantees the working-set property in the worst case. The unified bound [B?doiu et al. in Theor. Comput. Sci. 382(2), 86–96, 2007] roughly states that searching for an element is fast if it is near (in terms of rank distance) to a recently accessed element. We show how layered working-set trees can be used to achieve the unified bound to within a small additive term in the amortized sense while maintaining in the worst case an access time that is both logarithmic and within a small multiplicative factor of the working-set bound.     

ISS-Lyapunov functions for time-varying hyperbolic systems of balance laws

A family of time-varying hyperbolic systems of balance laws is considered. The partial differential equations of this family can be stabilized by selecting suitable boundary conditions. For the stabilized systems, the classical technique of construction of Lyapunov functions provides a function which is a weak Lyapunov function in some cases, but is not in others. We transform this function through a strictification approach to obtain a time-varying strict Lyapunov function. It allows us to establish asymptotic stability in the general case and a robustness property with respect to additive disturbances of input-to-state stability (ISS) type. Two examples illustrate the results.     

基于计算机视觉的果树害虫的形态特征分析

为解决农作物病虫害的诊断问题,选择京郊常见果树的三种害虫:桃蛀螟成虫、华北大黑鳃金龟成虫、桃六点天蛾,使用计算机视觉技术清除背景,获取该害虫的形状参数、偏心率等形态特征。通过判别分析,建立三种害虫形态特征的判别评分函数,并测试了该判别评分函数的有效性。实验结果表明,形状参数、偏心率、似圆度特征能反映这三种害虫的形态特点,可有效区分这三种害虫。     

Cognitive conflict in human-automation interactions: a psychophysiological study

The review of literature in sociology and distributed artificial intelligence reveals that the occurrence of conflict is a remarkable precursor to the disruption of multi-agent systems. The study of this concept could be applied to human factors concerns, as man-system conflict appears to provoke perseveration behavior and to degrade attentional abilities with a trend to excessive focus. Once entangled in such conflicts, the human operator will do anything to succeed in his current goal even if it jeopardizes the mission. In order to confirm these findings, an experimental setup, composed of a real unmanned ground vehicle, a ground station is developed. A scenario involving an authority conflict between the participants and the robot is proposed. Analysis of the effects of the conflict on the participants' cognition and arousal is assessed through heart-rate measurement (reflecting stress level) and eye-tracking techniques (index of attentional focus). Our results clearly show that the occurrence of the conflict leads to perseveration behavior and can induce higher heart rate as well as excessive attentional focus. These results are discussed in terms of task commitment issues and increased arousal. Moreover, our results suggest that individual differences may predict susceptibility to perseveration behavior.     

EDC/NHS交联胶原基牙周组织引导再生膜材料的研究

采用胶原材料制备了一种密实-疏松双层结构的牙周引导再生膜材料.为改善再生膜材料的物理化学性能,采用1-乙基-3-(3-二甲基氨丙基)碳二亚胺(EDC)和N-羟基琥珀酰亚胺(NHS)为交联剂对膜材料进行交联,考察了不同交联剂质量浓度对膜材料物理化学性能的影响,并通过差示扫描量热分析仪(DSC)、扫描电镜(SEM)、吸水率测试、膨胀动力学分析、抗酶解性能分析等手段对膜材料交联前后的结构与性能进行了研究.结果表明,以EDC/NHS为交联剂,在pH为5.5、EDC质量浓度为5 g/L、交联时间为24 h的条件下,引导再生胶原膜材料的综合性能达到最佳,进一步提高交联剂的浓度,材料物理化学性能的变化并不明显.采用EDC/NHS交联后,可显著改善再生膜材料的物理化学性能.交联后膜材料的变性温度和抗酶解性能显著提高,并且维持了密实-疏松的双层结构.     

3D动画在生物化学课程中的应用

针对生物化学课程内容抽象、枯燥,涉及到的化学反应和分子结构复杂等特点,对生物化学教学中多媒体3 D动画的制作、应用以及与传统教学的有机结合等进行了探讨。研究发现,在生物化学教学中恰当地使用3 D动画,能帮助学生改进思维方法,提高记忆力和学习效率,培养学生的形象思维和创新能力,从而达到提高教学质量的目的。     

New approaches for determining a common set of weights for a voting system

Data Envelopment Analysis (DEA) is one of the methods that have been proposed to determine the weights in a ranked voting system. DEA solves one model corresponding to each candidate and evaluates candidates with their own weights. However, sometimes solving only one model, and evaluating the candidates based on a common set of weights, is preferred. In this paper, some drawbacks of existing models are explained and new approaches for determining a common set of weights are proposed. Numerical examples are utilized to illustrate the content of the paper.