关于复杂网络中量子链路预测的复杂性
João P Moutinho1,2, Duarte Magano3,4, Bruno Coutinho4
1Instituto Superior Técnico, Universidade de Lisboa, Lisboa, Portugal. joao.p.moutinho@tecnico.ulisboa.pt.
Scientific reports
|January 10, 2024
概括
本研究介绍了一种优化的量子算法,用于网络中的链接预测. 量子方法在预测缺失连接方面比经典方法具有多项式优势.
科学领域:
- 网络科学 网络科学
- 量子计算是一种量子计算.
- 算法开发 算法开发
背景情况:
- 链接预测使用已知的数据模式识别网络中缺失的连接.
- 连续时间量子步行以前已经被探索为基于路径的链接预测.
研究的目的:
- 为基于路径的链接预测开发和分析一个优化的量子算法.
- 将拟议的量子算法的效率与经典方法进行比较.
主要方法:
- 利用抽样框架来分析用于链接预测的查询访问.
- 开发了一种基于连续时间量子步行的量子算法.
- 将量子算法性能与使用相邻矩阵权力的经典算法进行比较.
主要成果:
- 拟议的量子算法提供了关于节点数 (N) 的多项式量子优势.
- 在N中,算法的复杂性是次线性的.
- 算法性能受到网络相邻矩阵的量子模拟复杂性的限制.
结论:
- 量子算法显示出大网络中高效链接预测的前景.
- 这项研究强调了量子模拟对网络科学进步的重要性.
- 进一步研究网络邻矩阵的量子模拟是有必要的.
相关概念视频
Network Function of a Circuit
290
Frequency response analysis in electrical circuits provides vital insights into a circuit's behavior as the frequency of the input signal changes. The transfer function, a mathematical tool, is instrumental in understanding this behavior. It defines the relationship between phasor output and input and comes in four types: voltage gain, current gain, transfer impedance, and transfer admittance. The critical components of the transfer function are the poles and zeros.
290
¹H NMR: Interpreting Distorted and Overlapping Signals
1.0K
Spin systems where the difference in chemical shifts of the coupled nuclei is greater than ten times J are called first-order spin systems. These nuclei are weakly coupled, and their chemical shifts and coupling constant can generally be estimated from the well-separated signals in the spectrum.
As Δν decreases and the signals move closer, the doublets appear increasingly distorted. The intensities of the inner lines increase at the cost of those of the outer lines as the signals are...
As Δν decreases and the signals move closer, the doublets appear increasingly distorted. The intensities of the inner lines increase at the cost of those of the outer lines as the signals are...
1.0K
Protein Networks
4.0K
An organism can have thousands of different proteins, and these proteins must cooperate to ensure the health of an organism. Proteins bind to other proteins and form complexes to carry out their functions. Many proteins interact with multiple other proteins creating a complex network of protein interactions.
These interactions can be represented through maps depicting protein-protein interaction networks, represented as nodes and edges. Nodes are circles that are representative of a protein,...
These interactions can be represented through maps depicting protein-protein interaction networks, represented as nodes and edges. Nodes are circles that are representative of a protein,...
4.0K
Propagation of Uncertainty from Random Error
691
An experiment often consists of more than a single step. In this case, measurements at each step give rise to uncertainty. Because the measurements occur in successive steps, the uncertainty in one step necessarily contributes to that in the subsequent step. As we perform statistical analysis on these types of experiments, we must learn to account for the propagation of uncertainty from one step to the next. The propagation of uncertainty depends on the type of arithmetic operation performed on...
691
Transmission-Line Differential Equations
299
Transmission lines are essential components of electrical power systems. They are characterized by the distributed nature of resistance (R), inductance (L), and capacitance (C) per unit length. To analyze these lines, differential equations are employed to model the variations in voltage and current along the line.
Line Section Model
A circuit representing a line section of length Δx helps in understanding the transmission line parameters. The voltage V(x) and current i(x) are measured...
Line Section Model
A circuit representing a line section of length Δx helps in understanding the transmission line parameters. The voltage V(x) and current i(x) are measured...
299
Propagation of Uncertainty from Systematic Error
521
The atomic mass of an element varies due to the relative ratio of its isotopes. A sample's relative proportion of oxygen isotopes influences its average atomic mass. For instance, if we were to measure the atomic mass of oxygen from a sample, the mass would be a weighted average of the isotopic masses of oxygen in that sample. Since a single sample is not likely to perfectly reflect the true atomic mass of oxygen for all the molecules of oxygen on Earth, the mass we obtain from this...
521


