In this dissertation, we investigate three different problems in the field of Quantum computation. First, we discuss the quantum complexity of evaluating the Tutte polynomial of a planar graph. Furthermore, we devise a new quantum algorithm for approximating the phase of a unitary matrix. Finally, we provide quantum tools that can be utilized to extract the structure of black-box modules and algebras. While quantum phase estimation (QPE) is at the core of many quantum algorithms known to date, its physical implementation (algorithms based on quantum Fourier transform (QFT) ) is highly constrained by the requirement of high-precision controlled phase shift operators, which remain difficult to realize. In the second part of this dissertation, we introduce an alternative approach to approximately implement QPE with arbitrary constantprecision controlled phase shift operators. The new quantum algorithm bridges the gap between QPE algorithms based on QFT and Kitaev’s original approach. For approximating the eigenphase precise to the nth bit, Kitaev’s original approach does not require any controlled phase shift operator. In contrast, QPE algorithms based on QFT or approximate QFT require controlled phase shift operators with precision of at least Pi/2n. The new approach fills the gap and requires only arbitrary constant-precision controlled phase shift operators. From a physical implementation viewpoint, the new algorithm outperforms Kitaev’s approach. iii The other problem we investigate relates to approximating the Tutte polynomial. We show that the problem of approximately evaluating the Tutte polynomial of triangular graphs at the points (q, 1/q) of the Tutte plane is BQP-complete for (most) roots of unity q. We also consider circular graphs and show that the problem of approximately evaluating the Tutte polynomial of these graphs at the point (e 2πi/5 ,e−2πi/5 ) is DQC1-complete and at points (q k , 1 + 1−q−k (q 1/2−q−1/2) 2 ) for some integer k is in BQP. To show that these problems can be solved by a quantum computer, we rely on the relation of the Tutte polynomial of a planar G graph with the Jones and HOMFLY polynomial of the alternating link D(G) given by the medial graph of G. In the case of our graphs the corresponding links are equal to the plat and trace closures of braids. It is known how to evaluate the Jones and HOMFLY polynomial for closures of braids. To establish the hardness results, we use the property that the images of the generators of the braid group under the irreducible Jones-Wenzl representations of the Hecke algebra have finite order. We show that for each braid b we can efficiently construct a braid ˜b such that the evaluation of the Jones and HOMFLY polynomials of their closures at a fixed root of unity leads to the same value and that the closures of ˜b are alternating links. The final part of the dissertation focuses on finding the structure of a black-box module or algebra. Suppose we are given black-box access to a finite module M or algebra over a finite ring R, and a list of generators for M and R. We show how to find a linear basis and structure constants for M in quantum poly(log |M|) time. This generalizes a recent quantum algorithm of Arvind et al. which finds a basis representation for rings. We then show that iv our algorithm is a useful primitive allowing quantum computers to determine the structure of a finite associative algebra as a direct sum of simple algebras. Moreover, it solves a wide variety of problems regarding finite modules and rings. Although our quantum algorithm is based on Abelian Fourier transforms, it solves problems regarding the multiplicative structure of modules and algebras, which need not be commutative. Examples include finding the intersection and quotient of two modules, finding the additive and multiplicative identities in a module, computing the order of an module, solving linear equations over modules, deciding whether an ideal is maximal, finding annihilators, and testing the injectivity and surjectivity of ring homomorphisms. These problems appear to be exponentially hard classically.

Title: Quantum computing algorithms for quantum chemistry Author: Jakub Višňák Abstract: The topic of this study is the simulation of the quantum algorithm for the diagonalization of the matrix representation of the all-electron Dirac-Coulomb hamiltonian of the SbH molecule. Two different limited CI expansions were used to describe both the ground state (X 0+ ) and the first excited doublet (A 1) by simulating the Iterative Phase Estinamtion Algorith (IPEA). In the simulations numerically performed in this work, the "compact mapping" has been employed for the representation of the evolution operator exp(i Hˆ t); in the theoretical part of the work, the "direct mapping" is described as well. The influence of the metodics for choosing the initial eigenvector estimate is studied in both IPEA A and IPEA B variants. For those variants, the success probabilities pm are computed for different single-points on the SbH dissociation curves. The initial eigenvector estimates based on the "CISD(2)" method are found to be sufficient for both studied LCI-expansions up to internuclear distance R  6 a0. The pm dependence on the overlap between the eigenvector in question and its inital estimate - 2 0  is studied the for IPEA B method. The usability of the both variants of the IPEA in possible later calculations is...

