没有合适的资源?快使用搜索试试~ 我知道了~
首页复参数Ising与Tutte配分函数近似计算复杂性全面研究
复参数Ising与Tutte配分函数近似计算复杂性全面研究
0 下载量 91 浏览量
更新于2024-06-17
收藏 1.11MB PDF 举报
本研究论文深入探讨了复值Ising和Tutte配分函数逼近计算的复杂性理论,由 LeslieAnn Goldberg 和 HengGuo 于2017年1月24日提出。Ising和Tutte配分函数在组合数学和统计物理学中具有重要意义,特别是在描述物理系统中的能量和关联性时,尤其是在考虑物理相变时,复数参数是必不可少的,因为这些相变通常对应于配分函数在复平面上的零点。 以往的研究主要集中在实参数版本上,而本文则首次扩展到复参数,试图全面理解这些配分函数逼近问题的复杂性。作者引入了组合参数,首次给出了关于复值Ising配分函数中带有复杂边缘相互作用的乘法和加法逼近的完整复杂性分类。在处理外场存在时,特别是在参数为单位根的情况下,研究提供了比之前更为详尽的二分法,强化了从BQP(量子可计算)难度提升到#P(组合难题)难度的结果。这标志着对这些特定问题理解的显著进步,因为之前此类分析仅限于少数几个特殊点。 论文还关注了Tutte多项式符号计算的复杂性,证明了在某些情况下它是#P-hard,与量子计算的模拟BQP相关联。通过这些分类,作者重新审视了量子计算与配分函数计算之间的联系,尽管得出的结论与现有量子文献中的观点有所不同,但研究路径相似,进一步深化了对这两个领域的交叉理解。 该研究得到了欧洲研究委员会和英国工程和物理科学研究理事会(EPSRC)的资助,展示了对这类问题的多维度探索和理论进展。通过本文,研究人员不仅推动了复杂性理论在经典计算中的边界,也为量子计算的理论基础提供了新的洞见。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/88777937/bg8.jpg)
8
- −
- −
关于
我们
−
±
∈ {
− −
}
±
−
和
|
arg
z
−
arg
z
′
|
≤
NameS
IGN
-R
EAL
T
UTTE
(
x
,
y
)
实例
A(多)图
G
.
求
T
(
G
;
x
,
y
)的实数部分的符号为正、负或0。
名称
SIGN-REAL-NONZERO TUTTE(
x
,
y
)
实例
A(多)图
G
.
输出
一
个形式为“T(G ; x,y)≥ 0”或“T(G ; x,y)≤ 0”的
正确
状态
。
BQP是一类可由量子计算机在多项式时间内以有界误差解决的决策问题。定理
[4,定理6.1]表明,BQP中的所有问题也可以在多项式时间内使用一个oracle来经典地
解决,该oracle返回链路的琼斯多项式的实部的符号,在点
t
= exp(2
πi/
5)处求值。
Thistlethwaite [27](见[17,(6.1)])表明,这个问题反过来又与求平面图
G
的
Tutte多
项式
T
(
G
;
t
,
t
−
1
)的问题有关。这启发了Bordewich等人关于确定Tutte多项式的符号
的复杂性的问题,特别是对于点(
x
,
y
)=(
t
,
t
−
1
)。 我们表明,这个问题是很
难的
t
值,包括相关的值
t
= exp(2
πi/
5)。请注意,我们的结果对BQP的模拟没有
直接影响,因为我们没有处理平面性(尽管它回答了Bordewich等人的问题)。我们
在第5节中给出了详细的内容,在那里我们还讨论了Kuperberg [20]的一个相关结果。
我们的定理如下。
定理
4.
考虑
点
(
x
,
y
)
=
(exp(
aπ
i
/b
)
,
exp(
aπ
i
/b
))
,
其中
a
和
b
是满足
0
<a/b<
2
和
ab/
2
,
b
,
3
b/
2的正整数
。如果
a
是奇数并且
cos(
aπ/b
)
<
为11
/
27
,则
S
ig-R
EAL
-N
ONZE
RO
T
UTTE
(
x
,
y
)
为
#
P
-ha r
d
。
因此
,
Sig-R
EAL
T
UTTE
(
x
,
y
)
也
是
#
P-ha r
d
。
条件
cos(
a π
/b
)
<
11
/
27
约
为
0
。
36643
<a/<
b
63357.
由于
−
exp(
−
2
π
i
/
5)
=
exp(
π
i)
exp
(
−
2
π
i
/
5)
=
exp(3
π
i
/
5),
我们
得到了
a
=
3
和
b
=
5的相关推论。
推论5.
L
et
y
=
−
exp(
−
2
π
i
/
5)
.
则
S
IGN
-
REAL
-
N
ONZE RO
T
UTTE
(1
/y
,
y
)
为
#
P-ha r
d.
1.6
关于带场
我们在1.3节中的结果是关于在没有外场的情况下(当
λ
=
1时)计算伊辛配分函数的复
杂性。这适用于IQP的应用。有外场的伊辛模型本身就很重要。此外,De las Cuevas
等人[8,结果
2]
表明
,
当
边相互作用
i
和
外场
ei
π
/
4
时
,
配分函数的加法近似是BQP-困难
的.受这种量子连接的启发,我们给出了以下扩展。
定理6.
设
K>
1
。 设
y
和
z
是两个单位根。则以下成立:
1.
如果
y
=
i
和
z
1
,
1
,
i
,
i
,或
y
=
1
,则
Z
Ising
(;
y
,
z
)
可以在多项式时间
内精确计算。
2.
否则
F
ACTOR
-K-N
ONZERO
-NI
SING
(
y
,
z
)
是
#
P-hard
。
2
预赛
2.1
关于复数近似的
我们将使用以下关于1.2节中Ziv距离测度的技术引理。
引理
7.
若
z
和
z
′
是
两
个非零复
整数
且
d
(
z
′
,
z
)
≤
ε
,
则
|
z
′
|
/
|
z
|
≤
1
/
(1
−
ε
)
36
ε/
11
。
![](https://csdnimg.cn/release/download_crawler_static/88777937/bg9.jpg)
9
−
−
−
√
R
|
|/
≤
|
|
R
R
等于11(
θ
-
θ
)
/
24,
|
θ
−
θ
|
≤
K
R
1 −
1
−
证据
设
d
(
z
′
,
z
)≤
ε
,|
z
′
| ≥ |
z
|.
首先,根据三角不等式,|
z
|+的|
z
′
−
z
| ≥ |
z
′
|所以
|
= 1
+
| z
′
|
−
| z|
≤ 1 +
| z
′
−
z
|
=
1
+
| z
′
−
z
|
z
|z ′|
≤ 1 +
ε
|z
′
|
、
|
,
按要求
|z|
|z|
|z|
|z
′
|
|z|
|z|
第二、|
z
′
−
z
|
≤
ε
|
z
′
|所以(|
z
′
−
z
|)
2
≤
ε
2
|
z
′
|
二
、 设
z
=
r
exp(
iθ
)和
z
′
=
r
′
exp(
iθ
′
),我们
((
r
′
cos(
θ
′
)
−
r
cos(
θ
))
2
+
((
r
′
sin(
θ
′
)
−
r
sin(
θ
))
2
≤
ε
2
r
′
2
.
左边等于
r
2
+
r
′
2
−
2
rr
′
cos(
θ
−
θ
′
)。但我们已经证明了
r
′
1
1≤
r
≤
1
−
ε
,
所以
r
′
2
(1
−
ε
)
2
+
r
′
2
−
2
r
′
2
cos(
θ
−
θ
′
)
≤
ε
2
r
′
2
,
这意味着,通过重新安排上述内容,
cos(
θ
−
θ
′
)
≥
1
−
但cos(
x
)= 1
−
x
2
/
2!
+
x
4
/
4!
-6
/6
!
+···,所以
3
ε ε
2
+
。
2 2
(
θ θ
′
)
2
二号!
−
(
θ
θ
′
)
4
+
四个!
(
θ θ
′
)
6
六!
− · · ·
≤
3
ε ε
2
.
2 2
假设
ε
非常
小(所以
θ
−
θ
′
≤
1)
,则
左手边
至少
为
(
θ
−
θ
′
)
2
−
(
θ
−
θ
′
)
4
′
2
′
√
二号! 四个!
引理8.
设
K>
1
,
0
<ρ <
2
π
。 然后存在以下多项式时间图灵约简。
F
ACTOR
-K-NI
SING
(
y
,
λ
)≤
T
C
COMPLEX
A
PX
-I
SING
(
y
,
λ
)
,
因子-K-N
ONZERO
-NI
SING
(
y
,
λ
)≤
T
C
COMPLEX
A px-N
ONZERO
-I
SING
(
y
,
λ
)
,
距离-
ρ
-A
RG
I
SING
(
y
,
λ
)≤
T
C
COMPLEX
A
PX
-I
SING
(
y
,
λ
)
,
距离-
ρ
-N
ONZERO
-A
RG
I
SING
(
y
,
λ
)≤
T
C
COMPLEX
A
PX
-N
ONZERO
-I
SING
(
y
,
λ
)
,
证据
设
R
是任何(足够大的)整数,使得1
−
1
/R >
1
/K
且36
/
11
R
≤
ρ
。
考虑一个重图
G
,其中
Z
Ising
(
G
;
y
,
λ
)= 0.给定输入
G
和
R
,
C
COMPLEX
A
PX
-I
SING
(
y
,
λ
)或C
COMPLEX
A
PX
-N
ONZERO
-I
SING
(
y
,
λ
)的预言机返回复数
z
,使
得
d
(
z
,
Z
Ising
(
G
;
y
,
λ
) )
1
。 另 一 方 面 , 如 果
Z
Ising
(
G
;
y
,
λ
) = 0 , 则
COMPLEXAPX-ISING(
y
,
λ
)的预言机返回复数
z
= 0,而COMPLEXAPX- NONZERO-
ISING(
y
,
λ
)的预言机返回任何复数
z
。
对于
前
两
个
还原,
首先
假设
|
Z
Isin g
(
G
;
y
,
λ
)
|
为
0. 根据引理7,
d
(
z
,
Z
Ising
(
G
;
y
,
λ
))≤
1
意味着
|
≤
。
|
≤
.
1
−
1
Σ
|
z
|
≤
|
Z
(
G
;
y
,
λ
)
|
≤
|z|
≤
K
|
z
|
、
R
所以|
z
|是F actor-K-N I
SING
(
y
,
λ
)或F actor-K-N
ONZERO
-N I
SING
(
y
,
λ
)
与
输入
G
的
合适输出
。 另一方面
如果
|
Z
Isin g
(
G
;
y
,
λ
)
|
=
0
,则
|
z
|
在
两种
情况下仍然适用。
对于
最后
两
次
还原,
首先
假设
|
Z
Isin g
(
G
;
y
,
λ
)
|
=
0。
则
由
引理
7
,
d
(
z
,
Z
Ising
(
G
;
y
,
λ
))≤
1
意味
|≤
ε 36 ε/ 11 ≤ ρ
,
|
≤
√
36
ε/
11 ≤
ρ,
有
36
ε/
11。
Ising
剩余42页未读,继续阅读
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- Vue实现iOS原生Picker组件:详细解析与实现思路
- Arduino蓝牙小车:参数调试与功能控制
- 百度Java面试精华:200页精选资源涵盖核心知识点
- Swift使用CoreData填坑指南:CoreData在Swift 3.0的变化
- 微距离无线充电器创新设计及其实验探索
- MTK Android平台开发全攻略:44步详解流程
- RecyclerView全面解析:替代ListView的新选择
- Android开发:自动适配中英文键盘解决方案
- Android调用WebService接口教程
- Android开发:BitmapUtil图片处理全解析与实例
- Android多线程断点续传实现详解
- PCA算法在人脸识别会议签到系统中的应用
- EventBus 3.0:Android事件总线详解与实战应用
- Android FileUtil:全面解析文件操作实用技巧与实例
- RecyclerView添加头部和尾部实战教程
- Android实现微博滑动固定顶部栏实战与优化
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)