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.     

Packing问题的计算复杂性

本文讨论了离散模型与连续问题的关系以及图灵机的计算能力,在此基础上扩充了问题及NP完全问题的定义,根据解空间的拓扑结构特点将NP完全的Packing问题分为三类,并对多边形Packing问题进行了有益的探讨。这对设计Packing问题的求解算法具有借鉴意义。     

多参数最小支撑树问题的复杂性和算法

建立了多参数最小支撑树问题（ＲＭＳＴ）的模型,并证明该问题是ＮＰ－完全的。利用经典Ｇｒｅｅｄｙ算法,给出了该问题的一个近似算法,并分析了该近似算法的性能比,证明了所给出的界是紧的。     

Treating the Independent Set Problem by 2D Ising Interactions with Adiabatic Quantum Computing

We construct a nearest-neighbor interaction whose ground states encode the solutions to the NP-complete problem independent set for cubic planar graphs. The important difference to previously used Hamiltonians in adiabatic quantum computing is that our Hamiltonian is spatially local. Due to its special structure our Hamiltonian can be easily simulated by Ising interactions between adjacent particles on a 2D rectangular lattice. We describe the required pulse sequences. Our methods could help to implement adiabatic quantum computing by physically reasonable Hamiltonians like short-range interactions. Therefore, this universal resource Hamiltonian can be used for different graphs by applying suitable control operations. This is in contrast to a previous proposal where the Hamiltonians have to be wired in hardware for each graph. PACS: 03.67.Lx     

Natural Majorization of the Quantum Fourier Transformation in Phase-Estimation Algorithms

We prove that majorization relations hold step by step in the Quantum Fourier Transformation (QFT) for phase-estimation algorithms. Our result relies on the fact that states which are mixed by Hadamard operators at any stage of the computation only differ by a phase. This property is a consequence of the structure of the initial state and of the QFT, based on controlled-phase operators and a single action of a Hadamard gate per qubit. The detail of our proof shows that Hadamard gates sort the probability distribution associated to the quantum state, whereas controlled-phase operators carry all the entanglement but are immaterial to majorization. We also prove that majorization in phase-estimation algorithms follows in a most natural way from unitary evolution, unlike its counterpart in Grover's algorithm. PACS: 03.67.-a, 03.67.Lx     

P vs. NP问题研究状态及其对密码学的意义

介绍P vs.NP问题的研究状态以及P vs.NP问题的研究对于密码学的意义。主要内容包括关于证明P≠NP的主要研究方法和相关工作,关于证明P=NP的主要研究方法和相关工作,关于求解NP完全问题的相关方法,以及P vs.NP问题研究与密码学的关系。由于现代密码学建立在未知密钥情况下不存在有效的算法将明文消息从密文中提取出来的假定之上,因此安全加密算法存在的一个必要条件是P≠NP。如果P=NP,根据Cook的观点,现代密码体制将崩溃。依据P=NP的假定,给出一个可能的密码分析模型。     

Random Measurement Bases,Quantum State Distinction and Applications to the Hidden Subgroup Problem

We show that measuring any two low rank quantum states in a random orthonormal basis gives, with high probability, two probability distributions having total variation distance at least a universal constant times the Frobenius distance between the two states. This implies that for any finite ensemble of quantum states there is a single POVM that distinguishes between every pair of states from the ensemble by at least a constant times their Frobenius distance; in fact, with high probability a random POVM, under a suitable definition of randomness, suffices. There are examples of ensembles with constant pairwise trace distance where a single POVM cannot distinguish pairs of states by much better than their Frobenius distance, including the important ensemble of coset states of hidden subgroups of the symmetric group (Moore et al., Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 2005).We next consider the random Fourier method for the hidden subgroup problem (HSP) which consists of Fourier sampling the coset state of the hidden subgroup using random orthonormal bases for the group representations. In cases where every representation of the group has polynomially bounded rank when averaged over the hidden subgroup, the random Fourier method gives a POVM for the HSP operating on one coset state at a time and using totally a polynomial number of coset states. In particular, we get such POVMs whenever the group and the hidden subgroup form a Gel’fand pair, e.g., Abelian, dihedral and Heisenberg groups. This gives a positive counterpart to earlier negative results about random Fourier sampling when the above rank is exponentially large (Grigni et al., Combinatorica 24(1):137–154, 2004), which happens for example in the HSP in the symmetric group.     

网络编码中的优化问题研究

简要回顾了网络编码的理论研究,阐述了网络编码优化问题研究的重要意义.在介绍网络信息流模型的基础上,针对优化问题的陈述、特点和解法,结合最新的研究成果进行了综述.根据优化目标的不同,优化问题可分成4类:最小花费组播,无向网络的最大吞吐率,最小编码节点、编码边,基于网络编码的网络拓扑设计.归纳了问题的求解性质,对其中的(线性或凸)规划问题总结了求解的一般方法,对NP完全问题讨论了最新的启发式算法及其设计难点.同时,展望了未来的发展方向.     

The Dirichlet and Neumann Problems for Elliptical Equations with Conjugation Conditions and High-Precision Algorithms of Their Discretization

New Dirichlet and Neumann boundary-value problems for elliptic equations with conjugation conditions are considered and existence and uniqueness of their solutions are studied. High-precision discretization algorithms are constucted based on the classes of discontinuous admissible functions.     

Quantum effects and Haldane gap in magnetic chains with alternating anisotropy axes

