Michal Hajdušek

Yoshiki Kanazawa, Naphan Benchasattabuse, Michal Hajdušek et al.

We formulate a structure-informed multiple sequence alignment problem, denoted MSA-S. The model abstracts biological sequences as strings and structural information as designated position-pairs. It augments a fixed pairwise string score, defined by a fixed non-gap symbol-pair scoring rule and fixed affine gap penalties, with a binary overlap score on designated position-pairs, which can be interpreted as a contact-map overlap score in structural applications. This yields a fixed-score, integer-valued optimization model suitable for complexity-theoretic analysis. Under this formulation, we show that the decision problem MSA-S-DEC is NP-complete for a broad class of fixed pairwise string scoring schemes. We also show that NP-hardness persists even under the restriction that every designated position-pair set is nonempty and the pair-overlap threshold is strictly positive. For the associated scalarized optimization problem MSA-S-OPT(lambda) with any fixed rational constant lambda >= 1, we further show that, under the canonical unit scheme for the non-gap symbol-pair scoring rule, MSA-S-OPT(lambda) admits no polynomial-time approximation scheme (PTAS) even for two input strings (k = 2), unless P = NP. These results establish a formal complexity-theoretic baseline for structure-informed multiple sequence alignment.

Naphan Benchasattabuse, Michal Hajdušek, Rodney Van Meter

The all-photonic quantum repeater scheme, utilizing a type of graph state called the repeater graph state (RGS), promises resilience to photon losses and operational errors, offering a fast Bell pair generation rate limited only by the RGS creation time (rather than enforced round-trip waits). While existing research has predominantly focused on RGS generation and secret key sharing rate analysis, there is a need to extend investigations to encompass broader applications, such as distributed computation and teleportation, the main tasks envisioned for the Quantum Internet. Here we propose a new emitter-photonic qubit building block and an RGS protocol that addresses several key considerations: end node involvement in connection establishment, decoding of logical qubits within the RGS, and computing the Pauli frame corrections at each participating node to ensure the desired correct end-to-end Bell pair state. Our proposed building block significantly reduces the total number of emissive quantum memories required for end nodes and seamlessly integrates all-photonic and memory-based repeaters under the same communication protocol. We also present an algorithm for decoding logical measurement results, employing graphical reasoning based on graph state manipulation rules.

Ryosuke Satoh, Michal Hajdušek, Naphan Benchasattabuse et al.

We present an event-driven simulation package called QuISP for large-scale quantum networks built on top of the OMNeT++ discrete event simulation framework. Although the behavior of quantum networking devices have been revealed by recent research, it is still an open question how they will work in networks of a practical size. QuISP is designed to simulate large-scale quantum networks to investigate their behavior under realistic, noisy and heterogeneous configurations. The protocol architecture we propose enables studies of different choices for error management and other key decisions. Our confidence in the simulator is supported by comparing its output to analytic results for a small network. A key reason for simulation is to look for emergent behavior when large numbers of individually characterized devices are combined. QuISP can handle thousands of qubits in dozens of nodes on a laptop computer, preparing for full Quantum Internet simulation. This simulator promotes the development of protocols for larger and more complex quantum networks.

Joseph F. Fitzsimons, Michal Hajdušek

With recent progress on experimental quantum information processing, an important question has arisen as to whether it is possible to verify arbitrary computation performed on a quantum processor. A number of protocols have been proposed to achieve this goal, however all are interactive in nature, requiring that the computation be performed in an interactive manner with back and forth communication between the verifier and one or more provers. Here we propose two methods for verifying quantum computation in a non-interactive manner based on recent progress in the understanding of the local Hamiltonian problem. Provided that the provers compute certain witnesses for the computation, this allows the result of a quantum computation to be verified after the fact, a property not seen in current verification protocols.

Michal Hajdušek, Carlos A. Pérez-Delgado, Joseph F. Fitzsimons

As progress on experimental quantum processors continues to advance, the problem of verifying the correct operation of such devices is becoming a pressing concern. The recent discovery of protocols for verifying computation performed by entangled but non-communicating quantum processors holds the promise of certifying the correctness of arbitrary quantum computations in a fully device-independent manner. Unfortunately, all known schemes have prohibitive overhead, with resources scaling as extremely high degree polynomials in the number of gates constituting the computation. Here we present a novel approach based on a combination of verified blind quantum computation and Bell state self-testing. This approach has dramatically reduced overhead, with resources scaling as only $O(m^4\ln m)$ in the number of gates.