Three iteratively reweighted least squares algorithms for $$L_1$$-norm principal component analysis

Principal component analysis (PCA) is often used to reduce the dimension of data by selecting a few orthonormal vectors that explain most of the variance structure of the data. \(L_1\) PCA uses the \(L_1\) norm to measure error, whereas the conventional PCA uses the \(L_2\) norm. For the \(L_1\) PCA problem minimizing the fitting error of the reconstructed data, we propose three algorithms based on iteratively reweighted least squares. We first develop an exact reweighted algorithm. Next, an approximate version is developed based on eigenpair approximation when the algorithm is near convergent. Finally, the approximate version is extended based on stochastic singular value decomposition. We provide convergence analyses, and compare their performance against benchmark algorithms in the literature. The computational experiment shows that the proposed algorithms consistently perform the best and the scalability is improved as we use eigenpair approximation and stochastic singular value decomposition.     

Quantum image rotation by an arbitrary angle

In this paper, a novel method of quantum image rotation (QIR) based on shear transformations on NEQR quantum images is proposed. To compute the horizontal and vertical shear mappings required for rotation, we have designed quantum self-adder, quantum control multiplier, and quantum interpolation circuits as the basic computing units in the QIR implementation. Furthermore, we provide several examples of our results by presenting computer simulation experiments of QIR under \(30^\circ \), \(45^\circ \), and \(60^\circ \) rotation scenarios and have a discussion onto the anti-aliasing and computational complexity of the proposed QIR method.     

Efficient parallelizable hashing using small non-compressing primitives

A well-established method of constructing hash functions is to base them on non-compressing primitives, such as one-way functions or permutations. In this work, we present \(S^r\), an \(rn\)-to-\(n\)-bit compression function (for \(r\ge 1\)) making \(2r-1\) calls to \(n\)-to-\(n\)-bit primitives (random functions or permutations). \(S^r\) compresses its inputs at a rate (the amount of message blocks per primitive call) up to almost 1/2, and it outperforms all existing schemes with respect to rate and/or the size of underlying primitives. For instance, instantiated with the \(1600\)-bit permutation of NIST’s SHA-3 hash function standard, it offers about \(800\)-bit security at a rate of almost 1/2, while SHA-3-512 itself achieves only \(512\)-bit security at a rate of about \(1/3\). We prove that \(S^r\) achieves asymptotically optimal collision security against semi-adaptive adversaries up to almost \(2^{n/2}\) queries and that it can be made preimage secure up to \(2^n\) queries using a simple tweak.     

Good and asymptotically good quantum codes derived from algebraic geometry

In this paper, we construct several new families of quantum codes with good parameters. These new quantum codes are derived from (classical) t-point (\(t\ge 1\)) algebraic geometry (AG) codes by applying the Calderbank–Shor–Steane (CSS) construction. More precisely, we construct two classical AG codes \(C_1\) and \(C_2\) such that \(C_1\subset C_2\), applying after the well-known CSS construction to \(C_1\) and \(C_2\). Many of these new codes have large minimum distances when compared with their code lengths as well as they also have small Singleton defects. As an example, we construct a family \({[[46, 2(t_2 - t_1), d]]}_{25}\) of quantum codes, where \(t_1 , t_2\) are positive integers such that \(1<t_1< t_2 < 23\) and \(d\ge \min \{ 46 - 2t_2 , 2t_1 - 2 \}\), of length \(n=46\), with minimum distance in the range \(2\le d\le 20\), having Singleton defect at most four. Additionally, by applying the CSS construction to sequences of t-point (classical) AG codes constructed in this paper, we generate sequences of asymptotically good quantum codes.     

A quantum watermarking scheme using simple and small-scale quantum circuits

A new quantum gray-scale image watermarking scheme by using simple and small-scale quantum circuits is proposed. The NEQR representation for quantum images is used. The image sizes for carrier and watermark are assumed to be \(2n \times 2n\) and \(n \times n\), respectively. At first, a classical watermark with \(n \times n\) image size and 8 bits gray scale is expanded to an image with \(2n \times 2n\) image size and 2 bits gray scale. Then the expanded image is scrambled to be a meaningless image by the SWAP gates that controlled by the keys only known to the operator. The scrambled image is embedded into the carrier image by the CNOT gates (XOR operation). The watermark is extracted from the watermarked image by applying operations in the reverse order. Simulation-based experimental results show that our proposed scheme is excellent in terms of three items, visual quality, robustness performance under noises, and computational complexity.     

