Nominal Reasoning Techniques in Coq: (Extended Abstract)

We explore an axiomatized nominal approach to variable binding in Coq, using an untyped lambda-calculus as our test case. In our nominal approach, alpha-equality of lambda terms coincides with Coq's built-in equality. Our axiomatization includes a nominal induction principle and functions for calculating free variables and substitution. These axioms are collected in a module signature and proved sound using locally nameless terms as the underlying representation. Our experience so far suggests that it is feasible to work from such axiomatized theories in Coq and that the nominal style of variable binding corresponds closely with paper proofs. We are currently working on proving the soundness of a primitive recursion combinator and developing a method of generating these axioms and their proof of soundness from a grammar describing the syntax of terms and binding.     

量子隐形传态的通用线路

EPR态作为最基本的量子纠缠态,在量子隐形传态中起着重要作用.研究适应任意类型EPR通道的单量子比特隐形传送通用线路,并推广到任意N比特量子隐形传送通用线路.首先设计出4种EPR态,分别作为量子通道的单比特量子隐形传态,通过分析EPR量子通道与量子操作门之间的关系,设计一种单比特通用线路;然后,设计两比特的标准量子隐形传态线路,并用Mathematica进行仿真验证线路的正确性,再把它推广到N比特量子隐形传送线路;最后,将单量子比特通用线路与N比特量子隐形传送线路进行融合,最终设计出任意N比特量子隐形传送通用线路.N粒子量子比特通用线路通过信息接受者进行带参数的幺正变换,其中,参数由制备出的EPR对类型确定,解决了因EPR制备中心出错导致的信息传送失败问题.     

量子逻辑电路中控制点失效错误的定位

确保可逆电路的正确性与可靠性,错误检测必不可少,错误定位难度更高.通过分析发现当可逆电路中规模为k的可逆门发生控制点失效时仅对2<'n-k>个输入向量的输出产生影响,据此给出了一种把当前错误集分成若干个子集的方法生成控制点失效错误定位树.传统的错误定位方法都是通过生成真值表和错误表来产生错误定位树;该方法不需要生成和存储真值表以及错误表就能够有效定位电路中控制点失效错误.与Rfault算法相比,空间复杂度和时间复杂度更小,算法效率更高,能应用于更大规模的电路.     

Implementing and Reasoning About Hash-consed Data Structures in Coq

We report on four different approaches to implementing hash-consing in Coq programs. The use cases include execution inside Coq, or execution of the extracted OCaml code. We explore the different trade-offs between faithful use of pristine extracted code, and code that is fine-tuned to make use of OCaml programming constructs not available in Coq. We discuss the possible consequences in terms of performances and guarantees.We use the running example of binary decision diagrams and then demonstrate the generality of our solutions by applying them to other examples of hash-consed data structures.     

Proof Reflection in Coq

We formalize natural deduction for first-order logic in the proof assistant Coq, using de Bruijn indices for variable binding. The main judgment we model is of the form d[:], stating that d is a proof term of formula under hypotheses it can be viewed as a typing relation by the Curry–Howard isomorphism. This relation is proved sound with respect to Coq's native logic and is amenable to the manipulation of formulas and of derivations. As an illustration, we define a reduction relation on proof terms with permutative conversions and prove the property of subject reduction.     

基于Hash表的量子可逆逻辑电路综合的快速算法

量子可逆逻辑电路是构建量子计算机的基本单元,通过量子门的级联与组合构成量子计算机,量子可逆逻辑电路的综合就是根据电路功能,以较小的量子代价自动构造量子可逆逻辑电路.结合可逆逻辑电路综合的多种算法,提出了一种新颖高效的量子电路综合算法,巧妙构造最小完备的Hash函数,可使用多种量子门,采用任意量子代价标准,以极高的效率生成最优的量子可逆逻辑电路.为实现量子电路综合的自动化,首次提出了利用量子线的置换自动构造各种量子门库的通用算法.采用国际同行认可的3变量可逆函数测试标准,该算法不仅能够生成全部最优电路,而且运行速度远远超过其他算法.实验结果表明,该算法按最小长度、最小代价标准综合电路的平均速度分别是目前最好结果的49.15倍、365.13倍.     

Improved Gap Estimates for Simulating Quantum Circuits by Adiabatic Evolution