The estimation of the frequency and phase of a complex exponential in additive white Gaussian noise (AWGN) is a fundamental and well-studied problem in signal processing and communications. A variety of approaches to this problem, distinguished primarily by estimation accuracy, computational complexity, and processing latency, have been developed. One class of approaches is based on the Fast Fourier Transform (FFT) due to its connections with the maximum likelihood estimator (MLE) of frequency. This thesis compares several FFT-based approaches to the MLE in terms of their estimation accuracy and computational complexity. While FFT-based frequency estimation tends to be very accurate, the computational complexity of the FFT and the latency associated with performing these computations after the entire signal has been received can be prohibitive in some scenarios. Another class of approaches that addresses some of these shortcomings is based on linear regression of samples of the instantaneous phase of the observation. Linear- regression-based techniques have been shown to be very accurate at moderate to high signal to noise ratios and have the additional benefit of low computational complexity and low latency due to the fact that the processing can be performed as the samples arrive. These techniques, however, typically require the computation of four-quadrant arctangents, which must be approximated to retain low computational complexity. This thesis proposes a new frequency and phase estimator based on simple estimates of the zero-crossing times of the observation. An advantage of this approach is that it does not require arctangent calculations. Simulation results show that the zero-crossing frequency and phase estimator can provide high estimation accuracy, low computational complexity, and low processing latency, making it suitable for real-time applications. Accordingly, this thesis also presents a real-time implementation of the zero-crossing frequency and phase estimator in the context of a time-slotted round-trip carrier synchronization system for distributed beamforming. The experimental results show this approach can outperform a Phase Locked Loop (PLL) implementation of the same distributed beamforming system.

In coherent receivers, the effect of the multipath fading channel on the transmitted signal must be estimated to recover the transmitted data. In this thesis, the channel phase and data estimation problems are investigated in a transmitted data sequence when the channel is modeled as slowly fading, frequency non-selective channel. Channel phase estimation in a transmitted data sequence is investigated and data estimation is obtained in a symbol-by-symbol MAP receiver that is designed for minimum symbol error probability criterion. The channel phase is quantized in an interval of interest, the trellis diagram is constructed and Viterbi decoding algorithm is applied that uses the phase transition and observation models for channel phase estimation. The optimum coherent and noncoherent detectors for binary orthogonal and PSK signals are derived and the modulated signals in a sequence are detected in symbol-by-symbol MAP receivers.Simulation results have shown that the performance of the receiver with phase estimation is between the performance of the optimum coherent and noncoherent receiver.

It is commonly accepted that the induced noise on DFT phase spectrum has a negligible effect on speech intelligibility for short durations of analysis windows, as the early intelligibility studies pointed out. This fact is confirmed by recent intelligibility studies as well. Based on this phenomenon, classical speech enhancement algorithms do not modify DFT phase spectrum and only make changes in the DFT magnitude spectrum. However, in recent studies it is also indicated that these classical speech enhancement algorithms are not capable of improving the intelligibility scores of noise degraded speech signals. In other words, the contained information in a noise degraded signal cannot be increased by classical enhancement methods. Instead the ease of listening, i.e. quality, can be improved. Hence additional effort can be made to increase the amount of quality improvement using both DFT magnitude and DFT phase. Therefore if the performances of the classical methods are to be improved in terms of speech quality, the effect of DFT phase on speech quality needs to be studied. In this work, the contribution of DFT phase on speech quality is investigated through some simulations using an objective quality assessment criterion. It is concluded from these simulations that, the phase spectrum has a significant effect on speech quality for short durations of analysis windows. Furthermore, phase values of low frequency components are found to have the largest contribution to this quality improvement. Under the motivation of these results, a new enhancement method is proposed which modifies the phase of certain low frequency components as well as the magnitude spectrum. The proposed algorithm is implemented in MATLAB environment. The results indicate that the proposed system improves the performance of the classical methods in terms of speech quality.