Quantum codes from cyclic codes over $$F_q+uF_q+vF_q+uvF_q$$

In this paper, we study quantum codes over \(F_q\) from cyclic codes over \(F_q+uF_q+vF_q+uvF_q,\) where \(u^2=u,~v^2=v,~uv=vu,~q=p^m\), and p is an odd prime. We give the structure of cyclic codes over \(F_q+uF_q+vF_q+uvF_q\) and obtain self-orthogonal codes over \(F_q\) as Gray images of linear and cyclic codes over \(F_q+uF_q+vF_q+uvF_q\). In particular, we decompose a cyclic code over \(F_q+uF_q+vF_q+uvF_q\) into four cyclic codes over \(F_q\) to determine the parameters of the corresponding quantum code.     

Cost-efficient design of a quantum multiplier–accumulator unit

This paper proposes a cost-efficient quantum multiplier–accumulator unit. The paper also presents a fast multiplication algorithm and designs a novel quantum multiplier device based on the proposed algorithm with the optimum time complexity as multiplier is the major device of a multiplier–accumulator unit. We show that the proposed multiplication technique has time complexity \(O((3 {\hbox {log}}_{2}n)+1)\), whereas the best known existing technique has \(O(n{\hbox {log}}_{2} n)\), where n is the number of qubits. In addition, our design proposes three new quantum circuits: a circuit representing a quantum full-adder, a circuit known as quantum ANDing circuit, which performs the ANDing operation and a circuit presenting quantum accumulator. Moreover, the proposed quantum multiplier–accumulator unit is the first ever quantum multiplier–accumulator circuit in the literature till now, which has reduced garbage outputs and ancillary inputs to a great extent. The comparative study shows that the proposed quantum multiplier performs better than the existing multipliers in terms of depth, quantum gates, delays, area and power with the increasing number of qubits. Moreover, we design the proposed quantum multiplier–accumulator unit, which performs better than the existing ones in terms of hardware and delay complexities, e.g., the proposed (\(n\times n\))—qubit quantum multiplier–accumulator unit requires \(O(n^{2})\) hardware and \(O({\hbox {log}}_{2}n)\) delay complexities, whereas the best known existing quantum multiplier–accumulator unit requires \(O(n^{3})\) hardware and \(O((n-1)^{2} +1+n)\) delay complexities. In addition, the proposed design achieves an improvement of 13.04, 60.08 and 27.2% for \(4\times 4\), 7.87, 51.8 and 27.1% for \(8\times 8\), 4.24, 52.14 and 27% for \(16\times 16\), 2.19, 52.15 and 27.26% for \(32 \times 32\) and 0.78, 52.18 and 27.28% for \(128 \times 128\)-qubit multiplications over the best known existing approach in terms of number of quantum gates, ancillary inputs and garbage outputs, respectively. Moreover, on average, the proposed design gains an improvement of 5.62% in terms of area and power consumptions over the best known existing approach.     

Gauge Neural Network with Z(2) Synaptic Variables: Phase Structure and Simulation of Learning and Recalling Patterns

We study the Z(2) gauge-invariant neural network which is defined on a partially connected random network and involves Z(2) neuron variables \(S_i\) (\(=\pm \)1) and Z(2) synaptic connection (gauge) variables \(J_{ij}\) (\(=\pm \)1). Its energy consists of the Hopfield term \(-c_1S_iJ_{ij}S_j\), double Hopfield term \(-c_2 S_iJ_{ij}J_{jk} S_k\), and the reverberation (triple Hopfield) term \(-c_3 J_{ij}J_{jk}J_{ki}\) of synaptic self interactions. For the case \(c_2=0\), its phase diagram in the \(c_3-c_1\) plane has been studied both for the symmetric couplings \(J_{ij}=J_{ji}\) and asymmetric couplings (\(J_{ij}\) and \(J_{ji}\) are independent); it consists of the Higgs, Coulomb and confinement phases, each of which is characterized by the ability of learning and/or recalling patterns. In this paper, we consider the phase diagram for the case of nonvanishing \(c_2\), and examine its effect. We find that the \(c_2\) term enlarges the region of Higgs phase and generates a new second-order transition. We also simulate the dynamical process of learning patterns of \(S_i\) and recalling them and measure the performance directly by overlaps of \(S_i\). We discuss the difference in performance for the cases of Z(2) variables and real variables for synaptic connections.     

