On the Algorithmic Solvability of Spectral Factorization and Applications
H. Boche, V. Pohl.
IEEE Transactions on Information Theory 66, 4574-4592 (2020).
Spectral factorization is an operation which appears in many different engineering applications. This paper studies whether spectral factorization can be algorithmically computed on an abstract machine (a Turing machine). It is shown that there exist computable spectral densities with very good analytic properties (i.e. smooth with finite energy) such that the corresponding spectral factor cannot be determined on a Turing machine. Further, it will be proved that it is impossible to decide algorithmically whether or not a given computable density possesses a computable spectral factor. This negative result has consequences for applications of spectral factorization in computer-aided design, because there it is necessary that this problem be decidable. Conversely, this paper will show that if the logarithm of a computable spectral density belongs to certain Sobolev space of sufficiently smooth functions, then the spectral factor is always computable. As an application, the paper discusses the possibility of calculating the optimal causal Wiener filter on an abstract machine.
Identification Capacity of Channels with Feedback: Discontinuity Behavior, Super-Activation, and Turing Computability
R.F. Schaefer, H. Boche, H.V. Poor.
IEEE Transactions on Information Theory (2020).
The problem of identification is considered, in which it is of interest for the receiver to decide only whether a certain message has been sent or not, and the identification-feedback (IDF) capacity of channels with feedback is studied. The IDF capacity is shown to be discontinuous and super-additive for both deterministic and randomized encoding. For the deterministic IDF capacity the phenomenon of super-activation occurs, which is the strongest form of super-additivity. This is the first time that super-activation is observed for discrete memoryless channels. On the other hand, for the randomized IDF capacity, super-activation is not possible. Finally, the developed theory is studied from an algorithmic point of view by using the framework of Turing computability. The problem of computing the IDF capacity on a Turing machine is connected to problems in pure mathematics and it is shown that if the IDF capacity would be Turing computable, it would provide solutions to other problems in mathematics including Goldbach’s conjecture and the Riemann Hypothesis. However, it is shown that the deterministic and randomized IDF capacities are not Banach-Mazur computable. This is the weakest form of computability implying that the IDF capacity is not computable even for universal Turing machines. On the other hand, the identification capacity without feedback is Turing computable revealing the impact of the feedback: It transforms the identification capacity from being computable to non-computable.
Denial-of-Service Attacks on Communication Systems: Detectability and Jammer Knowledge
H. Boche, R.F. Schaefer, H.V. Poor.
IEEE Transactions on Signal Processing 68, 3754-3768 (2020).
Wireless communication systems are inherently vulnerable to intentional jamming. In this paper, two classes of such jammers are considered: those with partial and full knowledge. While the first class accounts for those jammers that know the encoding and decoding function, the latter accounts for those that are further aware of the actual transmitted message. Of particular interest are so-called denial-of-service (DoS) attacks in which the jammer is able to completely disrupt any transmission. Accordingly, it is of crucial interest for the legitimate users to detect such adversarial DoS attacks. This paper develops a detection framework based on Turing machines. Turing machines have no limitations on computational complexity and computing capacity and storage and can simulate any given algorithm. For both scenarios of a jammer with partial and full knowledge, it is shown that there exists no Turing machine which can decide whether or not a DoS attack is possible for a given channel and the corresponding decision problem is undecidable. On the other hand, it is shown for both scenarios that it is possible to algorithmically characterize those channels for which a DoS attack is not possible. This means that it is possible to detect those scenarios in which the jammer is not able to disrupt the communication. For all other channels, the Turing machine does not stop and runs forever making this decision problem semidecidable. Finally, it is shown that additional coordination resources such as common randomness make the communication robust against such attacks.
Secure Communication and Identification Systems — Effective Performance Evaluation on Turing Machines
H. Boche, R.F. Schaefer, H.V. Poor.
IEEE Transactions on Information Forensics and Security 15, 1013 - 1025 (2020).
Modern communication systems need to satisfy pre-specified requirements on spectral efficiency and security. Physical layer security is a concept that unifies both and connects them with entropic quantities. In this paper, a framework based on Turing machines is developed to address the question of deciding whether or not a communication system meets these requirements. It is known that the class of Turing solvable problems coincides with the class of algorithmically solvable problems so that this framework provides the theoretical basis for effective verification of such performance requirements. A key issue here is to decide whether or not the performance functions, i.e., capacities, of relevant communication scenarios, particularly those with secrecy requirements and active adversaries, are Turing computable. This is a necessary condition for the corresponding communication protocols to be effectively verifiable. Within this framework, it is then shown that for certain scenarios including the wiretap channel the corresponding capacities are Turing computable. Next, a general necessary condition on the performance function for Turing computability is established. With this, it is shown that for certain scenarios, including the wiretap channel with an active jammer, the performance functions are not computable when deterministic codes are used. As a consequence, such performance functions are also not computable on all other computer architectures such as the von Neumann-architecture or the register machines.
Turing Computability of Fourier Transforms of Bandlimited and Discrete Signals
H. Boche, U.J. Mönich.
IEEE Transactions on Signal Processing 68, 532-547 (2020).
The Fourier transform is an important operation in signal processing. However, its exact computation on digital computers can be problematic. In this paper we consider the computability of the Fourier transform and the discrete-time Fourier transform (DTFT). We construct a computable bandlimited absolutely integrable signal that has a continuous Fourier transform, which is, however, not Turing computable. Further, we also construct a computable sequence such that the DTFT is not Turing computable. Turing computability models what is theoretically implementable on a digital computer. Hence, our result shows that the Fourier transform of certain signals cannot be computed on digital hardware of any kind, including CPUs, FPGAs, and DSPs. This also implies that there is no symmetry between the time and frequency domain with respect to computability. Therefore, numerical approaches which employ the frequency domain representation of a signal (like calculating the convolution by performing a multiplication in the frequency domain) can be problematic. Interestingly, an idealized analog machine can compute the Fourier transform. However, it is unclear whether and how this theoretical superiority of the analog machine can be translated into practice. Further, we show that it is not possible to find an algorithm that can always decide for a given signal whether the Fourier transform is computable or not.
Secure Storage Capacity Under Rate Constraints—Continuity and Super Activation
S. Baur, H. Boche, R.F. Schaefer, H.V. Poor.
IEEE Transactions on Information Forensics and Security 15, 959-970 (2020).
The source model for secret key generation with one way public communication refers to a setting in which a secret key should be agreed upon at two terminals. At both terminals correlated components of a common source are available. In addition, a message can be sent from one terminal to the other via a public channel. In this paper, a related scenario is considered where instead of secret key generation, the goal is to securely store data in a public database. The database allows for error-free storing of the data, but is constrained in its size which imposes a rate constraint on storing. The corresponding capacity for secure storage is known and it has been shown that the capacity-achieving strategy satisfies the strong secrecy criterion. Here, the case when the storage in the public database is subject to errors is considered and the corresponding capacity is characterized. In addition, the continuity properties of the two capacity functions are analyzed. These capacity functions are continuous as opposed to the discontinuous secret key capacity with rate constraint. It is shown that for secure storage the phenomenon of super activation can occur. Finally, it is discussed how the results in this paper differ from previous results on super activation.
Secret message transmission over quantum channels under adversarial quantum noise: Secrecy capacity and super-activation
H. Boche, M. Cai, J. Nötzel, C. Deppe.
Journal of Mathematical Physics 60, 062202-1 to 062202-39 (2019).
We determine the secrecy capacities of arbitrarily varying quantum channels (AVQCs). Both secrecy capacities with average error probability and with maximal error probability are derived. Both derivations are based on one common code construction. The code we construct fulfills a stringent secrecy requirement, which is called the strong code concept. As an application of our result for secret message transmission over AVQCs, we determine when the secrecy capacity is a continuous function of the system parameters and completely characterize its discontinuity points both for average error criterion and for maximal error criterion. Furthermore, we prove the phenomenon “superactivation” for secrecy capacities of arbitrarily varying quantum channels, i.e., two quantum channels both with zero secrecy capacity, which, if used together, allow secure transmission with positive capacity. We give therewith an answer to the question “When is the secrecy capacity a continuous function of the system parameters?,” which has been listed as an open problem in quantum information problem page of the Institut für Theoretische Physik (ITP) Hannover. We also discuss the relations between the entanglement distillation capacity, the entanglement generating capacity, and the strong subspace transmission capacity for AVQCs. Ahlswede et al. made in 2013 the conjecture that the entanglement generating capacity of an AVQC is equal to its entanglement generating capacity under shared randomness assisted quantum coding. We demonstrate that the validity of this conjecture implies that the entanglement generating capacity, the entanglement distillation capacity, and the strong subspace transmission capacity of an AVQC are continuous functions of the system parameters. Consequently, under the premise of this conjecture, the secrecy capacities of an AVQC differ significantly from the general quantum capacities.
Message Transmission over Classical Quantum Channels with a Jammer with Side Information: Correlation as Resource, Common Randomness Generation
H. Boche, M. Cai, N. Cai.
Journal of Mathematical Physics 61, 062201 (2020).
In this paper, we analyze the capacity of a general model for arbitrarily varying classical-quantum channels (AVCQCs) when the sender and the receiver use correlation as a resource. In this general model, a jammer has side information about the channel input. We determine a single letter formula for the correlation assisted capacity. As an application of our main result, we determine the correlation assisted common randomness generation capacity. In this scenario, the two channel users have access to correlation as a resource and further use an AVCQC with an informed jammer for additional discussion. The goal is to create common randomness between the two channel users. We also analyze these capacity formulas when only a small number of signals from the correlation are available. For the correlation assisted common randomness generation capacity, we show an additional interesting property: For a sufficient amount of “public communication,” common randomness generation capacity is Turing computable; however, without this public communication constraint, the correlation assisted common randomness generation capacity is, in general, not Turing computable. Furthermore, we show that even without knowing the capacity formula of the deterministic capacity using the maximal error criterion, we can show that it is impossible to evaluate the performance algorithmically on any current or future digital computer.
Universal superposition codes: Capacity regions of compound quantum broadcast channel with confidential messages
H. Boche, G. Janssen, S. Saeedinaeeni.
Journal of Mathematical Physics 61, 042204 (2020).
We derive universal codes for transmission of broadcast and confidential messages over classical-quantum–quantum and fully quantum channels. These codes are robust to channel uncertainties considered in the compound model. To construct these codes, we generalize random codes for transmission of public messages to derive a universal superposition coding for the compound quantum broadcast channel. As an application, we give a multi-letter characterization of regions corresponding to the capacity of the compound quantum broadcast channel for transmitting broadcast and confidential messages simultaneously. This is done for two types of broadcast messages, one called public and the other common.
Message Transmission Over Classical Quantum Channels With a Jammer With Side Information: Message Transmission Capacity and Resources
H. Boche, M. Cai, N. Cai.
IEEE Transactions on Information Theory 65 (5), 2922 - 2943 (2019).
In this paper, a new model for arbitrarily varying classical-quantum channels is proposed. In this model, a jammer has side information. The communication scenario in which a jammer can select only classical inputs as a jamming sequence is considered in the first part of the paper. This situation corresponds to the standard model of arbitrarily varying classical-quantum channels. Two scenarios are considered. In the first scenario, the jammer knows the channel input, while in the second scenario the jammer knows both the channel input and the message. The transmitter and receiver share a secret random key with a vanishing key rate. The capacity for both average and maximum error criteria for both scenarios is determined in this paper. A strong converse is also proved. It is shown that all these corresponding capacities are equal, which means that additionally revealing the message to the jammer does not change the capacity. The communication scenario with a fully quantum jammer is considered in the second part of the paper. A single letter characterization for the capacity with secret random key as assistance for both average and maximum error criteria is derived in the paper.
Simultaneous transmission of classical and quantum information under channel uncertainty and jamming attacks
H. Boche, G. Janssen, S. Saeedinaeeni.
Journal of Mathematical Physics 60, 022204 (2019).
We derive universal codes for simultaneous transmission of classical messages and entanglement through quantum channels, possibly under the attack of a malignant third party. These codes are robust to different kinds of channel uncertainties. To construct such universal codes, we invoke and generalize the properties of random codes for classical and quantum message transmission through quantum channels. We show these codes to be optimal by giving a multi-letter characterization of regions corresponding to capacity of compound quantum channels for simultaneously transmitting and generating entanglement with classical messages. In addition, we give dichotomy statements in which we characterize the capacity of arbitrarily varying quantum channels for simultaneous transmission of classical messages and entanglement. These include cases where the malignant jammer present in the arbitrarily varying channel model is classical (chooses channel states of the product form) and fully quantum (is capable of general attacks not necessarily of the product form).
Turing meets circuit theory: Not every continuous-time LTI system can be simulated on a digital computer
H. Boche, V. Pohl.
IEEE Transactions on Circuits and Systems I: Regular Papers 67, 5051 - 5064 (2020).
Solving continuous problems on digital computers gives generally only approximations of the continuous solutions. It is therefore crucial that the error between the continuous solution and the digital approximation can effectively be controlled. This paper investigates the possibility of simulating linear, time-invariant (LTI) systems on Turing machines. It is shown that there exist elementary LTI systems for which an admissible and computable input signal results in a non-computable output signal. For these LTI systems, the paper gives sharp characterizations of input spaces such that the output is guaranteed to be computable. The second part of the paper discusses the computability of the impulse and step response of LTI systems. It is shown that the computability of the step response implies not the computability of the impulse response. Moreover, there exist impulse responses which cannot be computed from the transfer function using the inverse Laplace transform. Finally, the paper gives a stronger version of a classical non-computability result, showing that there exist admissible and computable initial values for the wave equation so that the solution cannot be computed at certain points in space and time.
Extending Quantum Links: Modules for Fiber- and Memory-Based Quantum Repeaters
P. van Loock, W. Alt, C. Becher, O. Benson, H. Boche, C. Deppe, J. Eschner, S. Höfling, D. Meschede, P. Michler, F. Schmidt, H. Weinfurter.
Advancing Quantum Technologies - Chances and Challenges Advanced Quantum Technologies, (2020).
Elementary building blocks for quantum repeaters based on fiber channels and memory stations are analyzed. Implementations are considered for three different physical platforms, for which suitable components are available: quantum dots, trapped atoms and ions, and color centers in diamond. The performances of basic quantum repeater links for these platforms are evaluated and compared, both for present‐day, state‐of‐the‐art experimental parameters as well as for parameters that can in principle be reached in the future. The ultimate goal is to experimentally explore regimes at intermediate distances—up to a few 100 km—in which the repeater‐assisted secret key transmission rates exceed the maximal rate achievable via direct transmission. Two different protocols are considered, one of which is better adapted to the higher source clock rate and lower memory coherence time of the quantum dot platform, while the other circumvents the need of writing photonic quantum states into the memories in a heralded, nondestructive fashion. The elementary building blocks and protocols can be connected in a modular form to construct a quantum repeater system that is potentially scalable to large distances.
Communication under Channel Uncertainty: An Algorithmic Perspective and Effective Construction
H. Boche, R.F. Schaefer, H.V. Poor.
IEEE Transactions on Signal Processing 68, 6224 - 6239 (2020).
The availability and quality of channel state information heavily influences the performance of wireless communication systems. For perfect channel knowledge, optimal signal processing and coding schemes have been well studied and often closed-form solutions are known. On the other hand, the case of imperfect channel information is less understood and closed-form characterizations of optimal schemes remain unknown in many cases. This paper approaches this question from a fundamental, algorithmic point of view by studying whether or not such optimal schemes can be constructed algorithmically in principle (without putting any constraints on the computational complexity of such algorithms). To this end, the concepts of compound channels and averaged channels are considered as models for channel uncertainty and block fading and it is shown that, although the compound channel and averaged channel themselves are computable channels, the corresponding capacities are not computable in general, i.e., there exists no algorithm (or Turing machine) that takes the channel as an input and computes the corresponding capacity. As an implication of this, it is then shown that for such compound channels, there are no effectively constructible optimal (i.e., capacity-achieving) signal processing and coding schemes possible. This is particularly noteworthy as such schemes must exist (since the capacity is known), but they cannot be effectively, i.e., algorithmically, constructed. Thus, there is a crucial difference between the existence of optimal schemes and their algorithmic constructability. In addition, it is shown that there is no search algorithm that can find the maximal number of messages that can be reliably transmitted for a fixed blocklength. Finally, the case of partial channel knowledge is studied in which either the transmitter or the receiver have perfect channel knowledge while the other part remains uncertain. It is shown that also in the cases of an informed encoder and informed decoder, the capacity remains non-computable in general and, accordingly, optimal signal processing and coding schemes are not effectively constructible.