量子态分解

Question

我正在寻找可以处理由位组成的加权经典状态求和形式的任意量子态的算法，例如下面这个形式：

|0000>/2 - |0011>/2 + |0100>/2 - |0111>/2

并使用张量积将其转化为更紧凑的形式，如下所示：

|0> x (|0> + |1>) x (|00> - |11>) / 2

我希望使用算法来可视化/简化（模拟的）量子电路的状态。

对于单个量子比特，我知道可以将所有状态与比特翻转时的状态进行配对，并检查每对状态之间的x:y关系是否相同。在上面的例子中，翻转第二个比特总是会得到一个权重为1:1的状态，因此第二个比特可以表示为(1|0> + 1|1>)。

但是，将这种方法扩展到检测纠缠比特（例如示例中的第三个和第四个比特）会使其需要至少Ω(n^c)时间（可能更长，我还没有完全思考），其中n是状态的数量，c是纠缠比特的数量。由于n已经随着比特数的增加呈指数增长，所以...不太理想。

有更好的算法吗？易于分解或重组的表示形式？改变基础知识有多有用？提供论文链接将非常有益。

- Craig Gidney

---

这与整数分解无关。 - Daniel Brückner

@AndersonGreen 一种普通的编程语言。我想用它来可视化量子计算的状态，但由于我没有量子计算机，因此对于分解算法本身来说，它并不是量子的。 - Craig Gidney

@Craig：你能给我一些提示，为什么说“那是一个分解整数的算法”吗？ - Hans-Peter Stricker

@Craig：你最终是如何解决这个问题的？ - Hans-Peter Stricker

@HansStricker 由于整个问题都是NP难的，我专注于“用户指定的一组特定连续量子比特是否与其余部分可分离？”[您可以在Quirk的振幅显示中看到它的运作。]（http://algorithmicassertions.com/quirk#circuit=%7B%22cols%22%3A%5B%5B%22Y%5Et%22%2C%22X%5Et%22%5D%2C%5B%22Amps2%22%5D%2C%5B%5D%2C%5B1%2C%22%E2%80%A2%22%2C%22X%22%5D%2C%5B%22Amps2%22%5D%2C%5B%5D%5D%7D) - Craig Gidney

Answer 1

看起来一个高效的算法会很难实现：

从 维基百科 中得知：

在量子信息理论中，判断一个状态是否可分被称为可分离问题。它被认为是一个困难的问题。已经被证明这是NP难的。

Gurvits, L., Classical deterministic complexity of Edmonds’ problem and quantum entanglement, in Proceedings of the 35th ACM Symposium on Theory of Computing, ACM Press, New York, 2003.

Sevag Gharibian, Strong NP-Hardness of the Quantum Separability Problem, Quantum Information and Computation, Vol. 10, No. 3&4, pp. 343-360, 2010. arXiv:0810.4507

- Peter de Rivaz