We use elementary variational arguments to prove, and improve on, gap estimates which arise in simulating quantum circuits by adiabatic evolution. Partially supported by the National Science Foundation under Grant DMS-0314228 and by the National Security Agency and Advanced Research and Development Activity under Army Research Office contract number DAAD19-02-1-0065.     

Reasoning with Numeric and Symbolic Time Information

Representing and reasoning about time is fundamental in many applications of Artificial Intelligence as well as of other disciplines in computer science, such as scheduling, planning, computational linguistics, database design and molecular biology. The development of a domain-independent temporal reasoning system is then practically important. An important issue when designing such systems is the efficient handling of qualitative and metric time information. We have developed a temporal model, TemPro, based on the Allen interval algebra, to express and manage such information in terms of qualitative and quantitative temporal constraints. TemPro translates an application involving temporal information into a Constraint Satisfaction Problem (CSP). Constraint satisfaction techniques are then used to manage the different time information by solving the CSP. In order for the system to deal with real time applications or those applications where it is impossible or impractical to solve these problems completely, we have studied different methods capable of trading search time for solution quality when solving the temporal CSP. These methods are exact and approximation algorithms based respectively on constraint satisfaction techniques and local search. Experimental tests were performed on randomly generated temporal constraint problems as well as on scheduling problems in order to compare and evaluate the performance of the different methods we propose. The results demonstrate the efficiency of the MCRW approximation method to deal with under constrained and middle constrained problems while Tabu Search and SDRW are the methods of choice for over constrained problems.     

Improving Gate-Level Simulation of Quantum Circuits