Coherent detection employing multilevel modulation format has become one of the most promising technologies for next generation high speed transmission system due to the high power and spectral efficiencies. With the powerful digital signal processing (DSP), coherent optical receivers allow the significant equalization of chromatic dispersion (CD), polarization mode dispersion (PMD), phase noise (PN) and nonlinear effects in the electrical domain. Recently, the realizations of these DSP algorithms for mitigating the channel distortions in the transmission system are the most attractive investigations.  The CD equalization can be performed by the digital filters developed in the time and the frequency domain, which can suppress the fiber dispersion effectively. The PMD compensation is usually performed in the time domain with the adaptive least mean square (LMS) and constant modulus algorithms (CMA) equalization. Feed-forward and feed-back carrier phase estimation algorithms are employed to mitigate the phase noise from the transmitter and local oscillator lasers. The fiber nonlinearities are compensated by using the digital backward propagation methods based on solving the nolinear Schrodinger (NLS) equation and the Manakov equation.  In this dissertation, we present a comparative analysis of three digital filters for chromatic dispersion compensation, an analytical evaluation of carrier phase estimation with digital equalization enhanced phase noise and a brief discussion for PMD adaptive equalization. To implement these investigations, a 112-Gbit/s non-return-to-zero polarization division multiplexed quadrature phase shift keying (NRZ-PDM-QPSK) coherent transmission system is realized in the VPI simulation platform. With the coherent transmission system, these CD equalizers have been compared by evaluating their applicability for different fiber lengths, their usability for dispersion perturbations and their computational complexity. Meanwhile, the bit-error-rate (BER) floor in carrier phase estimation using a one-tap normalized LMS filter is evaluated analytically, and the numerical results are compared to a differential QPSK detection system. / QC 20110629

Extremsökande reglering (ESC) är en modellfri adaptiv reglermetod som kan användas för att lokalisera den optimala arbetspunkten i olinjära processer. Det har nyligen visats att det finns problem med traditionell ESC om det reglerade systemet är dynamiskt. I den här avhandlingen behandlar vi en ny metod för extremsökande reglering som är applicerbar för både statiska och dynamiska system. Metoden är baserad på att reglera processens arbetspunkt tills det lokala fasskiftet hos processen når ⇡/2. Resultatet är baserat på det faktum att fasskiftet hos processer generellt förändras kraftigt kring optimum, och för låga frekvenser motsvarar optimum ett fasskift på ⇡/2radianer. Regulatorstrukturen som används liknar en faslåst slinga (PLL). Ett olinjärt Kalmanfilter används för att estimera fasen och en integrerande regulator används för att justera arbetspunkten tills fasen når det önskade fasskiftet. Resultaten är illustrerade i ett exempel där den nya regulatorstrukturen används för att optimera produktionen i en kemisk reaktor. / Extremum Seeking Control (ESC) is a model-free adaptive control method to locate and track the optimal working point for nonlinear plants. However, as shown recently, traditional ESC methods may not work well for dynamic systems. In this thesis, we consider a novel ESC loop to locate the optimal operating point for both static and dynamic systems. Considering that the phase-lag of the system undergoes a large shift near a steady-state optimum and reaches the value of ⇡/2attheoptimaloperatingpoint, thenovelESC applies the phase-lag of the target system to track the optimum. An ex-tended Kalman filter is used to ensure the accuracy of the phase estimation. The structure of a phase locked loop (PLL) is employed in combination with an integral controller to lock the phase near ⇡/2, such that the target system will operate near the optimal working point. The controller is demonstrated by application to optimization of the substrate conversion in a chemical re-actor.