The isotropic quantum Heisenberg model with alternating uniaxial anisotropy axes is analyzed numerically by the density-matrix renormalization-group (DMRG) method. In the classical version, the model is applied to describe the magnetic properties of the S=2 zigzag chain containing Mn(III) acetate meso-tetraphenylporphyrin complexes coupled by the phenylphosphinate ligands which transmit antiferromagnetic interactions. Although the tensors representing the uniaxial magnetic anisotropy D and g factors are non-diagonal in the global coordination system, the DMRG approach has been successfully applied to this complex model in the entire temperature region studied. The predictions of our quantum approach are compared to those previously obtained from the classical one and the importance of quantum effects for analysis of the single-crystal susceptibility and magnetization is demonstrated. At low temperatures the magnetization in the field applied along the c direction increases much more slowly than the classical counterpart. The magnetization behavior is very sensitive to temperature. Moreover, the presence of a magnetization jump in the limit T→0 at the field H=3.8 Tesla can be an indication of the Haldane gap of the order of 10.2 K. The considerable differences are demonstrated for the temperature dependent single-crystal susceptibilities, but surprisingly they disappear after averaging over the three crystallographic directions which has not been reported before.     

多机相关任务均匀衡调度问题的复杂性与新算法

本文讨论了多处理机系统中的一种相关任务均衡调度问题 ,证明了该问题是 NP完全问题 ,并给出了一个新的启发式算法。该算法克服了现有算法的不足。数值实例和仿真结果表明 ,该算法有令人满意的优化效果     

The Setting of Shelf Heights and the Distribution of Box Sizes in Two-dimensional Shelf Packing

In this paper we explore two factors which have been relatively neglected in the study of shelf packing algorithms. Boxes arrive one by one at a bin that is shelved over its width and are placed into the shelves side by side, left-justified. We consider the setting of the shelf heights, which needs to be decided upon before packing starts. We investigate the relationship between the number of boxes to be packed and the number of shelf heights that leads to minimal space wastage in the resulting packings. We also consider the distribution of the box sizes, for which we distinguish three types: (a) the continuous uniform distribution U(0, 1); (b) the discrete uniform distribution where M sizes {1/M, 2/M,……,1} have equal probability of being chosen; and (c) an alternative discrete uniform distribution where M sizes {s₁, s₂,……,s_M} are drawn from U(0, 1), which then each have equal probability of being chosen. In simulation studies we illustrate important differences between the three types of distribution.     

The Equivalence between Ordinal Optimization in Deterministic Complex Problems and in Stochastic Simulation Problems

In the last decade ordinal optimization (OO) has been successfully applied in many stochastic simulation-based optimization problems (SP) and deterministic complex problems (DCP). Although the application of OO in the SP has been justified theoretically, the application in the DCP lacks similar analysis. In this paper, we show the equivalence between OO in the DCP and in the SP, which justifies the application of OO in the DCP. Acknowledgment of Financial Support This work was supported by ARO contract DAAD19-01-1-0610, AFOSR contract F49620-01-1-0288, NSF grant ECS-0323685, NSFC Grant No.60274011 and the NCET (No.NCET-04-0094) program of China.     

The One-Machine Problem with Earliness and Tardiness Penalties

We address the one-machine problem in which the jobs have distinct due dates, earliness costs, and tardiness costs. In order to determine the minimal cost of such a problem, a new lower bound is proposed. It is based on the decomposition of each job in unary operations that are then assigned to the time slots, which gives a preemptive schedule. Assignment costs are defined so that the minimum assignment cost is a valid lower bound. A branch-and-bound algorithm based on this lower bound and on some new dominance rules is experimentally tested.     

石油传输网络最少增压器问题的回溯与分支限界解法

回溯法和分支限界法是用于解决诸多问题的重要而有效的方法。本文首先提出石油传输网络中的最少增压器问题,然后介绍了基于回溯法和分支限界法的两种有效算法,最后对这两种算法进行了比较和讨论。实验结果验证了算法的有效性。     

The Preliminary Study of Problem Equation in Complex System Based on All Set Theory and Extenics

This paper introduces All Set Theory and a mathematical tool used for intelligent applications, and applies this method to establish models in complex systems. Furthermore, problem equation based on All Set Theory is put forward, and the application of Extensible Forces as well as its transformation to solve problem equation is expounded in this paper. At last, the program flow chart and application example are presented. It shows that intelligent methods are useful when they are used to settle the complex system.     

互联网信息三级巡控体系的构建

随着互联网的迅猛发展,互联网信息在给人们生活工作带来了便利快捷的同时,也对互联网管理部门的管理提出了系列问题与挑战。为应对挑战文章提出有效开展互联网信息的三级巡控,对管理部门加强虚拟社会和现实社会的管理具有重要意义。但目前管理部门对于推行互联网信息三级巡控的应对不足,存在诸多问题,急需从理念、机制、管理、制度、措施、保障等多方面去系统科学地建立健全互联网信息的三级巡控体系。     

我国农业投资中的问题浅析及对策建议

本文从农业生产的基本特征出发,分析了我国农业投资的现状,挖掘其存在的问题是：财政支农资金严重不足;农业投资环境差,农业的外资利用在逐年缩减;农业的比较利益低,农业资金的非农化倾向严重。提出了继续加大国家财政对农业的投资、培育新的投资主体、加强对农业资金的科学管理和建立农业投资的激励机制等对策建议。     

图像色偏的量化研究与应用

目前,国内外针对各种色彩I／O设备中图像色偏的量化的研究还比较薄弱,虽然有ICC色彩标准,但是没有一个独立于设备的图像色偏量化标准。本文试图提出一套独立于打机、印刷机等色彩设备的色偏量化体系与方法,通过该方法的应用可方便地实现不同种类的数码打样(印刷机打样,照排机打样,屏幕打样等)。随着色偏量化的深入研究与应用,业界通过主观经验进行色彩纠偏的做法将会成为历史。