pgp9c5ah2/Paper_Notes_LZT.md

Paper Notes

• Programming languages and compiler design for realistic quantum hardware

  • Debugging and assertions

    • 模拟器旁路，从而加速

    • 形式化验证

      An alternative approach is to focus on specific properties of the algorithm. For example, one can use mathematical constructs and for- malisms in the programming language, and then allow the compiler to infer and annotate subsequent levels of the toolchain with attributes of the state that are known at different points of execution64. Such programmer annotations can be checked by a classical satisfiability modulo theory solver or theorem prover65. In addition, type analysis can be used to support QC correctness checks, such as the no-cloning rule66, entangle- ment, qubit uncomputation or re-use, and probability of error.

    • building the classical control resources for a QC 上的挑战

  • Classical Co-computing

    • Furthermore, the interface between classical and quantum computation may involve a slow and low-capacity communication channel. （应该把需要接在芯片上的，可能也要低温的，和传统部分合理划分）
    • The classical computation may need to communicate precision requirements to the quantum computation, and the quantum computation may need to communicate noise and error information back to the classical computation.

  • Static Compilation

    • In addition, QC hardware provides much more parallelism than classical hardware—some designs propose that the same operation can be applied to every qubit at the same time. This information and physical capability is critical because the primary disad- vantage QC systems face is such severe resource constraints (for example, low gate and storage counts and high quantum error correction code requirements) that QC compilers must perform much more aggressive optimizations to ‘make things fit’. These aggressive optimizations them- selves require substantial computation resources, hindering the com- piler’s ability to compile effectively and scalably for large applications or large data input sizes
    • Loop unrolling (像 FPGA) & Function inlining
    • The compiler’s decisions regarding when to unroll and inline, as well as optimizing the resulting code, are very time- and memory-intensive at compilation time.

  • Dynamic Compilation

    • 有些分支依赖之前的测量结果，所以只能运行时做
      • 并且量子协处理器和其它部分通信的带宽相对比较低（多低？）
    • We now discuss both generating instructions at runtime (that is, dynamic compilation) and performing operations for which code is available but dynamic information is necessary to know whether to run those instructions (that is, dynamic execution).
    • For example, all superconducting qubits studied thus far can be described by an LCJ circuit, consisting of inductors (L), capacitors (C), and Josephson junctions (J). These circuits can be con- trolled to reduce one of two kinds of qubit errors, amplitude and phase, but not both at the same time. This error tradeoff may be useful for some error correction algorithms.
      • Dempster, J. M., Fu, B., Ferguson, D. G., Schuster, D. I. & Koch, J. Understanding degenerate ground states of a protected quantum circuit in the presence of disorder. Phys. Rev. B 90, 094518 (2014).
      55. Mavadia, S., Frey, F., Sastrawan, J., Dona, S. & Biercuk, M. J. Prediction and real-time compensation of qubit decoherence via machine learning. Nature Commun. 8, 14106 (2017).
    • More speculatively, there is some potential that machine learning techniques can be used to adapt qubits to environmental noise.

  • 编程

    • imperative vs functional
    • First, there is a need for languages that allow programmers to specify easily what a program ought to do at a high level as opposed to existing operation-oriented languages that specify only the step-by-step mechanics of what to do. We need such specification languages so that we can specify what it takes for a program to be correct and check the implementation of the program against that specification. Such verification support is crucial because QC developers will always implement quantum programs for the next-generation quantum machine that cannot be tested on current machines. Although recent experimental progress has been impressive, fully capable quantum computers large enough to test most programs do not yet exist, so all testing must be done through classical simulation. Once we have small quantum computers, we will still have difficulty because each new qubit in future machine sizes will increase computational power exponentially.
      • Figgatt, C. et al. Complete 3-qubit grover search on a programmable quantum computer. Preprint at https://arxiv.org/abs/1703.10535 (2017).
      49. Castelvecchi, D. IBM’s quantum cloud computer goes commercial. Nature 543, 159 (2017).
    • Second, we need to specify the desired precision and error tolerance in quantum programming languages. This need is similar to that in approximate computing paradigms on classical machines. For two reasons, quantum algorithms are typically designed to be inherently error tolerant. First, quantum machines have high rates of error. Second, some quantum operations (such as an arbitrary rotation) can only be approximated on real machines. Consequently, many quantum algorithms have easy classical tests for correct output (for example, multiplying the results in Shor’s algorithm to check the proper factorization of the product of two primes) and may require multiple executions before producing correct output. A problem that is easy to check is often referred to as a ‘promise problem’. For a quantum algorithm to find a solution to a promise problem in a small, constant number of executions, the probability of correct output must be reasonably high (for example, 0.5). Additionally, some algorithms (for example, ground-state estimation in quantum chemistry) require a numerical precision that scales with the complexity of the physical system modelled.
    • To target near-term machines, we expect quantum software to adopt a much more optimized approach, evolving as have classical approximate computing tools. We expect that error probabilities and precision require- ments will be specified for each quantum program output, perhaps in a manner similar to classical languages for approximate computation.
      • Park, J., Esmaeilzadeh, H., Zhang, X., Naik, M. & Harris, W. Flexjava: Language support for safe and modular approximate programming. In Proc. 10th Joint Meet. on Foundations of Software Engineering (ESEC/FSE 2015) 745–757 (ACM, 2015)