The increase in capacity demand along with the advancement in digital signal processing (DSP) have recently revived the interest in coherent optical communications and led to its commercialization. However, design and development of robust DSP algorithms for example for carrier phase recovery (CPR) becomes complex as we opt for high order modulation formats such as 16QAM and beyond. Further, electrical-domain dispersion compensation (EDC), while providing many advantages, makes the system more susceptible to laser frequency noise (FN). For instance, in coherent optical links with post-reception EDC, while the transmitter frequency noise causes only phase impairment, the local oscillator (LO) FN in these systems results in a noise enhancement in both amplitude and phase. This noise is commonly known as equalization enhanced phase noise (EEPN). It results in asymmetric requirements for transmitter laser and LO laser. Further, the system design in the presence of lasers with non-white frequency noise becomes increasingly challenging for increased capacity-distance product. The main contributions of this thesis are, firstly, an experimentally validated theory of coherent optical links with lasers having general non-white frequency noise spectrum and corresponding system/laser design criteria and mitigation technique. Secondly, low complexity and high phase noise tolerant CPR for high order modulation formats. The general theory propounded in this thesis elucidates the origin of the laser frequency noise induced noise enhancement in coherent optical links with different DSP configurations. The thesis establishes the existence of multiple frequency noise regimes and shows that each regime results in different set of impairments. The influence of the impairments due to some regimes can ideally be reduced by optimizing the corresponding mitigation algorithms, while other regimes cause irretrievable impairments. Experimentally validated theoretical boundaries of these regimes and corresponding criteria applicable to system/laser design are provided. Further, an EEPN mitigation method and its two possible implementations are proposed and discussed. The thesis also demonstrates an intrinsic limitation of the conventional Blind Phase Search (BPS) algorithm due to angular quantization and provides methods to overcome it. Finally, this thesis proposes and demonstrates single stage and multi-stage carrier phase recovery algorithms for compensation of phase impairments due to the two lasers for higher order circular and square modulations. The proposed methods outperform the state of art algorithms both in performance and in complexity. / <p>QC 20170516</p> / European project ICONE gr. #608099

Magnetic Resonance Imaging (MRI) is an important diagnostic tool for imaging soft tissue without the use of ionizing radiation. Moreover, through advanced signal processing, MRI can provide more than just anatomical information, such as estimates of tissue-specific physical properties. Signal processing lies at the very core of the MRI process, which involves input design, information encoding, image reconstruction, and advanced filtering. Based on signal modeling and estimation, it is possible to further improve the images, reduce artifacts, mitigate noise, and obtain quantitative tissue information. In quantitative MRI, different physical quantities are estimated from a set of collected images. The optimization problems solved are typically nonlinear, and require intelligent and application-specific algorithms to avoid suboptimal local minima. This thesis presents several methods for efficiently solving different parameter estimation problems in MRI, such as multi-component T2 relaxometry, temporal phase correction of complex-valued data, and minimizing banding artifacts due to field inhomogeneity. The performance of the proposed algorithms is evaluated using both simulation and in-vivo data. The results show improvements over previous approaches, while maintaining a relatively low computational complexity. Using new and improved estimation methods enables better tissue characterization and diagnosis. Furthermore, a sequence design problem is treated, where the radio-frequency excitation is optimized to minimize image artifacts when using amplifiers of limited quality. In turn, obtaining higher fidelity images enables improved diagnosis, and can increase the estimation accuracy in quantitative MRI.

Coherent detection together with multilevel modulation formats has the potential to significantly increase the capacity of existing optical communication systems at no extra cost in signal bandwidth. However, these modulation formats are more susceptible to the impact of different noise sources and distortions as the distance between its constellation points in the complex plane reduces with the modulation index. In this context, digital signal processing (DSP) plays a key role as it allows compensating for the impairments occurring during signal generation, transmission and/or detection relaxing the complexity of the overall system. The transition towards pluggable optical transceivers, offers flexibility for network design/upgrade but sets strict requirements on the power consumption of the DSP thus limiting its complexity. The DSP module complexity however, scales with the modulation order and, in this scenario, low complex yet high performance DSP algorithms are highly desired. In this thesis, we mainly focus on the impact of laser phase noise arising from the transmitter and local oscillator (LO) lasers in coherent optical communication systems employing high order modulation formats. In these systems, the phase noise of the transmitting and LO lasers translate into phase noise in the received constellation impeding the proper recovery of the transmitted data. In order to increase the system phase noise tolerance, we firstly explore the possibility of re-arranging the constellation points in a circularly shaped mQAM (C-mQAM) constellation shape to exploit its inherent phase noise tolerance. Different low-complex carrier phase recovery (CPR) schemes applicable to these constellations are proposed along with a discussion on its performance and implementation complexity. Secondly, the design guidelines of high performance and low complex CPR schemes for conventional square mQAM constellations are presented. We identify the inherent limitation of the state-of-the-art blind phase search (BPS) carrier phase recovery algorithm which hinders its achievable performance and implementation complexity and present a low complex solution to overcome it. The design guidelines of multi-stage CPR schemes for high order modulation formats, where the BPS algorithm is employed at any of the stages, are also provided and discussed. Finally, the interplay between the received dispersed signal and the LO phase noise is analytically investigated to characterize the origin of the equalization enhanced phase noise phenomena. / <p>QC 20170516</p> / EU project ICONE, gr. #608099