Recursive Computation of Logarithmic Derivatives,Ratios, and Products of Spheroidal Harmonics and Modified Bessel Functions and Applications

Spheroidal harmonics and modified Bessel functions have wide applications in scientific and engineering computing. Recursive methods are developed to compute the logarithmic derivatives, ratios, and products of the prolate spheroidal harmonics (\(P_n^m(x)\), \(Q_n^m(x)\), \(n\ge m\ge 0\), \(x>1\)), the oblate spheroidal harmonics (\(P_n^m(ix)\), \(Q_n^m(ix)\), \(n\ge m\ge 0\), \(x>0\)), and the modified Bessel functions (\(I_n(x)\), \(K_n(x)\), \(n\ge 0\), \(x>0\)) in order to avoid direct evaluation of these functions that may easily cause overflow/underflow for high degree/order and for extreme argument. Stability analysis shows the proposed recursive methods are stable for realistic degree/order and argument values. Physical examples in electrostatics are given to validate the recursive methods.     

No nexiste nce of n-qubit u nexte ndible product bases of size $$2^ n-5$$2 n-5

It is known that the n-qubit system has no unextendible product bases (UPBs) of cardinality \(2^n-1\), \(2^n-2\) and \(2^n-3\). On the other hand, the n-qubit UPBs of cardinality \(2^n-4\) exist for all \(n\ge 3\). We prove that they do not exist for cardinality \(2^n-5\).     

Pure state ‘really’ informationally complete with rank-1 POVM

What is the minimal number of elements in a rank-1 positive operator-valued measure (POVM) which can uniquely determine any pure state in d-dimensional Hilbert space \(\mathcal {H}_d\)? The known result is that the number is no less than \(3d-2\). We show that this lower bound is not tight except for \(d=2\) or 4. Then we give an upper bound \(4d-3\). For \(d=2\), many rank-1 POVMs with four elements can determine any pure states in \(\mathcal {H}_2\). For \(d=3\), we show eight is the minimal number by construction. For \(d=4\), the minimal number is in the set of \(\{10,11,12,13\}\). We show that if this number is greater than 10, an unsettled open problem can be solved that three orthonormal bases cannot distinguish all pure states in \(\mathcal {H}_4\). For any dimension d, we construct \(d+2k-2\) adaptive rank-1 positive operators for the reconstruction of any unknown pure state in \(\mathcal {H}_d\), where \(1\le k \le d\).     

A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines,small looseness,and small slack

We study the problem of non-preemptively scheduling n jobs, each job j with a release time \(t_j\), a deadline \(d_j\), and a processing time \(p_j\), on m parallel identical machines. Cieliebak et al. (2004) considered the two constraints \(|d_j-t_j|\le \lambda {}p_j\) and \(|d_j-t_j|\le p_j +\sigma \) and showed the problem to be NP-hard for any \(\lambda >1\) and for any \(\sigma \ge 2\). We complement their results by parameterized complexity studies: we show that, for any \(\lambda >1\), the problem remains weakly NP-hard even for \(m=2\) and strongly W[1]-hard parameterized by m. We present a pseudo-polynomial-time algorithm for constant m and \(\lambda \) and a fixed-parameter tractability result for the parameter m combined with \(\sigma \).     

New q-ary quantum MDS codes with distances bigger than $$\frac{ q}{2}$$