Simulating quantum computation on a classical computer is a difficult problem. The matrices representing quantum gates, and the vectors modeling qubit states grow exponentially with an increase in the number of qubits. However, by using a novel data structure called the Quantum Information Decision Diagram (QuIDD) that exploits the structure of quantum operators, a useful subset of operator matrices and state vectors can be represented in a form that grows polynomially with the number of qubits. This subset contains, but is not limited to, any equal superposition of n qubits, any computational basis state, n-qubit Pauli matrices, and n-qubit Hadamard matrices. It does not, however, contain the discrete Fourier transform (employed in Shor's algorithm) and some oracles used in Grover's algorithm. We first introduce and motivate decision diagrams and QuIDDs. We then analyze the runtime and memory complexity of QuIDD operations. Finally, we empirically validate QuIDD-based simulation by means of a general-purpose quantum computing simulator QuIDDPro implemented in C++. We simulate various instances of Grover's algorithm with QuIDDPro, and the results demonstrate that QuIDDs asymptotically outperform all other known simulation techniques. Our simulations also show that well-known worst-case instances of classical searching can be circumvented in many specific cases by data compression techniques. PACS: 03.67.Lx, 03.65.Fd, 03.65.Vd, 07.05.Bx     

应用系统中身份认证建模及推理方法

逻辑推理是对身份认证进行形式化研究的重要手段,但现有研究成果主要集中在认证机制、认证协议等单个方面,并不考虑应用环境,通过引入身份认证域,对应用系统中身份认证进行形式化描述;在此基础上,提出一种基于谓词的身份认证建模及推理方法,包括7种谓词、8个推理规则和一种4步骤推理方法等,并对基于静态口令、动态口令和数字证书的身份认证模型进行实例分析.     

A case-study in algebraic manipulation using mechanized reasoning tools

In this article, two different mechanized reasoning tools (Coq and Isabelle/HOL) are used in order to prove some basic but significant properties extracted from a symbolic computation system called Kenzo. In particular, we focused on a property called ‘cancellation theorem’, which can be applied to the proof of the idempotence property of a differential morphism. This result is used as a case-study to compare the capabilities and styles of the two proof assistants. The conclusion of our comparison is that both tools are adequate to solve the case-study presented in this article in a rather similar way but depending on their specific styles. This research is part of a more general project devoted to increase the reliability of computer algebra systems for calculations in algebraic topology.     

Quantum secure circuit evaluation

In order to solve the problem of classical secure circuit evaluation, this paper proposes a quantum approach. In this approach, the method of inserting redundant entangled particles and quantum signature has been employed to strengthen the security of the system. Theoretical analysis shows that our solution is secure against classical and quantum attacks.     

Topological-Like Features in Diagrammatical Quantum Circuits

In this paper, we revisit topological-like features in the extended Temperley–Lieb diagrammatical representation for quantum circuits including the teleportation, dense coding and entanglement swapping. We describe these quantum circuits and derive characteristic equations for them with the help of topological-like operations. Furthermore, we comment on known diagrammatical approaches to quantum information phenomena from the perspectives of both tensor categories and topological quantum field theories. Moreover, we remark on the proposal for categorical quantum physics and information as described by dagger ribbon categories. The main results in this paper had been presented at the workshop “Cats, Kets and Cloisters” (Computing Laboratory, Oxford University, July 17–23, 2006). Categorical quantum physics and information is proposed as described by dagger ribbon categories. The functor between Abramsky and Coecke’s categorical quantum mechanics and the extended Temperley–Lieb categorical approach is recognized as the same type as those defining topological quantum field theories. On the one hand, fundamental objects in the physical world may be string-like (even brane-like) and satisfy the braid statistics. On the other hand, fundamental particles at the Planck energy scale (or quasi-particles of many-body systems) may obey the braid statistics and have an effective (or a new internal) degree of freedom called the “twist spin”. The name “categorical quantum physics and information” hereby refers to quantum physics and information which can be recast in terms of the language of categories. This is a simple and intuitional generalization of the name “categorical quantum mechanics”. The latter does not yet recognize conformal field theories, topological quantum field theories, quantum gravity and string theories which have been already described in the categorical framework by different research groups. Besides, the proposal categorical quantum physics and information is strongly motivated by the present study in quantum information phenomena and theory. It is aimed at setting up a theoretical platform on which both categorical quantum mechanics and topological quantum computing by Freedman, Larsen and Wang are allowed to stand.     

Spatial Reasoning About Points in a Multidimensional Setting

For n 1, we consider the possible relations between two points of the Euclidean space of dimension n. We define the n-point algebra on the pattern of the point algebra and the cardinal algebra. Generalizing the concept of convexity just as the one of preconvexity, we prove that the consistency problem of convex n-point networks is polynomial for n 1, whereas the consistency problem of preconvex n-point networks is NP-complete for n 3. We characterize a subset of the set of all preconvex relations: the set of all strongly preconvex relations, which contains the set of all convex relations. We demonstrate that the consistency problem of strongly preconvex n-point networks can be decided in polynomial time by means of the weak path-consistency method for all n 1. For n = 3 the set of all strongly preconvex relations is a maximal tractable subclass of the set of all n-point relations. Finally, we prove that the concept of strong preconvexity corresponds to the one of ORD-Horn representability.     

面向范例推理的软构件模型研究

软件构件模型的建立对于软件再工程的构件复用起着非常重要的作用。本文提出几种面向范例推理的软构件建模方法，这将更有利于软件再工程的构件复用。     

一维量子卷积计算

研究了一维信息编码为量子态后进行量子卷积计算的量子线路模型。基于量子图像表示和经典信息的卷积算法,设计出了一维量子卷积计算的量子线路结构,表明量子卷积计算可以以[O(n2)]的复杂度计算卷积。与经典卷积相比,量子卷积计算由于利用量子并行计算在计算速率上达到了指数级的加速,为量子卷积神经网络卷积层的设计实施作铺垫。     

Experimental Analysis of Numeric and Symbolic Constraint Satisfaction Techniques for Temporal Reasoning

Many temporal applications like planning and scheduling can be viewed as special cases of the numeric and symbolic temporal constraint satisfaction problem. Thus we have developed a temporal model, TemPro, based on the interval Algebra, to express such applications in term of qualitative and quantitative temporal constraints. TemPro extends the interval algebra relations of Allen to handle numeric information. To solve a constraint satisfaction problem, different approaches have been developed. These approaches generally use constraint propagation to simplify the original problem and backtracking to directly search for possible solutions. The constraint propagation can also be used during the backtracking to improve the performance of the search. The objective of this paper is to assess different policies for finding if a TemPro network is consistent. The main question we want to answer here is how much constraint propagation is useful for finding a single solution for a TemPro constraint graph. For this purpose, we have experimented by randomly generating large consistent networks for which either arc and/or path consistency algorithms (AC-3, AC-7 and PC-2) were applied. The main result of this study is an optimal policy combining these algorithms either at the symbolic (Allen relation propagation) or at the numerical level.