【摘 要】
:
量子信息论和计算经济学是算法和复杂性研究中两个新的热点,其中涉及的一些问题,例如量子算法下界问题,量子信息分辨问题,Nash均衡问题,拍卖定价问题等等,无论在理论上还是在
论文部分内容阅读
量子信息论和计算经济学是算法和复杂性研究中两个新的热点,其中涉及的一些问题,例如量子算法下界问题,量子信息分辨问题,Nash均衡问题,拍卖定价问题等等,无论在理论上还是在实际上都具有重要的意义。在本文中,我们研究了如下五个量子信息论和计算经济学中的算法和复杂性问题:1.针对量子算法下界问题,我们证明了对于任何图性质、轮换对称函数、弱对称函数,它们的量子查询复杂度下界至少是Ω( N1/4)。同时我们还给出了Scorpion图性质和一个轮换对称函数的例子,以及它们的量子算法,复杂度是O ( N1/4)。因此Ω( N1/4)的下界是最好的。2.借助另外一个量子纠缠态的帮助,一对量子纠缠态能够实现局部操作、经典通信下的转化。这一辅助状态被称作量子纠缠催化剂。本文给出了存在2×2量子态能够催化一对4×4量子态进行转化的充分必要条件(解析表达式);对一般的n×n的情况,我们给出了多项式时间的算法来判定能否催化转化。在我们之前[47]给出了一些必要条件,[6]提出了一个指数时间的算法。3.我们证明了量子状态的无错分辨问题在数学上等价于一个半正定规划问题,利用这一结果我们给出了一系列分辨效率的下界。4.我们推广了[29]对于Fisher市场均衡问题的研究,从线性模型推广到凹函数收益模型。我们给出了一个均衡价格下买卖双方的对偶定理,并利用对偶定理给出了买方或者卖方有界时计算均衡价格的多项式时间算法。5.我们研究了一类特殊的组合拍卖——single-minded拍卖。我们给出了匹配的通信复杂性上下界,证明了判定Walrasian均衡的存在性是NP难的,同时给出了Walrasian均衡的对偶定理。
其他文献
目的:观察泼尼松联合丙种球蛋白对重症肌无力(MG)患者外周血乙酰胆碱受体抗体(AChR-Ab)水平及转化生长因子-β1(TGF-β1)的影响。方法:选择94例MG患者为观察对象,按随机数表
氮氧化物是大气中主要的污染物之一,除了参与光化学烟雾和酸雨等环境污染事故之外,还可对人体健康造成威胁,控制氮氧化物的排放是实现可持续发展的必然要求之一。文章概括介
一、期刊简介《工程爆破》(ISSN 1006-7051;CN 11-3675/TD)(双月刊)1995年创刊,由汪旭光院士担任总编辑和编委会主任委员,由谢先启院士、杨仁树和卢文波教授担任编委会副主任
数学教学通过活动教学能够变抽象为形象,变复杂为简单,变难懂为易学,通过创建生动的活动素材,调动其主动学习的积极性;通过活动教学能活跃课堂气氛,加深巩固教学内容,使学生感受学习
大量实验已在受者体内成功诱导了混合嵌合体形成,且证实其较完全供者嵌合体具有更强的免疫力.混合嵌合状态下的供者特异性反应细胞的克隆消失,使移植物在受者体内得以长期存
民间糕饼印模是制作各色糕饼的模具,是随着民间饮食工艺历史而逐渐出现而多样的,饼印作为精致实用的民间工艺品,是民间增进邻里、亲朋感情的重要食品模具,也是民间传统礼俗文化的
初中物理课,是一门注重实验的自然科学基础课程,为了发挥物理实验的教学功能,使学生在教师的指导下,通过观察、实验、交流、讨论,使他们学习的主动性、积极性、求知欲得到充分发挥
<正>前言:司法公开下的大势所趋审判流程公开,作为司法公开"三大平台建设"~①的其中之一,经历了群众旁听、录音直播、电视直播、视频直播、微博直播再到累加发展的历程。目前
最近几年,从中小企业概念中剥离出一个新的概念,即小微企业。小微企业是我国国民经济的重要组成部分,其在多个方面发挥着积极的作用,比如为社会提供就业岗位、推动经济发展、
<正>一、被告故意逃避:民事诉讼"送达难"问题之核心症结通过对司法实践活动的观察和总结,我们不难发现,在整个诉讼程序中,原告扮演的是程序的启动者和推动者角色,往往是积极