The construction of quantum MDS codes has been studied by many authors. We refer to the table in page 1482 of (IEEE Trans Inf Theory 61(3):1474–1484, 2015) for known constructions. However, there have been constructed only a few q-ary quantum MDS \([[n,n-2d+2,d]]_q\) codes with minimum distances \(d>\frac{q}{2}\) for sparse lengths \(n>q+1\). In the case \(n=\frac{q^2-1}{m}\) where \(m|q+1\) or \(m|q-1\) there are complete results. In the case \(n=\frac{q^2-1}{m}\) while \(m|q^2-1\) is neither a factor of \(q-1\) nor \(q+1\), no q-ary quantum MDS code with \(d> \frac{q}{2}\) has been constructed. In this paper we propose a direct approach to construct Hermitian self-orthogonal codes over \(\mathbf{F}_{q^2}\). Then we give some new q-ary quantum codes in this case. Moreover many new q-ary quantum MDS codes with lengths of the form \(\frac{w(q^2-1)}{u}\) and minimum distances \(d > \frac{q}{2}\) are presented.     

Two Mixed Finite Element Methods for Time-Fractional Diffusion Equations

Based on spatial conforming and nonconforming mixed finite element methods combined with classical L1 time stepping method, two fully-discrete approximate schemes with unconditional stability are first established for the time-fractional diffusion equation with Caputo derivative of order \(0<\alpha <1\). As to the conforming scheme, the spatial global superconvergence and temporal convergence order of \(O(h^2+\tau ^{2-\alpha })\) for both the original variable u in \(H^1\)-norm and the flux \(\vec {p}=\nabla u\) in \(L^2\)-norm are derived by virtue of properties of bilinear element and interpolation postprocessing operator, where h and \(\tau \) are the step sizes in space and time, respectively. At the same time, the optimal convergence rates in time and space for the nonconforming scheme are also investigated by some special characters of \(\textit{EQ}_1^{\textit{rot}}\) nonconforming element, which manifests that convergence orders of \(O(h+\tau ^{2-\alpha })\) and \(O(h^2+\tau ^{2-\alpha })\) for the original variable u in broken \(H^1\)-norm and \(L^2\)-norm, respectively, and approximation for the flux \(\vec {p}\) converging with order \(O(h+\tau ^{2-\alpha })\) in \(L^2\)-norm. Numerical examples are provided to demonstrate the theoretical analysis.     

Hybridized Discontinuous Galerkin Method for Elliptic Interface Problems: Error Estimates Under Low Regularity Assumptions of Solutions

New hybridized discontinuous Galerkin (HDG) methods for the interface problem for elliptic equations are proposed. Unknown functions of our schemes are \(u_h\) in elements and \(\hat{u}_h\) on inter-element edges. That is, we formulate our schemes without introducing the flux variable. We assume that subdomains \(\Omega _1\) and \(\Omega _2\) are polyhedral domains and that the interface \(\Gamma =\partial \Omega _1\cap \partial \Omega _2\) is polyhedral surface or polygon. Moreover, \(\Gamma \) is assumed to be expressed as the union of edges of some elements. We deal with the case where the interface is transversely connected with the boundary of the whole domain \(\overline{\Omega }=\overline{\Omega _1\cap \Omega _2}\). Consequently, the solution u of the interface problem may not have a sufficient regularity, say \(u\in H^2(\Omega )\) or \(u|_{\Omega _1}\in H^2(\Omega _1)\), \(u|_{\Omega _2}\in H^2(\Omega _2)\). We succeed in deriving optimal order error estimates in an HDG norm and the \(L^2\) norm under low regularity assumptions of solutions, say \(u|_{\Omega _1}\in H^{1+s}(\Omega _1)\) and \(u|_{\Omega _2}\in H^{1+s}(\Omega _2)\) for some \(s\in (1/2,1]\), where \(H^{1+s}\) denotes the fractional order Sobolev space. Numerical examples to validate our results are also presented.     

Throughput maximization for speed scaling with agreeable deadlines

We study the following energy-efficient scheduling problem. We are given a set of n jobs which have to be scheduled by a single processor whose speed can be varied dynamically. Each job \(J_j\) is characterized by a processing requirement (work) \(p_j\), a release date \(r_j\), and a deadline \(d_j\). We are also given a budget of energy E which must not be exceeded and our objective is to maximize the throughput (i.e., the number of jobs which are completed on time). We show that the problem can be solved optimally via dynamic programming in \(O(n^4 \log n \log P)\) time when all jobs have the same release date, where P is the sum of the processing requirements of the jobs. For the more general case with agreeable deadlines where the jobs can be ordered so that, for every \(i < j\), it holds that \(r_i \le r_j\) and \(d_i \le d_j\), we propose an optimal dynamic programming algorithm which runs in \(O(n^6 \log n \log P)\) time. In addition, we consider the weighted case where every job \(J_j\) is also associated with a weight \(w_j\) and we are interested in maximizing the weighted throughput (i.e., the total weight of the jobs which are completed on time). For this case, we show that the problem becomes \(\mathcal{NP}\)-hard in the ordinary sense even when all jobs have the same release date and we propose a pseudo-polynomial time algorithm for agreeable instances.     

