We show how to translate a subset of RISC-V machine code compiled from a subset of C to quadratic unconstrained binary optimization (QUBO) models that can be solved by a quantum annealing machine: given a bound $n$, there is input $I$ to a program $P$ such that $P$ runs into a given program state $E$ executing no more than $n$ machine instructions if and only if the QUBO model of $P$ for $n$ evaluates to 0 on $I$. Thus, with more qubits on the machine than variables in the QUBO model, quantum annealing the model reaches 0 (ground) energy in constant time with high probability on some input $I$ that is part of the ground state if and only if $P$ runs into $E$ on $I$ in no more than $n$ instructions. Translation takes $\mathcal{O}(n^2)$ time turning a quantum annealer into a polynomial-time symbolic execution engine and bounded model checker, eliminating their path and state explosion problems. Here, we take advantage of the fact that any machine instruction may only increase the size of the program state by $\mathcal{O}(w)$ bits where $w$ is machine word size. Translation time comes down to $\mathcal{O}(n)$ if memory consumption of $P$ is bounded by a constant, establishing a linear (quadratic) upper bound on quantum space, in number of qubits, in terms of algorithmic time (space) in classical computing. The generated QUBO models only have $\mathcal{O}(2^w\cdot n^2)$ solutions out of $\mathcal{O}(2^{n^2})$ choices and only require $\mathcal{O}(wn)$ attempts to find a solution on a quantum machine. The construction motivates a temporal and spatial metric of quantum advantage and provides a non-relativizing argument for $NP\subseteq BQP$ effectively utilizing the optimality of Grover's algorithm. Our prototypical open-source toolchain translates machine code that runs on real RISC-V hardware to models that can be solved by real quantum annealing hardware, as shown in our experiments.


翻译:我们展示如何将从 C 子集中编译的 RISC- V 机器代码子集( $P$ ) 转换成 QUB 模型中比变量多的 QUBO 优化( QUBO) 模型中, 可以用量子反射的量子平方位( 美元) : 如果一个程序中输入美元, 美元不会超过美元, 执行一个特定程序状态 $E, 执行不超过美元 美元 的机器指令。 翻译需要美元美元=美元=美元 美元=美元 美元=美元 。 因此, 在QUBO 模型中, 更多的量子平价平方( 美元) 数字=美元 。 当我们用量子平时, 直线性模型的量子值 =( 美元) 只能用量子平价平方平方平方平方平方平方平方平方平方平方平方平方平方平方平方平方平方平方平方平方平方平方平方平方平调 。

0
下载
关闭预览

相关内容

ACM/IEEE第23届模型驱动工程语言和系统国际会议,是模型驱动软件和系统工程的首要会议系列,由ACM-SIGSOFT和IEEE-TCSE支持组织。自1998年以来,模型涵盖了建模的各个方面,从语言和方法到工具和应用程序。模特的参加者来自不同的背景,包括研究人员、学者、工程师和工业专业人士。MODELS 2019是一个论坛,参与者可以围绕建模和模型驱动的软件和系统交流前沿研究成果和创新实践经验。今年的版本将为建模社区提供进一步推进建模基础的机会,并在网络物理系统、嵌入式系统、社会技术系统、云计算、大数据、机器学习、安全、开源等新兴领域提出建模的创新应用以及可持续性。 官网链接:http://www.modelsconference.org/
专知会员服务
122+阅读 · 2021年8月4日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
鲁棒机器学习相关文献集
专知
8+阅读 · 2019年8月18日
Github项目推荐 | RecQ - Python推荐系统框架
AI研习社
8+阅读 · 2019年1月23日
Python推荐系统框架:RecQ
专知
12+阅读 · 2019年1月21日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
量子计算
人工智能学家
7+阅读 · 2018年4月6日
机器学习线性代数速查
机器学习研究会
19+阅读 · 2018年2月25日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
0+阅读 · 2022年2月18日
Arxiv
0+阅读 · 2022年2月17日
Arxiv
0+阅读 · 2022年2月16日
Arxiv
0+阅读 · 2022年2月16日
Arxiv
0+阅读 · 2022年2月16日
Arxiv
0+阅读 · 2022年2月15日
Arxiv
4+阅读 · 2018年4月30日
VIP会员
相关VIP内容
专知会员服务
122+阅读 · 2021年8月4日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
相关资讯
鲁棒机器学习相关文献集
专知
8+阅读 · 2019年8月18日
Github项目推荐 | RecQ - Python推荐系统框架
AI研习社
8+阅读 · 2019年1月23日
Python推荐系统框架:RecQ
专知
12+阅读 · 2019年1月21日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
量子计算
人工智能学家
7+阅读 · 2018年4月6日
机器学习线性代数速查
机器学习研究会
19+阅读 · 2018年2月25日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
相关论文
Arxiv
0+阅读 · 2022年2月18日
Arxiv
0+阅读 · 2022年2月17日
Arxiv
0+阅读 · 2022年2月16日
Arxiv
0+阅读 · 2022年2月16日
Arxiv
0+阅读 · 2022年2月16日
Arxiv
0+阅读 · 2022年2月15日
Arxiv
4+阅读 · 2018年4月30日
Top
微信扫码咨询专知VIP会员