• [量子计算]Shor算法

    秀尔算法(Shor’s algorithm)是一种非常著名的量子算法,甚至可以说是量子计算的一块金字招牌了。Shor’s algorithm可以在多项式时间内完成大整数质因数分解。所以Shor’s algorithm从诞生之时,就和以RSA算法为根基的加密技术形成了不可调和的矛盾。2001年,IBM的研究小组使用Shor’s algorithm完成了15 = 3×5这个整数分解运算 。时至今日,快20年过去了,量子计算机没有摧毁RSA。未来这一天来临的时候,希望我们已经准备好了。下图是,经典大数分解和秀尔算法的复杂度对比。

    Shor算法的整体流程

    完整的Shor算法是需要经典计算机和量子计算机协作完成的。其中量子计算机实现一个周期查找的函数,经典计算机负责整个算法流程的控制,以及调用量子算法。

    首先、还是表达一下Shor’s … 【查看更多】

  • [量子计算]量子搜索Grover算法

    搜索算法是最常用的一类算法了,然而传统计算机对非结构化数据的搜索其实是比较低效的。一般情况下,算法复杂度为\Omicron(N)N为数据规模。而量子计算机中存在着量子搜索算法,也称为Grover’s算法,它的时间复杂度是\Omicron(\sqrt N)。听起来似乎提升不是非常大,然而在数据规模较大的情况下,量子搜索算法的优越性还是非常惊人的。例如,用Grover算法破解通用的56位加密标准(DES),只需要2^{28} \approx2.68 * 10^{8} 步,而经典算法则需要2^{55} \approx3.6 * 10^{16} 。如果每秒钟计算十亿次,则经典计算需要11年,而量子算法则只需要3秒钟【参考北大物理学院讲义】。

    1、 Grover算法理论基础

    Grover’s算法的基本思路其实非常容易理解,而且存在非常直观的可视化解释(这一点是非常棒的!)。Grover… 【查看更多】

  • [量子计算]相位估计算法

    本文出自:【InTheWorld的博客】 (欢迎留言、交流)

    量子相位估计算法

    量子相位估计算法(Quantom Phase Estimation)也称作量子特征值估计算法,是一个比较基本的算法。它的作用直观说来就是来估计一个酉变换的特征值。由于酉矩阵拥有一个性质:酉矩阵的特征值都是模为1的复数。所以对酉矩阵而言,其特征值和相位基本是对等的(因为模长已经确定了)。

    量子傅里叶变换

    在量子相位估计算法中,需要使用到量子傅里叶反变换。因此,我们简单了解一下量子傅里叶变换的相关知识。经典的离散傅里叶变换作用于一个复向量(x_{0}, x_{1},\cdots,x_{N-1}),并把它映射到另一个向量(y_{0}, y_{1},\cdots,y_{N-1}),其映射关系如下:

    y_{k}=\frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} {x_{j}e^{-2\pi ijk/N}}【查看更多】

  • [量子计算] Deutsch-Jozsa算法原理与实现

    本文出自:【InTheWorld的博客】 (欢迎留言、交流)

    写在前面

    学习量子力学是几年前立的Flag了,一直没有真正投入时间。主要的原因还是“要吃饭”,而且一些层出不穷的新技术也有点迷惑了我。不过本质上还是自己科学品味太差,二来加上意志力不够坚定。目前已经花了一段时间学量子力学、量子信息,写在这里权当做笔记吧!

    Deutsch-Jozsa算法问题

    Deutsch-Jozsa是一个简单的量子算法例子。虽然从实用角度讲,这个算法意义不大,但是却能很好的体现量子计算的优越性。首先是问题的描述:

    考虑一个黑盒子,我们称为oracle。它可以计算一个比特的布尔函数。每做一次计算,我们就称为是
    对oracle的一次查询。对于这个函数,存在以下四种可能:

    输入 0 1 0 1
    输出 1 0 0 1

    第(1,4)列或者(2,3)列组合而成的情况,我们称oracle为常数函数;第(1,2)列,或者(3,4)列… 【查看更多】

  • LQR与汽车横向动力学

    本文出自:【InTheWorld的博客】 (欢迎留言、交流)

    LQR (linear quadratic regulator)即线性二次型调节器,这是一个非常常见的控制学科名词。以前学习《现代控制理论》的时候就有接触了,但由于最优控制这部分东西没有作为重点,所以没太掌握。但是自己心里知道《最优控制》是非常重要的,前面看强化学习Model Base部分的时候也同时买了本胡寿松版的《最优控制》。

    从个人的学习过程来看,LQR还是挺多种情况的。不少人(甚至是一些书籍的作者)都没把LQR的各种情况搞清楚。首先,LQR有离散形式和连续形式。一般来说教科书上讲连续形式的较多,学过现代控制理论的同学大概都会觉得连续系统的证明和推导都更有理论美感,而离散形式则往往需要一些近似或者假设。而且连续系统在Matlab中也很好仿真。但在实际的工程中,基本都是使用离散形式,谁让现在是数字计算机的时代呢?… 【查看更多】

  • ROS之激光雷达

    激光雷达已经成为机器人标配了,ROS作为通用机器人系统也支持激光雷达数据。激光雷达产生的数据类型是sensor_msgs/LaserScansensor_msgs/PointCloud,或者是新的sensor_msgs/PointCloud2。对于我手头的这台Turtlebot3而言,LDS设备的数据类型是sensor_msgs/LaserScan。ROS中的传感器数据非常多,但是这些数据流常常需要同步,所以ROS定义了一个通用的数据头,各种数据都会带上这个header

    ROS header的数据结构

    类型Header包括多个字段。字段seq对应一个标识符,随着消息被发布,它会自动增加。字段stamp存储与数据相关联的时间信息。以激光扫描为例,stamp可能对应每次扫描开始的时间。字段frame_id存储与数据相关联的tf帧【查看更多】

  • 强化学习之Policy Gradient笔记

    本文出自:【InTheWorld的博客】 (欢迎留言、交流)

    Policy Gradient方法是强化学习中非常重要的方法。不同于基于最优价值的算法,Policy Gradient算法更着眼于算法的长期回报。策略梯度根据目标函数的梯度方向去寻找最优策略。策略梯度算法中,整个回合结束之后才会进行学习,所以策略梯度算法对全局过程有更好的把握。DeepMind的David Silver在深度学习讲座中这样评价基于策略的方法:
    Policy Based强化学习方法优点:
    – 收敛性好
    – 在高维和连续问题中比较有效
    – 能学习随机策略

    其缺点有:
    – 容易陷入局部最优
    – 评价一个策略比较低效

    基本理论

    从理论上讲,其实策略梯度其实是更容易理解的一种方法,毕竟我们对梯度下降再… 【查看更多】

  • 强化学习之DQN笔记

    之前的一次机器学习会议中,LeCun表示强化学习或者弱监督学习会是机器学习最重要的发展方向。相比于强监督学习,强化学习更符合人类的学习过程。AlphaGo已经向人类展示出了强化学习的强大,之前看OpenAI机器人和职业玩家solo Dota2游戏,AI的游戏水平强大到令人吃惊。

    Q-learning是一种比较常见的强化学习方法,其实现方式是通过一个表(Q-Table)存放状态S和行动A的reward。然而,Q-Table是有缺陷的,对于状态空间巨大的问题就显得无能为力了。为了解决这类问题,有人提出了使用深度神经网络来实现Q函数,这种方法就是deep QNetwork。使用DNN来表示Q函数与使用Q-Table还是有一些区别的,Q-Table实现了S, A =》reword的映射。而DQN中的深度神经网络实现的其实是S => [A]的映射,这里[A]就是【查看更多】

  • 简单分析ARCore和SceneForm

    本文出自:【InTheWorld的博客】 (欢迎留言、交流)

    arcore-hero-800x498

    从ARCore去年下半年发布到现在已经半年有余了。之前其实一直有点手痒,想玩玩AR应用开发。之前有参考一本书,玩过一个简单的基于OpenCV和OpenGL的AR应用,但的确太简陋了。然而之前ARCore只支持Pixel之类的亲儿子手机,所以一直没有机会把玩一下。前两周偶然发现mix2s已经支持ARCore了,所以就乘放假的机会玩玩demo,分析一下ARCore的应用开发。

    ARCore支持Java, C, Unity以及Unreal这几种开发方式。在最近的Java SDK中新增了SceneForm api来支持渲染。这确实是一个比较大的进步,毕竟裸写OpenGL还是有点麻烦的。本人没弄过Unity和Unreal这些渲染引擎,所以就从Java SceneForm的SDK入手了,毕竟比较熟悉(其实就是懒)。

    虽然前文废话已经说了不少,… 【查看更多】

  • 关于Fuchsia OS的一些思考

    fuchsia

    去年年中的时候,就听说了Fuchsia。不过当时也没特别关注,毕竟Google对OS的执念很重,一不开心就启动一个新的OS项目。这几天官方公布了Fuchsia的一部分文档,这个文档目前还不太全面,不过也能粗略了解一下Fuchsia吧!限于个人水平有限,博文不免会有错误,还望多多指教。

    一、“瞎掰向”分析

    对于顶级IT公司来说,“操作系统”一直是一个独特的东西。从正面看,操作系统意味着生态系统、用户粘性。所以OS成就了很多公司,Solaris之于Sun,Windows之于微软。然而成功背后总有很多失败,而做OS的风险非常之大,强如微软和Facebook,都在移动操作系统领域一败涂地。

    Google作为一个后来者,Andriod目前在移动市场的份额已经非常成功了。即使在美国,iOS【查看更多】