The local–global conjecture for scheduling with non-linear cost

We consider the classical scheduling problem on a single machine, on which we need to schedule sequentially n given jobs. Every job j has a processing time \(p_j\) and a priority weight \(w_j\), and for a given schedule a completion time \(C_j\). In this paper, we consider the problem of minimizing the objective value \(\sum _j w_j C_j^\beta \) for some fixed constant \(\beta >0\). This non-linearity is motivated for example by the learning effect of a machine improving its efficiency over time, or by the speed scaling model. For \(\beta =1\), the well-known Smith’s rule that orders job in the non-increasing order of \(w_j/p_j\) gives the optimum schedule. However, for \(\beta \ne 1\), the complexity status of this problem is open. Among other things, a key issue here is that the ordering between a pair of jobs is not well defined, and might depend on where the jobs lie in the schedule and also on the jobs between them. We investigate this question systematically and substantially generalize the previously known results in this direction. These results lead to interesting new dominance properties among schedules which lead to huge speed up in exact algorithms for the problem. An experimental study evaluates the impact of these properties on the exact algorithm A*.     

A Weak Galerkin Method with an Over-Relaxed Stabilization for Low Regularity Elliptic Problems

A new weak Galerkin (WG) finite element method is developed and analyzed for solving second order elliptic problems with low regularity solutions in the Sobolev space \(W^{2,p}(\Omega )\) with \(p\in (1,2)\). A WG stabilizer was introduced by Wang and Ye (Math Comput 83:2101–2126, 2014) for a simpler variational formulation, and it has been commonly used since then in the WG literature. In this work, for the purpose of dealing with low regularity solutions, we propose to generalize the stabilizer of Wang and Ye by introducing a positive relaxation index to the mesh size h. The relaxed stabilization gives rise to a considerable flexibility in treating weak continuity along the interior element edges. When the norm index \(p\in (1,2]\), we strictly derive that the WG error in energy norm has an optimal convergence order \(O(h^{l+1-\frac{1}{p}-\frac{p}{4}})\) by taking the relaxed factor \(\beta =1+\frac{2}{p}-\frac{p}{2}\), and it also has an optimal convergence order \(O(h^{l+2-\frac{2}{p}})\) in \(L^2\) norm when the solution \(u\in W^{l+1,p}\) with \(p\in [1,1+\frac{2}{p}-\frac{p}{2}]\) and \(l\ge 1\). It is recovered for \(p=2\) that with the choice of \(\beta =1\), error estimates in the energy and \(L^2\) norms are optimal for the source term in the sobolev space \(L^2\). Weak variational forms of the WG method give rise to desirable flexibility in enforcing boundary conditions and can be easily implemented without requiring a sufficiently large penalty factor as in the usual discontinuous Galerkin methods. In addition, numerical results illustrate that the proposed WG method with an over-relaxed factor \(\beta (\ge 1)\) converges at optimal algebraic rates for several low regularity elliptic problems.     

Quantum Fourier transform in computational basis

The quantum Fourier transform, with exponential speed-up compared to the classical fast Fourier transform, has played an important role in quantum computation as a vital part of many quantum algorithms (most prominently, Shor’s factoring algorithm). However, situations arise where it is not sufficient to encode the Fourier coefficients within the quantum amplitudes, for example in the implementation of control operations that depend on Fourier coefficients. In this paper, we detail a new quantum scheme to encode Fourier coefficients in the computational basis, with fidelity \(1 - \delta \) and digit accuracy \(\epsilon \) for each Fourier coefficient. Its time complexity depends polynomially on \(\log (N)\), where N is the problem size, and linearly on \(1/\delta \) and \(1/\epsilon \). We also discuss an application of potential practical importance, namely the simulation of circulant Hamiltonians.