Publications by authors named "Stephan Eidenbenz"
Article Synopsis
- Quantum computing offers capabilities that surpass classical computers, but current quantum machines produce noisy outputs, complicating result accuracy.
- This study assesses how noise affects bit string sampling and its consequences for optimization and machine learning tasks.
- By quantifying the sampling overhead and relating it to layer fidelity, the research establishes provable bounds on noise-free expectation values, validated through experiments on quantum computers with up to 127 qubits, showing good alignment with theoretical outcomes.*
We revisit the DOUBLE DIGEST problem, which occurs in sequencing of large DNA strings and consists of reconstructing the relative positions of cut sites from two different enzymes. We first show that DOUBLE DIGEST is strongly NP-complete, improving upon previous results that only showed weak NP-completeness. Even the (experimentally more meaningful) variation in which we disallow coincident cut sites turns out to be strongly NP-complete.
View Article and Find Full Text PDF